Teoria obliczalności

Podstawowe wiadomości z zakresu matematyki i informatyki obejmujące teorię zbiorów, matematykę dyskretną, teorię języków formalnych, teorię algorytmów oraz programowanie.

przedmiot obowiązkowy

30h - wykład,

30h - ćwiczenia,

50h - praca własna - bieżące przygotowanie do zajęć, studiowanie literatury

35h - praca własna - przygotowanie do egzaminu

5h - zaliczenie ćwiczeń i egzamin

Razem 150h,

6pkt. ECTS

Student

W1: ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie teorii obliczalności (KW_02). W szczególności zna i rozumie:

* uniwersalne modele obliczeń

* maszyny licznikowe

* maszyny Turinga

* pojęcie rozstrzygalności i częściowej rozstrzygalności

* przykłady rozstrzygalnych, nierozstrzygalnych oraz częściowo rozstrzygalnych problemów w informatyce

* pojęcie złożoności obliczeniowej algorytmu (czasowej i pamięciowej)

* klasy złożoności obliczeniowej i relacje między nimi

* pojęcie trudności i zupełności problemów obliczeniowych

* przykłady trudnych i zupełnych problemów obliczeniowych

W2: zna podstawowe metody projektowania i analizowania algorytmów (projektowanie strukturalne, rekurencja, złożoność obliczeniowa) (KW_04)

Student potrafi:

U1: potrafi wykorzystać wiedzę matematyczną oraz informatyczną do formułowania, analizowania i rozwiązywania problemów obliczeniowych (KU_01), w szczególności:

w szczególności

* odróżniać problemy rozstrzygalne i częściowo rozstrzygalne od nierozstrzygalnych

* dowodzić obliczalność, rozstrzygalność oraz częściową rozstrzygalność typowych problemów matematycznych

* dowodzić trudność i zupełność problemów obliczeniowych przez sprowadzenie do znanych problemów obliczeniowych

U2: potrafi projektować oraz analizować rozwiązania problemów obliczeniowych pod kątem ich poprawności i złożoności obliczeniowej (KU_07)

U3: potrafi pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie; (KU_02)

Student:

KK1: skutecznie przekazuje innym swoje myśli w zrozumiały sposób (KK_02)

KK2: właściwie posługuje się terminologią fachową (KK_02)

KK3: potrafi nawiązać kontakt w obrębie swojej dziedziny i z osobą reprezentującą inną dziedzinę (KK_02)

KK4: rozumie potrzebę ciągłego uczenia się i doskonalenia swoich umiejętności (KK_03)

- wykład informacyjny (konwencjonalny)

Przedmiot dla studiów I stopnia na kierunku informatyka. Jego celem jest: prezentacja formalizacji pojęcia obliczalności, omówienie podstawowych problemów nierozstrzygalnych w informatyce (stopu, wejścia, wyjścia, itp.) i matematyce (X problemu Hilberta, itp.) oraz przedstawienie podstawowych wyników teorii złożoności obliczeniowej.

W ramach przedmiotu omawiane będą m.in. następujące zagadnienia:

1. Obliczalność – pojęcia podstawowe
2. Maszyny licznikowe
3. Funkcje częściowo rekurencyjne
4. Maszyny Turinga
5. Pojęcie rozstrzygalności, częściowej rozstrzygalności oraz nierozstrzygalności problemów obliczeniowych
6. Przykłady problemów rozstrzygalnych, częściowo rozstrzygalnych oraz nierozstrzygalnych
7. Czasowa i pamięciowa złożoność obliczeniowa
8. Problemy trudne i zupełne

• Michael Sipser Wprowadzenie do teorii obliczeń
• Antonii Kościelski Teoria obliczeń. Wykłady z matematycznych podstaw informatyki
• Christos H. Papadimitriou Złożoność obliczeniowa
• David Harel Rzecz o istocie informatyki: algorytmika
• John E. Hopcroft, Jeffrey D. Ullman Wprowadzenie do teorii automatów, języków i obliczeń

Laboratorium: kolokwia pisemne

Wykład: egzamin pisemny