Oferta dydaktyczna Instytutu Informatyki

Poniższa lista przedstawia przedmioty, które są uczone w Instytucie Informatyki, niektóre z nich co roku, niektóre z mniejszą częstotliwością Każdy student Instytutu Informatyki studiuje wg indywidualnego toku studiów, wybierając (zgodnie z pewnymi zasadami) z tej listy swoje przedmioty.

Jeżeli zastanawiasz się nad studiami u nas, jeżeli chcesz wiedzieć, czy na Uniwersytecie można zostać inżynierem, jeżeli interesuje Cię 1000 zł stypendium miesięcznie - zapraszamy na naszą stronę główną

Języki formalne i złożoność obliczeniowa

Nazwa angielska (title in English):
Prowadzący (lecturer): Jerzy Marcinkowski
Liczba punktów (ECTS): 9
Liczba punktów 2007 (ECTS since 2007): 9
Rodzaj (type): obowiązkowy
Rodzaj od 2007 (type since 2007): obowiązkowy.O3
Liczba godzin (hours in semester):
wykład:60
ćwiczenia:30
repetytorium:30
Egzamin (exam): tak
Możliwe zajęcia w języku angielskim (can be taught in English): nie
Przedmiot zostal uaktualniony na biezacy rok (updated): tak
Semestr (semester): letni

Wymagania (prerequisites)

Program (program)

  1. Wyrażenia i języki regularne. Automaty skończone, równoważność deterministycznych automatów skończonych, niedeterministycznych automatów skończonych i wyrażeń regularnych. (4 godz.)
  2. Lemat o pompowaniu. Twierdzenie Myhilla-Nerode'a i minimalizacja automatu. (4 godz.)
  3. Gramatyki i języki bezkontekstowe. Postać normalna Greibach i Chomsky'ego. #Automaty ze stosem. Równoważność gramatyk bezkontekstowych i automatów ze stosem. (10 godz.)
  4. Lemat o pompowaniu i lemat Ogdena. (4 godz.)
  5. Języki deterministyczne i jednoznaczne. (4 godz.)
  6. Teoretyczne modele maszyn obliczających. Modele obliczeń sekwencyjnych: maszyna Turinga i jej modyfikacje, RAM. Niedeterministyczna maszyna Turinga. #Przykładowe symulacje pomiędzy różnymi modelami. Definicja Kleene'go. Teza Churcha. (6 godz.)
  7. Pojęcie zbioru rekurencyjnego i rekurencyjnie przeliczalnego. Kodowanie i numeracja maszyn Turinga, maszyna uniwersalna. Nierozstrzygalność problemu stopu. Inne przykłady problemów nierozstrzygalnych. Twierdzenie Rice'a. (4 godz.)
  8. Nierozstrzygalność problemów Posta i problemu słów w półgrupie. Informacja o nierozstrzygalności arytmetyki. (4 godz.)
  9. Czasowa i pamięciowa złożoność obliczeniowa dla modelu maszyny Turinga. #Zależności pomiędzy nimi. Pojęcie klasy złożoności i najważniejsze przykłady (LOGSPACE, NLOGSPACE, PTIME, UP, NP, PSPACE, EXPTIME). Przykład problemu wymagającego wykładniczego czasu i pamięci. (8 godz.)
  10. NP-zupełność, sens pojęcia, przykłady, tw. Cooka, redukcje pomiędzy problemami, hipoteza P¹ NP. (6 godz.)
  11. Zagadnienie złożoności dla modeli równoległych, klasa PSPACE jako pułap złożoności dla obliczeń równoległych w czasie wielomianowym, informacja o klasie NC, jej podklasach i strukturze. (4 godz.)

Literatura (references)

Jeżeli jesteś zainteresowany studiowaniem w naszym instytucie, zapraszamy na stronę poświęconą tegorocznej rekrutacji.

Nazwa użytkownika (user name):
Hasło (password):