Podstawowe własności permanentu

In linear algebra the permanent is a function similar to the determinant, which has many applications in combinatorics and graph theory. Because a polynomial time algorithm for computing the permanent is not known, we use different methods for bounding its value. In the first part of the thesis there are shown definition and basic properties of the permanent and also the best known method for computing the permanent. The second part presents the inequalities connected with the permanent - upper bound for nonnegative matrices and zero-one matrices. The last part of the thesis includes a Python code for computing and estimating the permanent.

W algebrze liniowej permanent macierzy kwadratowej jest funkcją podobną do wyznacznika, mającą wiele zastosowań w kombinatoryce oraz teorii grafów. Ponieważ nie jest znany wielomianowy algorytm, który pozwalałby wyznaczyć dokładną wartość permanentu, stosuje się metody pozwalające oszacować jego wartość. W pierwszej części pracy omówione zostały definicja i podstawowe własności permanentu macierzy, a także najefektywniejsza znana metoda jego obliczania. Druga część natomiast przedstawia nierówności związane z permanentem - górne oszacowanie wartości permanentu dla macierzy nieujemnych oraz zero-jedynkowych. Ostatnia część pracy zawiera kod w języku Python służący do obliczania i szacowania permanentu.