Generowanie obiektów losowych przy użyciu łańcuchów Markova

Celem tej pracy jest zaprezentowanie użycia łańcuchów Markova jako narzędzia do generowania losowych obiektów (z rozkładem jednostajnym, w czasie wielomianowym).Praca ta została napisana w oparciu o książkę A. Sinclair "Algorithms for Random Generation and Counting".Postanowiliśmy wybrać najważniejsze pojęcia i twierdzenia dotyczące łańcuchów Markova oraz zaprezentować ich zastosowanie w problemie generowania losowych skojarzeń doskonałych w grafach dwudzielnych. Ponadto praca zawiera program testujący wykorzystywane techniki.The aim of this work is to present the use of Markov Chains as a tool for generating random objects(with uniform distribution and polynomial time).The work is based on the book "Algorithms for Random Generation and Counting" by Sinclair.We decided to extract the most important notions and theorems regarding Markov chains and to show their application in the problem of generating random matchings in dense bipartite graphs. Additionally, the work includes a program testing presented techniques