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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Diks (dyskusja | edycje)
538 edycji
Diks (dyskusja | edycje)
538 edycji
Linia 15: Linia 15:


=== 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  pozytywnym zastosowanie 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.
# L. Banachowski, K. Diks, W. Rytter, ''Algorytmy i struktury danych'', Wydawnictwa Naukowo - Techniczne, 2006.
# Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,  ''Wprowadzenie do algorytmów'', Wydawnictwa Naukowo - Techniczne, 2004.
# Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,  ''Wprowadzenie do algorytmów'', Wydawnictwa Naukowo - Techniczne, 2004.

Wersja z 09:04, 18 paź 2006

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 matematy
  • 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 pozytywnym zastosowanie problemów trudnych obliczeniowo, np. w kryptografii.

Literatura

  1. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, Wydawnictwa Naukowo - Techniczne, 2006.
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, Wydawnictwa Naukowo - Techniczne, 2004.
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=MIMINF:Języki,_automaty_i_obliczenia&oldid=64183”