Podstawy teorii obliczalności

Znajomość podstawowych pojęć algorytmiki (Podstawy programowania oraz Algorytmy i struktury danych) oraz podstaw matematyki współczesnej (Matematyka dla informatyków I oraz II)

przedmiot obligatoryjny

30h – wykłady klasyczne

5h – wykłady zdalne

2h – egzamin

30h – ćwiczenia klasyczne

15h – projekt wykonywany zdalnie

60h – pracy własnej (ćwiczenia), rozwiązywanie zadań zadanych przez prowadzącego zajęcia

60h – studia literatury (wykład)

20h – przygotowanie do egzaminu

RAZEM: 222 godziny

8 punktów ECTS

Po ukończeniu kursu student osiąga następujące efekty (kody odnoszą się do efektów dla studiów 1 stopnia na kierunku informatyka - studia inżynierskie):

(W1) ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie problematyki obliczalności, języków formalnych i automatów (K_W02)

(W2) ma pogłębioną wiedzę teoretyczną w zakresie złożoności obliczeniowej (K_W04)

Po ukończeniu kursu student osiąga następujące efekty (kody odnoszą się do efektów dla studiów 1 stopnia na kierunku informatyka - studia inżynierskie):

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

(U2) potrafi pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, (K_U02)

(U3) potrafi analizować pod kątem poprawności i złożoności obliczeniowej problemy i algorytmy (K_U07)

Po ukończeniu kursu student osiąga następujące efekty (kody odnoszą się do efektów dla studiów 1 stopnia na kierunku informatyka - studia inżynierskie):

(K1) Jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegół; jest systematyczny (K_K04)

(K2) Jest nastawiony na nieustanne zdobywanie nowej wiedzy, umiejętności i doświadczeń; rozumie potrzebę ciągłego doskonalenia się i podnoszenia kompetencji zawodowych (K_K06)

Jest to klasyczny przedmiot z zakresu informatyki teoretycznej – z wykładem zawierającym precyzyjne dowody przedstawianych faktów oraz ćwiczeniami mającymi na celu głębsze zrozumienie omawianych pojęć.

• Metody dydaktyczne podające:

o wykład informacyjny (konwencjonalny)

• Metody dydaktyczne poszukujące:

o ćwiczeniowa

o referatu

- wykład informacyjny (konwencjonalny)

- ćwiczeniowa
- projektu

- metody ewaluacyjne

Celem przedmiotu jest przedstawienie podstawowych zagadnień teorii języków formalnych, teorii obliczalności oraz teorii złożoności obliczeniowej

1. Języki regularne i bezkontekstowe

1.1 Wyrażenia regularne, automaty jako akceptory jezyków

1.2 Twierdzenie Kleene’ego

1.3 Klasyfikacja gramatyk Chomsky’ego

1.4 Parsery dla gramatyk bezkontekstowych (algorytm CYK)

2. Różne definicje obliczalności

2.1 Funkcje obliczalne wg Kleene’ego

2.2 Maszyna Turinga

2.3 Maszyna licznikowa.

2.4 Hipoteza Churcha

3. Problemy nierozstrzygalne - przykłady

3.1 Problem stopu dla maszyn Turinga

3.2 Przykłady funkcji nierekurencyjnych

3.3 Twierdzenie Rice’a

3.4 Problem odpowiedniości Posta

3.5 X problem Hilberta

4. Złożoność obliczeniowa, przykłady problemów o różnej złożoności

4.1 Skala złożoności

4.2 P = NP ?

1) Wprowadzenie do teorii obliczeń, M. Sipser

2) Wprowadzenie do teorii automatów języków i obliczeń, J.E.Hopcroft, J.D. Ullman

3) Złożoność obliczeniowa, Ch. H. Papadimitriou

4) Skrypty UMK do wykładów i ćwiczeń z przedmiotów Teoria Języków Formalnych oraz Teoria Obliczalności (K. Barylska, Ł. Mikulski, M. Piątkowski)

5) Wykłady zdalne dostępne na platformie Moodle kursu

Zaliczenie ćwiczeń na ocenę oraz egzamin.

Ćwiczenia zaliczane na ocenę na podstawie dwóch kolokwiów

• kolokwium 1 – języki regularne i bezkontekstowe (W1, U1);

• kolokwium 2 – obliczalność, rozstrzygalność i złożoność obliczeniowa (W1+W2, U1 + U3);

• projekt związany ze skanerami i parserami (W1, U2, K1+K2).

Egzamin pisemny (W1+W2, U1+U3, K1).

nie dotyczy