Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Języki, automaty i obliczenia

Informacje ogólne

Kod przedmiotu: 1000-214bJAO
Kod Erasmus / ISCED: 11.302 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Języki, automaty i obliczenia
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Przedmioty obowiązkowe dla II roku informatyki
Przedmioty obowiązkowe dla II roku JSIM - wariant 3I+4M
Przedmioty obowiązkowe dla II roku JSIM - wariant 3M+4I
Punkty ECTS i inne: 5.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

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 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ę:

Wiedza - absolwent zna i rozumie:

- podstawy teorii języków formalnych (języki, wyrażenia regularne, gramatyki) i formalnych modeli obliczeniowych (automaty, automaty ze stosem, maszyny Turinga) (K_W12)

Umiejętności - absolwent potrafi:

- zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania związanych z informatyką zadań (K_U01),

- pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie (K_U02),

- samodzielnie planować i realizować własne uczenie się przez całe życie (K_U09),

- definiować języki formalne z pomocą gramatyk i automatów oraz operować abstrakcyjnymi modelami obliczeń ze szczególnym uwzględnieniem maszyn Turinga (K_U11),

Kompetencje społeczne - absolwent jest gotów do:

- uznawania znaczenia wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz wyszukiwania informacji w literaturze oraz zasięgania opinii ekspertów (K_K03)

Metody i kryteria oceniania:

* 4 zadania domowe po 5 pkt każde.

* 8 testów domowych łącznie za 8 pkt.

* egzamin końcowy za ~30 pkt.

* zadania z gwiazdką pozwalające zdobyć dodatkowe punkty.

By być dopuszczonym do egzaminu w pierwszym terminie, wymagane jest przynajmniej 14 pkt (próg ten może zostać opuszczony).

Ostateczna ocena w pierwszym terminie to 1/10 sumy uzyskanych punktów (z zaokrągleniem w dół do 0.5).

Egzamin w drugim terminie będzie skutkował oceną ostateczną (bez wpływu uzyskanych wcześniej punktów j.w.).

Zajęcia w cyklu "Semestr letni 2023/24" (w trakcie)

Okres: 2024-02-19 - 2024-06-16
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Sławomir Lasota
Prowadzący grup: Tomasz Gogacz, Łukasz Kamiński, Sławomir Lasota, Filip Mazowiecki, Paweł Parys, Michał Skrzypczak, Jerzy Tyszkiewicz, 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.
Krakowskie Przedmieście 26/28
00-927 Warszawa
tel: +48 22 55 20 000 https://uw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)