Katalog przedmiotów
Algorytmy i struktury danych 2
CeleCelem kształcenia jest przedstawienie zaawansowanych zagadnień algorytmiki. Omawiane są następujące modele obliczeniowe: układy logiczne, automaty skończone, automaty ze stosem, maszyny Turinga (RAM, PRAM). Równolegle przedstawiana jest hierarchia języków Chomsky’ego: języki regularne, bezkontekstowe, kontekstowe i gramatyki typu 0. Wprowadzane są definicje klas złożoności obliczeniowej (NC, P, NP, PSPACE etc.) oraz relacje zachodzące między tymi klasami. Szczególny nacisk kładziony jest na omówienie problemu P vs. NP. Analizowane są również algorytmy dokładne i aproksymacyjne dla szeregu różnych problemów z klasy NP-trudnych.
Zakres
Układy logiczne, złożoność obliczeniowa. Szybkie i potokowe układy arytmetyczne. Szybkie sieci sortujące DFT, FFT, RMT, twierdzenie o splocie. Automaty skończone, języki regularne. Automaty ze stosem, języki bezkontekstowe. Maszyny Turinga, gramatyki typu 0, hierarchia Chomskiego. Klasy złożoności, NP, PTIME, PSPACE, tw. Savitcha. Twierdzenie Cooka. Algorytmy dokładne dla problemów NP-trudnych. Algorytmy aproksymacyjne dla problemów NP-trudnych. Problem pokrycia wierzchołkowego, kliki, zbioru niezależnego. Pokrycie zbiorami. Rodzina testująca. Transwersala w hipergrafie. Kolorowanie wierzchołkowe grafów. Algorytmy randomizacyjne i relaksacja dla problemów NP-trudnych.
Literatura podstawowa
1. T. Cormen, Ch. Leiserson, R. Rivest: Wprowadzenie do algorytmów, WNT.
Literatura uzupełniająca
1. G. Ausiello and others: Complexity and Approximation, Springer.
2. J. Hromković: Algorithms for Hard Problems, Springer.
3. J. Savage: Models of Computation, Addison Wesley.
Punkty ECTS
5 - niestacjonarne,
5 - stacjonarne
Rodzaje studiów, na których przedmiot jest realizowany
niestacjonarne - 1-go stopnia,
stacjonarne - 1-go stopnia
Specjalności, na których przedmiot jest realizowany
Inżynieria oprogramowania
Prowadzący
dr Piotr Sapiecha
