« powrót do strony głównej

Obliczalność i złożoność - ćwiczenia


Punkty i wyniki Studenta.
Dane do logowania jak do Sigmy. Podczas pierwszego logowania należy zapisać się do odpowiedniej grupy.

Uwaga! Sprawdzian z obliczalności odbędzie się w dniu 21.01.2018 r. o godz. 12:15 w sali 210.

Zajęcia:

Temat
  1. Języki regularne i automaty skończone.
  2. Lemat o pompowaniu dla języków regularnych. Języki bezkontekstowe.
  3. Automaty ze stosem. Maszyna Turinga
  4. Złożoność czasowa dla maszyn Turinga.
  5. Niedeterministyczne maszyny Turinga.
  6. Problemy NP-zupełne.
  7. Problemy NP-zupełne i redukcje.
  8. Problemy nierozstrzygalne.
  9. Sprawdzian (21.01.2017)
    • Lista zagadnień - podane na tablicy podczas zajęć.
    • Uwaga! Sprawdzian odbędzie się o godz. 12:15 w sali 210.

Zaliczenie przedmiotu:

Na zaliczenie przedmiotu składają się:
Zaliczenie od 50% maksymalnej ilości punktów. Nie ma popraw sprawdzianów ani wejściówek. Osoby, które na koniec semestru nie będą miały wystarczającej ilości punktów będą pisały poprawę zbiorczą podczas egzaminu.

Materiały:

  1. J. Jędrzejowicz, A. Szepietowski, Języki, automaty, złożoność obliczeniowa, Wydawnictwo Uniwersytetu Gdańskiego, Gdańsk, 2008.
  2. Strona wykładowcy: dr hab. Joanna Jędrzejowicz, prof. UG.