MIMINF:Języki, automaty i obliczenia: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Diks (dyskusja | edycje)
538 edycji
Tarlecki (dyskusja | edycje)
272 edycje
 
(Nie pokazano 8 wersji utworzonych przez 2 użytkowników)
Linia 3: Linia 3:


== Opis ==
== Opis ==
Podstawowe modele obliczeń (automaty, gramatyki, maszyna Turinga), związki między trudnoœścią problemów obliczeniowych a strukturalną złożonoœcią modeli obliczeń. Hierarchia Chomsky'ego. Matematyczny sens pojęcia obliczalnośœci oraz jego ograniczenia, a także - w zarysie - podstawowe zagadnienia złożonośœci obliczeniowej.
Podstawowe modele obliczeń (automaty, gramatyki, maszyna Turinga), związki między trudnością problemów obliczeniowych a strukturalną złożonością modeli obliczeń. Hierarchia Chomsky'ego. Matematyczny sens pojęcia obliczalności oraz jego ograniczenia, a także - w zarysie - podstawowe zagadnienia złożoności obliczeniowej.


== Sylabus ==
== Sylabus ==
Linia 10: Linia 10:


=== Wymagania wstępne ===
=== Wymagania wstępne ===
* Podstawy matematy
* Podstawy matematyki
* Matematyka dyskretna
* Matematyka dyskretna
* Wstęp do programowania
* Wstęp do programowania


=== Zawartość ===
=== Zawartość ===
* Podstawowe zasady analizy algorytmów:
*Elementy teorii języków formalnych: słowa, języki, wyrażenia regularne.
** poprawność
*Automaty skończone i twierdzenie Kleene'go o efektywnej odpowiedniości automatów i wyrażeń.
** złożoność obliczeniowa algorytmu (czasowa i pamieciowa, pesymistyczna i oczekiwana, koszt zamortyzowany)
*Konstrukcje optymalizujące automaty - determinizacja, minimalizacja.
** złożoność problemu algorytmicznego a złożoność algorytmu - dolne granice, metody analizy złożoności
*Języki bezkontekstowe: gramatyki i ich postaci normalne.
* Metody projektowania wydajnych algorytmów:
*Odpowiedniość gramatyk bezkontekstowych i niedeterministycznych automatów ze stosem.
** metoda ''dziel i zwyciężaj''
*Kryteria rozróżniania języków regularnych i bezkontekstowych - lematy o pompowaniu.
** algorytmy zachłanne
*Zagadnienia algorytmiczne: problem niepustości dla automatów i gramatyk, rozpoznawanie jezyków bezkontekstowych.
** pogramowanie dynamiczne
*Przykłady zastosowań automatów i gramatyk.
** przeszukiwanie z nawrotami i metoda podziału i ograniczeń
*Uniwersalne modele obliczeń: maszyna Turinga i jej warianty.
** transformacyjna konstrukcja algorytmu
*Granice obliczalności: nierozstrzygalność problemu stopu, przykłady praktycznych problemów nierozstrzygalnych.
* Sortowanie:
*Podsumowanie - klasyfikacja  gramatyk, modeli obliczeń i języków według hierarchii Chomsky'ego.
** sortowanie przez porównania (sortowanie przez wstawianie - ''InsertionSort'', sortowanie szybkie - ''QuickSort'', sortowanie przez scalanie - ''MergeSort'')
*Wprowadzenie do zagadnień złożoności obliczeniowej: klasy P i NP.
** proste kolejki priorytetowe: kopce binarne
*Twierdzenie Cooka-Levina o NP-zupełności SAT.
** sortowanie kopcowe - ''HeapSort''
*Hipoteza P=/=NP i jej praktyczne implikacje, informacja o  pozytywnych zastosowaniach problemów trudnych obliczeniowo, np. w kryptografii.
** sortowanie pozycyjne
** złożoność problemu sortowania
* Selekcja:
** algorytm Hoare'a
** algorytm ''magicznych piątek''
* Wyszukiwanie i słowniki:
** wyszukiwanie liniowe i binarne
** drzewa wyszukiwań binarnych, zrównoważone drzewa wyszukiwań binarnych (AVL, drzewa czerwono-czarne, drzewa typu ''splay'')
** haszowanie (funkcje haszujące, haszowanie uniwersalne, metody rozwiązywania kolizji, haszowanie doskonałe)
** B-drzewa
*Kolejki priorytetowe:
**złączalne kolejki priorytetowe (kopce dwumianowe i Fibonacciego)
**algorytm Dijkstry
*Problem "Find-Union" i jego zastosowania
*Algorytmy grafowe:
**komputerowe reprezentacje grafów
**metody przeszukiwania grafów i ich zastosowania - najkrótsze ścieżki, spójność, dwuspójność, silna spójność, sortowanie topologiczne 
** problemy ścieżkowe
** minimalne drzewo rozpinające
** najliczniejsze skojarzenia w grafach dwudzielnych
* Wyszukiwanie wzorca w tekstach:
** prefikso-sufiksy
** algorytm Knutha-Morisa-Pratta
*Tekstowe struktury danych:
**tablice sufiksowe
**drzewa sufiksowe


