« powrót do strony głównej

Matematyczne podstawy informatyki

Podstawowe informacje:

Bieżące informacje o wykładzie (np. odwołania itp.) oraz materiały do przedmiotu będą umieszczane na zespole MS Teams:

Tematy wykładów

  1. Języki formalne, wyrażenia regularne
    • Wstępnie o alfabetach, słowach i językach
    • Klasa języków regularnych
    • Wyrażenia regularne
  2. Automaty skończone
    • Automaty deterministyczne
    • Automaty niedeterministyczne
  3. Determinizacja automatu
    • Determinizacja automatu niedeterministycznego
    • Automaty z lambda-przejściami
    • Twierdzenie Kleene'ego
    • Własności języków regularnych
  4. Języki nieregularne i wstęp do języków bezkontekstowych
    • Lemat o pompowaniu dla języków regularnych
    • Gramatyki bezkontekstowe
  5. Automaty ze stosem
    • Gramatyki bezkontekstowe c.d.
    • Automaty ze stosem
    • Własności języków bezkontekstowych
  6. Maszyny Turinga
    • Definicja maszyny Turinga
    • Języki rekurencyjne i rekurencyjnie przeliczalne
  7. Maszyny Turinga c.d.
    • Maszyny wielościeżkowe i wielotaśmowe
  8. Złożoność czasowa
    • Czas działania maszyny Turinga
    • Powtórzenie
    • Kolokwium

Zaliczenie przedmiotu

Składa się z: Ocena 3.0 od 51% maksymalnej liczby podstawowych punktów. Każde kolejne 10% to pół oceny w górę.

Materiały i literatura

  1. J. Jędrzejowicz, A. Szepietowski, Języki Automaty Złożoność Obliczeniowa, Wydawnictwo Uniwersytetu Gdańskiego, Gdańsk, 2008.
  2. J. E. Hopcroft, J. D. Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979.