Algorytmy probablistyczne


Informacje ogólne

Typ:obowiazkowy
Kierunek:Informatyka studia drugiego stopnia
Specjalność:Algorytmy
Semestr:2
Wymiar zajęć:30h wykładu + 30h ćwiczeń
Punkty ECTS:7

Program

Algorytmy probabilistyczne losują w trakcie swojego obliczenia liczby lub ciągi bitów i uzależniają dalsze obliczenie od tego, co wylosowały. Dla wielu problemów takie algorytmy są prostrze i szybsze od deterministycznych. Algorytmy probabilistyczne są też wykorzystywane w kryptografii. Na wykładzie przedstawię kilka prostych algorytmów i na ich przykładzie omówię podstawowe techniki probabilistyczne. Nie wymagam od słuchaczy dużej wiedzy z rachunku prawdopodobieństwa. Podstawowy aparat matematyczny przedstawię na wykładzie.
Główne tematy wykładu: algorytmy z jednostronnymi i dwustronnymi błędami, techniki zmniejszania prawdopodobieństwa błędu, testy pierwszości, generatory liczb pierwszych, odciski palców (fingerprinting), weryfikacja iloczynu macierzy, perfect matching, błądzenie (random walks), łańcuchy Markowa, funkcje haszujące, dowody interakcyjne, dowody z wiedzą zerową, generatory bitów losowych, probabilistyczne klasy złożoności.

Literatura

  • R.Motwani, P.Raghavan, Randomized Algorithms, Cambridge University Press 1995.
  • A.Menezes, P. van Oorschot, S.Vanstone, Handbook of Applied Cryptography, CRC Press 1997.
  • C.H.Papadimitriou, Computational Complexity, Addison-Weseley Publishing Company 1994.