=== Literatura ===
=== Literatura ===
# L. Banachowski, K. Diks, W. Rytter, ''Algorytmy i struktury danych'', Wydawnictwa Naukowo - Techniczne, 2006.
# J. E. Hopcroft, R. Motwani, J. D. Ullman, ''Wprowadzenie do teorii automatów, języków i obliczeń'', PWN, Warszawa 2005.
# Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,  ''Wprowadzenie do algorytmów'', Wydawnictwa Naukowo - Techniczne, 2004.
# Ch. Papadimitriou, ''Złożoność obliczeniowa'', WNT, Warszawa 2002.

Aktualna wersja na dzień 12:50, 11 sty 2007

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Podstawowe modele obliczeń (automaty, gramatyki, maszyna Turinga), związki między trudnością problemów obliczeniowych a strukturalną złożonością modeli obliczeń. Hierarchia Chomsky'ego. Matematyczny sens pojęcia obliczalności oraz jego ograniczenia, a także - w zarysie - podstawowe zagadnienia złożoności obliczeniowej.

Sylabus

Autorzy

  • Damian Niwiński — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki, Instytut Informatyki

Wymagania wstępne

  • Podstawy matematyki
  • Matematyka dyskretna
  • Wstęp do programowania

Zawartość

  • Elementy teorii języków formalnych: słowa, języki, wyrażenia regularne.
  • Automaty skończone i twierdzenie Kleene'go o efektywnej odpowiedniości automatów i wyrażeń.
  • Konstrukcje optymalizujące automaty - determinizacja, minimalizacja.
  • Języki bezkontekstowe: gramatyki i ich postaci normalne.
  • Odpowiedniość gramatyk bezkontekstowych i niedeterministycznych automatów ze stosem.
  • Kryteria rozróżniania języków regularnych i bezkontekstowych - lematy o pompowaniu.
  • Zagadnienia algorytmiczne: problem niepustości dla automatów i gramatyk, rozpoznawanie jezyków bezkontekstowych.
  • Przykłady zastosowań automatów i gramatyk.
  • Uniwersalne modele obliczeń: maszyna Turinga i jej warianty.
  • Granice obliczalności: nierozstrzygalność problemu stopu, przykłady praktycznych problemów nierozstrzygalnych.
  • Podsumowanie - klasyfikacja gramatyk, modeli obliczeń i języków według hierarchii Chomsky'ego.
  • Wprowadzenie do zagadnień złożoności obliczeniowej: klasy P i NP.
  • Twierdzenie Cooka-Levina o NP-zupełności SAT.
  • Hipoteza P=/=NP i jej praktyczne implikacje, informacja o pozytywnych zastosowaniach problemów trudnych obliczeniowo, np. w kryptografii.

Literatura

  1. J. E. Hopcroft, R. Motwani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, Warszawa 2005.
  2. Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=MIMINF:Języki,_automaty_i_obliczenia&oldid=68403”