Nazywam się Tomasz Idziaszek, a to jest miejsce, w którym gromadzę moje zapiski dotyczące algorytmów przydatnych w konkursach programistycznych. Zacząłem w marcu 2018 i planuję publikować nowy artykuł co około dwa miesiące. Z uwagi na to, by materiały na tej stronie mogły być przydatne jak najszerszej grupie czytelników, większość z nich jest w języku angielskim.

Notatki

Dynamic programming on trees with minimal memory

Szczegółowa analiza, jak rozwiązać klasyczne zadanie korzystające z metody programowania dynamicznego na drzewie, ale używając jak najmniej pamięci operacyjnej. Pokazuje nieefektywność standardowego podejścia (wektory, rekursja), opisuje różne reprezentacje drzew w pamięci (z pomysłowymi metodami kompresji, ale umożliwiającej obchodzenie drzewa) i parę trików optymalizujących obliczenia. EN

Opublikowane w marcu 2018

Survey of knapsack problems

Opis licznych wariantów problemu plecakowego rozwiązywanych przeważnie przy pomocy programowania dynamicznego. Zawiera wariant zero-jedynkowy, nieograniczony i ograniczony, jak również plecaki z elementami o różnych kosztach, o ograniczonym czasie życia, związane zależnościami itd. EN

Opublikowane w maju 2018 (prace w toku; dostępna pierwsza część)

Counting perfect matchings in grids and planar graphs

Opis algorytmów zliczających doskonałe skojarzenia w pewnych klasach grafów. Omawia trudność tego problemu dla grafów ogólnych związaną z obliczaniem permanentu i pokazuje dwa pomysłowe algorytmy, które sprowadzają ten problem dla krat i grafów planarnych do obliczenia wyznacznika sprytnie zmodyfikowanych macierzy. EN

Opublikowane we wrześniu 2018 (prace w toku; dostępna pierwsza część)