Wykład Zaawansowane techniki algorytmiczne
studia inżynierskie PPT, informatyka
prof. Mirosław Kutyłowski
Tematy poruszane na wykładach
- fingerprinting: wykrywanie błędów transmisji- interpretacja przy pomocy
wielomianów modulo p, testowanie poprawności iloczynu macierzy,
testowanie równości symbolicznych
- alokacja zasobów - losowy wybór, analiza "rzucania kul do urn",
przypadek n kul i n urn, przykłady pokrewnych protokołów
- algorytm selekcji przez sampling, analiza zachowania algorytmu
- two-point sampling: testy pierwszości, redukcja liczby losowań, analiza
prawdopodobieństwa błędnego wyniku
- problem kolekcjonowania kuponów, zastosowania, analiza czasu działania
- routing: model: kolejkowanie pakietów, algorytm z losowymi adresami pośrednimi,
hiperkostka, protokół bit fixing na hiperkostce,
tw. o opóźnieniach dla
algorytmów deterministycznych, analiza zachowania dla algorytmu z
losowymi pośrednimi
adresami
- metoda probabilistyczna: podział grafów, problem MAX-SAT,
metoda spełniania co najmniej połowy klauzul,
programowanie całkowitoliczbowe i programowanie liniowe,
algorytm losowego zaokrąglania, pojęcie algorytmu aproksymacyjnego,
dowód jakości rozwiązania dla MAX-SAT
- algorytmy online: pojęcie algorytmu online,
przykład zagadnienia: administarcja cache'em, paging,
algorytmy: MIN (off-line) i MARKER (online), analiza
konkurencyjności MARKERa.
- programowanie liniowe: metodyka zastosowań, sprowadzanie
do postaci standardowej, rozwiązania bazowe,
przechodzenie do nowych rozwiązań bazowych,
informacje o złożoności algorytmu, problem dualny i
rozwiązywanie problemu dualnego,
- branch and bound dla problemu komiwojażera,
- algorytmy wyżarzania (simulated annealing), algorytmy genetyczne