Problem sumy podzbioru - podejście przez szeregi potęgowe.

Mając zbiór n liczb całkowitych dodatnich S i liczbę t, problem sumy podzbiorupolega na sprawdzeniu czy istnieje podzbiór S, którego elementy sumują się do t.Ten dość prosto sformułowany problem należy jednak do klasy problemów NPzupełnych. W celu jego rozwiązania powstało wiele algorytmów, korzystającychz rozmaitych technik programistycznych.Celem tej pracy jest implementacja randomizowanego algorytmu autorstwaCe Jin i Hongxun Wu, opisanego w [6] i rozwiązującego powyższy problem wwersji zliczającej liczbę możliwych podzbiorów modulo liczba pierwsza p > t.Działa on w czasie O˜(n + t), który uważany jest niemal optymalny (notacja O˜zawiera polilogarytmiczne czynniki). Ważnym wkładem będzie stworzenie biblioteczki operującej na szeregach formalnych, która umożliwi policzenie głównej części algorytmu alternatywnym sposobem - za pomocą iteracyjnej metodyNewtona.

Given a set S of n positive integers and number t, the Subset Sum problem asks todetermine whether there exists a subset of S that sums up to t. This easy to formulate problem is, however, NP-complete. In order to solve it, many algorithms have been created using various programming techniques.Goal of this thesis is implementation of randomized algorithm by Ce Jin and Hongxun Wu described in [6] and solving above problem in its counting version modulo prime number p > t.Its running time is O˜(n + t), which is said to be near optimal (notation O˜ contains polilogarithmic factors). Important contribution will be library operating on formal power series, which will enable calculating main part of algorithm in alternative way - by Newtons iterative method.