Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Języki, automaty i obliczenia

Informacje ogólne

Kod przedmiotu: 1000-214bJAO Kod Erasmus / ISCED: 11.302 / (0612) Database and network design and administration
Nazwa przedmiotu: Języki, automaty i obliczenia
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty fakultatywne dla studiów 2 stopnia na matematyce
Przedmioty fakultatywne na matematyce
Przedmioty obowiązkowe dla II roku (4. semestr) JSIM - wariant 3I+4M
Przedmioty obowiązkowe dla II roku (4. semestr) JSIM - wariant 3M+4I
Przedmioty obowiązkowe dla II roku informatyki
Punkty ECTS i inne: 5.00
zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Wymagania (lista przedmiotów):

Algorytmy i struktury danych 1000-213bASD
Matematyka dyskretna 1000-212bMD
Podstawy matematyki 1000-211bPM
Wstęp do programowania (podejście imperatywne) 1000-211bWPI

Skrócony 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.

Pełny opis:

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 językó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.

Efekty uczenia się:

Student ma wiedzę o podstawowych problemach i technikach związanych z konstruowaniem automatów i gramatyk, oraz z różnymi modelami obliczeniowymi. Poza tym potrafi względnie precyzyjnie przeprowadzać dowody faktów związanych z tą dziedziną. Umiejętność precyzyjnego dowodzenia poprawności różnego rodzaju konstrukcji informatycznych jest najsłabszą stroną studentów informatyki i jednym z najważniejszych efektów jest polepszenie tej umiejętności. Przedmiot ten się świetnie do tego nadaje ponieważ ma charakter częściowo matematyczny i uczy abstrahowania podstawowych elementów w różnego rodzaju konstrukcjach i modelach obliczeniowych (K_U31, K_W16).

W szczególności student:

1. Ma uporządkowaną wiedzę w zakresie konstrukcji automatów skończonych, ich minimalizacji i równoważności.

2. Zna związki automatów z wyrażeniami regularnymi. Umie udowodnić, że wybrany język formalny nie jest regularny.

3. Ma podstawową wiedzę w zakresie gramatyk bezkontekstowych i zna ich związki z automatami stosowymi.

4. Zna kryteria na to, że język nie jest bezkontekstowy.

5. Zna podstawowe algorytmy sprawdzania przynależności do języka bezkontekstowego.

6. Rozumie, jakie są uniwersalne modele obliczeniowe: maszyna Turinga i jej równoważniki (automaty wielolicznikowe, wielostosowe).

7. Potrafi udowodnić nierozstrzygalność wybranych problemów.

8. Zna definicję NP-zupełności, zna szereg problemów NP-zupełnych.

9. Rozumie pojęcie PSPACE-zupełności.

10. Ma świadomość tego, że istnieją problemy, które są rozstrzygalne ale mają astronomiczna złożoność.

Metody i kryteria oceniania:

Jedno kolokwium i egzamin pisemny.

Zajęcia w cyklu "Semestr letni 2018/19" (zakończony)

Okres: 2019-02-16 - 2019-06-08
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Szymon Toruńczyk
Prowadzący grup: Lorenzo Clemente, Filip Murlak, Radosław Piórkowski, Wojciech Rytter, Szymon Toruńczyk, Daria Walukiewicz-Chrząszcz
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr letni 2019/20" (jeszcze nie rozpoczęty)

Okres: 2020-02-17 - 2020-06-10
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Szymon Toruńczyk
Prowadzący grup: Radosław Piórkowski, Julian Salamanca Tellez, Janusz Schmude, Michał Skrzypczak, Szymon Toruńczyk, Daria Walukiewicz-Chrząszcz
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.