Automaty, obliczalność i złożoność Teoria złożoności Teoria obliczalności Teoria automatów Pojęcia matematyczne i terminologia Zbiory Ciągi i krotki Funkcje i relacje Grafy Słowa i języki Logika Boole'a14 Podsumowanie terminów matematycznych Definicje, twierdzenia i dowody Znajdowanie dowodów Typy dowodów Dowód przez konstrukcję Dowód nie wprost (przez sprowadzenie do sprzeczności) Dowód indukcyjny Dowód AUTOMATY I JĘZYKI Języki regularne Automaty skończone Formalna definicja automatu skończonego Przykłady automatów skończonych Formalna definicja obliczeń Projektowanie automatów skończonych Operacje regularne Niedeterminizm Formalna definicja niedeterministycznego automatu skończonego Równoważność NFA i DFA Zamknięcie ze względu na operacje regularne Wyrażenia regularne Formalna definicja wyrażenia regularnego Równoważność z automatami skończonymi Języki nieregularne Lemat o pompowaniu dla języków regularnych 2.Języki bezkontekstowe Gramatyki bezkontekstowe Formalna definicja gramatyki bezkontekstowej Projektowanie gramatyk bezkontekstowych Niejednoznaczność Postać normalna Chomsky'ego Automaty ze stosem Formalna definicja automatu ze stosem Przykłady automatów ze stosem Równoważność z gramatykami bezkontekstowymi Języki niebędące bezkontekstowymi Lemat o pompowaniu dla języków bezkontekstowych Deterministyczne języki bezkontekstowe Właściwości języków DCFL Deterministyczne gramatyki bezkontekstowe Zależności między DPDA a gramatykami DCFG Parsing i gramatyki LR(k) TEORIA OBLICZALNOŚCI Hipoteza Churcha-Turinga Maszyny Turinga Formalna definicja maszyny Turinga Przykłady maszyn Turinga Odmiany maszyn Turinga Wielotaśmowe maszyny Turinga Niedeterministyczne maszyny Turinga Enumeratory Równoważność z innymi modelami Definicja algorytmu Problemy Hilberta Konwencja opisywania maszyn Turinga Rozstrzygalność Języki rozstrzygalne Problemy rozstrzygalne dotyczące języków regularnych Problemy rozstrzygalne dotyczące języków bezkontekstowych Nierozstrzygalność Metoda diagonalizacji Język nierozstrzygalny Język nierozpoznawalny w sensie Turinga Redukowalność Nierozstrzygalne problemy teorii języków Redukcje przez historie obliczeń Prosty problem nierozstrzygalny Redukcja przez odwzorowanie Funkcje obliczalne Formalna definicja redukcji przez odwzorowanie Zaawansowane zagadnienia teorii obliczalności Twierdzenie o rekurencji Samoodniesienie Posługiwanie się twierdzeniem o rekurencji Zastosowania Rozstrzygalność teorii logicznych Teoria rozstrzygalna Teoria nierozstrzygalna Redukowalność w sensie Turinga Pojęcie informacji Opisy minimalnej długości Optymalność definicji Słowa niekompresowalne i losowość TEORIA ZŁOŻONOŚCI Złożoność czasowa Mierzenie złożoności Notacja wielkiego O i małego o Analiza algorytmów Zależności między złożonościami modeli Klasa P Czas wielomianowy Przykłady problemów z klasy P Klasa NP Przykłady problemów z klasy NP Zagadnienie P versus NP NP-zupełność Redukowalność w czasie wielomianowym Definicja NP-zupełności Twierdzenie Cooka-Levina Dalsze problemy NP-zupełne Problem pokrycia wierzchołkowego Problem ścieżki Hamiltona Problem sumy podzbioru Złożoność pamięciowa Twierdzenie Savitcha Klasa PSPACE PSPACE-zupełność Problem TQBF Strategie wygrywające w grach Uogólniona gra w łańcuszek Klasy L i NL NL-zupełność Przeszukiwanie grafów Klasa NL równa się klasie coNL Problemy trudne Twierdzenia o hierarchii Zupełność pamięci wykładniczej Relatywizacja Ograniczenia stosowalności metody diagonalizacji Złożoność obwodów Zaawansowane zagadnienia teorii złożoności Algorytmy aproksymacyjne Algorytmy probabilistyczne Klasa BPP Pierwszość Programy z rozgałęzieniami z jednokrotnym odczytem Alternacje Czas i pamięć w obliczeniach alternujących Wielomianowa hierarchia czasowa Systemy dowodów interaktywnych Nieizomorfizm grafów Definicja modelu IP = PSPACE Obliczenia równoległe Jednolite obwody logiczne Klasa NC P-zupełność Kryptografia Klucze tajne Systemy szyfrowania z kluczem publicznym Funkcje jednokierunkowe Funkcje z bocznym wejściem