Zajęcia 3: meet in the middle

Zadanie 1: Problem plecakowy

Mamy n przedmiotów o wagach a_i i wartościach c_i. Mamy plecak o pojemności M. Chcemy do niego zmieścić przedmioty o jak największej łącznej wartości.

Zazwyczaj widzi się rozwiązania tego problemu za pomocą programowania dynamicznego. Jednak takie rozwiązania nie mają szans, jeśli a_i, c_i oraz M są z zakresu [0, 10⁸]. W przypadku dowolnie dużych wag i wartości przedmiotów problem okazuje się NP-trudny! Dlatego rozwiążemy go dla n ≤ 40.

Algorytm działający w czasie O(2^n/2 * n) można wysnuć z opracowania zadania Szyfr z IX OI.

Zadanie 2: Logarytm dyskretny

Dane są liczba pierwsza p, p < 10⁹, oraz liczby 0 ≤ a,b < p. Chcemy znaleźć całkowity wykładnik m, taki że a^m = b (mod p).

Istnieje algorytm działający w czasie O(√ p log p), tzw. algorytm Baby-Step-Giant-Step, patrz s. 19–20 w czwartej części skryptu prof. Guzickiego z Algorytmicznej Teorii Liczb. Uwaga: w rozwiązaniu zadania jest potrzebne obliczanie odwrotności modulo liczba pierwsza, co można wykonać za pomocą rozszerzonego algorytmu Euklidesa lub Małego Twierdzenia Fermata.

Zadanie 3: Zliczanie klik

Dany jest graf nieskierowany G o n ≤ 50 wierzchołkach. Chcemy wyznaczyć liczbę wszystkich klik w tym grafie. Przypomnijmy, że klika w grafie to zbiór wierzchołków, z których każde dwa są połączone krawędzią. Mamy też klikę pustą i wszystkie kliki jednowierzchokowe.

Algorytm o złożoności O(2^n/2) można znaleźć w IKO z Delty 3/2013 autorstwa Tomasza Idziaszka.

Zadanie domowe

Zadanie domowe: implementacja rozwiązania zadania Zliczanie klik na ASD-SIO.