Podstawy teorii obliczalności
1000-ZiPTO
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 ?
Całkowity nakład pracy studenta
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
Efekty uczenia się - wiedza
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)
Efekty uczenia się - umiejętności
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)
Efekty uczenia się - kompetencje społeczne
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)
Metody dydaktyczne
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
Metody dydaktyczne podające
- wykład informacyjny (konwencjonalny)
Metody dydaktyczne poszukujące
- ćwiczeniowa
- projektu
Metody dydaktyczne w kształceniu online
- metody ewaluacyjne
Rodzaj przedmiotu
przedmiot obligatoryjny
Wymagania wstępne
Znajomość podstawowych pojęć algorytmiki (Podstawy programowania oraz Algorytmy i struktury danych) oraz podstaw matematyki współczesnej (Matematyka dla informatyków I oraz II)
Koordynatorzy przedmiotu
Kryteria oceniania
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).
Praktyki zawodowe
Literatura
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
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i
terminach zajęć) mogą być dostępne w serwisie USOSweb: