Uniwersytet Jagielloński w Krakowie - Centralny System Uwierzytelniania
Strona główna

Teoria Programowania

Informacje ogólne

Kod przedmiotu: WMI.TCS.TP.OM
Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Teoria Programowania
Jednostka: Instytut Informatyki Analitycznej
Grupy:
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
zobacz reguły punktacji
Język prowadzenia: polski

Zajęcia w cyklu "Semestr letni 2023/2024" (w trakcie)

Okres: 2024-02-26 - 2024-06-16
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Marek Zaionc
Prowadzący grup: Katarzyna Grygiel, Marek Zaionc
Strona przedmiotu: https://marekzaionc.staff.tcs.uj.edu.pl//STUDENCI/
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Efekty kształcenia:

Student zna klasę funkcji i predykatów pierwotnie rekurencyjnych, kwantyfikatory ograniczone oraz ograniczony μ operator.


Student zna pojęcia obliczalności wyrażalnej przez strukturalne języki programowania, schematy blokowe, rachunek lambda.


Student potrafi dowodzić nierozstrzygalność problemów; zna dowody nierozstrzygalności. problemu stopu, problemu Posta, pustości języka


Student zna twierdzenia Rice’a dotyczące języków rekurencyjnych i języków rekurencyjnie przeliczalnych


Student zna podstawowe twierdzenia dotyczące rekursji, np. twierdzenie o eliminacji rekursji prostej, o formie normalnej rekursji, o punkcie stałym rekursji.


Student umie wykorzystać w rozumowaniu maszyny z wyrocznią, zna hierarchię nierozstrzygalności.


Student potrafi w sposób zrozumiały przedstawić poprawne rozumowanie matematyczne; potrafi formułować twierdzenia i wnioski
Forma i warunki zaliczenia:

ZALICZENIE: Warunkiem otrzymania zaliczenia z ćwiczeń jest uzyskanie więcej niż 50 punktów łącznie za kolokwium i za aktywność na ćwiczeniach. W ramach aktywności będą oceniane zadania do rozwiązania (45%) jak i prezentacja referatu (15%). 40% będzie przyznawane za ocenę z kolokwium. Kolokwium wspólne odbędzie się w poniedziałek 5 czerwca 2024 w terminie wykładu.


EGZAMIN: Warunkiem przystąpienia do egzaminu jest otrzymanie pozytywnego (3.0 lub więcej) zaliczenia z ćwiczeń. Egzamin ustny odbędzie się w dniach 17-19 czerwca 2024 od godziny 10 do 18. Ocena końcowa jest średnią z odpowiedzi egzaminacyjnej i oceny z zaliczenia.


EGZAMIN POPRAWKOWY: Studenci którzy nie zdali egzaminu lub nie otrzymali zaliczenia z ćwiczeń będą mogli przystąpić do egzaminu poprawkowego. Egzamin poprawkowy odbędzie się około 2 września 2024.


Skala ocen: od 0 do 50 niedostateczny, od 51 do 60 dostateczny, od 61 do 70 dostateczny+, od 71 do 80 dobry, od 81 do 90 dobry+, od 91 do 100 bardzo dobry.
Metody dydaktyczne:

tradycyjny wykład tablicowy
Sylabus przedmiotu dla studentów rozpoczynających studia od roku akademickiego 19/20 lub później:

Informatyka analityczna, studia stacjonarne drugiego stopnia, rok 1
Pełny opis:

1. Predykaty z klasy PRec są zamknięte na operacje logiczne i kwantyfikatory ograniczone

2. Twierdzenie o eliminacji rekursji prostej

3. Klasa Prec jest najmniejsza klasa zawierąjacą funkcje inicjujące oraz kodowanie i dekodowanie par zamknięta na złożenia i iteracje.

4. Twierdzenie o rekursji z historia

5.

6. Twierdzenie o eliminacji rekursji prostej.

7. Twierdzenie o formie normalnej rekursji.

8. Obliczalność przez wyrażalność w rachunku lambda.

9. Języki rekurencyjne i rekurencyjnie przeliczalne

10. Język przekatniowy L_d.

11. Nierozstrzygalność problemu stopu, język LHP .

12. Nierozstrzygalność problemu pustości języka, języki L_e i L_ne.

13. Nierozstrzygalność problemu Posta.

14. Problem rekurencyjności i nierekurencyjności, języki L_r i L_ne.

15. Twierdzenie Ricea o językach rekurencyjnych.

16. Twierdzenie Ricea o językach rekurencyjnie przeliczalnych.

17. Twierdzenie S_{m,n}.

18. Maszyny z wyroczną, hierarchia.

19. L_u ≈ L_e

20. {< M >:L(M) = Σ∗} jest rekurencyjny ze względu na S_2

21. Twierdzenie o punkcie stałym rekursji.

22. Przykłady formuł prawdziwych w Ar i niewywiedlnych w Q.

23. Funkcje z klasy Rec są reprezentowalne w Q.

24. Twierdzenie o diagonalizacji.

25.

26. Jeżeli teoria T jest niesprzecznym rozszerzeniem Q to zbiór numerów G¨odela twierdzeń T nie jest w T definiowalny.

27. Żadne niesprzeczne rozszerzenie Q nie jest rozstrzygalne.

28. Rachunek predykatów nie jest rozstrzygalny.

29. Arytmetyka nie jest rozstrzygalna.

30.

31. Każda aksjomatyzowalna i zupełna teoria jest rozstrzygalna.

32. Twierdzenie G¨odela o niezupełności.
Literatura:

J.H. Hopcroft, J.D. Ullman "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley 1979

G. Boolos, R. Jeffrey "Computability and Logic", Cambridge Univ. Press, 1980

Jako uzupełnienie zalecam ciekawy artykuł Piergiorgio Odifreddi, Godel for Children, zawierający dowód twierdzenia Godela. Dostęp przez stronę https://marekzaionc.staff.tcs.uj.edu.pl/STUDENCI/
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Jagielloński w Krakowie.
ul. Gołębia 24, 31-007 Kraków https://www.uj.edu.pl kontakt deklaracja dostępności USOSweb 7.0.3.0 usosweb12b