Uniwersytet Marii Curie-Skłodowskiej w Lublinie - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Wstęp do teorii obliczalności

Informacje ogólne

Kod przedmiotu: MFI-I.2Z.093 Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Wstęp do teorii obliczalności
Jednostka: Instytut Informatyki
Grupy:
Strona przedmiotu: https://teams.microsoft.com/l/meetup-join/19%3a9b47a18a30a14ec0a0cb61f8a91c6b63%40thread.tacv2/1603119421623?context=%7b%22Tid%22%3a%2280dbd34a-9b20-490b-ac49-035af103ab2b%22%2c%22Oid%22%3a%22c6b122b0-76e5-467d-b6cb-1e6f475bcd4c%22%7d
Punkty ECTS i inne: 0 LUB 4.00 LUB 3.00 (zmienne w czasie)
zobacz reguły punktacji
Język prowadzenia: polski
Wymagania wstępne:

Podstawowe umiejętności programistyczne

Godzinowe ekwiwalenty punktów ECTS:

Zajęcia w obecności prowadzącego - 30h

Konsultacje dla studenta - 30h

Razem 2.2 p. ETCS


Czas poświęcony na pracę indywidualną studenta potrzebną do owocnego udziału w zajęciach - 30h

Czas wymagany do przygotowania się i do uczestnictwa w sprawdzianach - 20h

Razem 1.8 ETCS


suma 110h = 4 punkty ETCS

Sposób weryfikacji efektów kształcenia:

Zaliczenia pisemne - efekty W01, W02

Zaliczenie ustne -efekty W01, W02

Odpowiedzi ustne - efekty W01, W02, U01, U02

Aktywność - efekty U01, U02

Pełny opis:

Celem wykładu jest zapoznanie studentów z podstawami teorii obliczalności, a w szczególności z wybranymi matematycznymi modelami obliczeń oraz z przykładami problemów nierozwiązywalnych w tych modelach.

W trakcie laboratoriów studenci mają nabyć umiejętność sprawnego posługiwania się pojęciami poznanymi na wykładzie (w tym przeprowadzania prostych dowodów matematycznych z zakresu teorii obliczalności).

Spis zagadnień:

1. Maszyna Turinga

2. Funkcje obliczalne (rekursja i minimalizacja)

3. Zbiory i relacje rekurencyjne

4. Zbiory rekurencyjnie przeliczalne

5. Uniwersalność

6. Hierarchia arytmetyczna

7. Stopnie Turinga

Literatura:

Literatura podstawowa:

1. Michael Sipser, Wprowadzenie do teorii obliczeń. WNT, Warszawa 2009

2. Jerzy Mycka, Elementy teorii obliczalnosci, Instytut Informatyki UMCS, Lublin, 2011

Literatura uzupełniająca.

3. Maria Foryś, Wit Foryś, Adam Roman,Języki, automaty, obliczenia, http://wazniak.mimuw.edu.pl/index.php?title=J%C4%99zyki%2C_automaty_i_obliczenia

Efekty uczenia się:

W01 - zna podstawowe narzędzia matematyki potrzebne do analizy obliczeniowej problemów informatycznych - K_U09. K_W09, K_W10

W02 - zna teoretyczne podstawy informatyki - K_W04, K_W05, K_W10

U01 - potrafi uzasadniać i dowodzić podstawowe własności systemów obliczeniowych - K_K02, K_K05, K_K07, K_U13

U02 - potrafi uzasadnić podstawowe teoretyczne wyniki dotyczące rozstrzygalności i uniwersalności obliczeń - K_W9, K_U09. K_U13

Zajęcia w cyklu "Semestr zimowy 2019/2020" (zakończony)

Okres: 2019-10-01 - 2020-02-01
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin więcej informacji
Wykład, 15 godzin więcej informacji
Koordynatorzy: Jerzy Mycka
Prowadzący grup: Krzysztof Borzęcki, Jerzy Mycka
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Zaliczenie na ocenę
Laboratorium - Zaliczenie na ocenę
Wykład - Zaliczenie na ocenę

Zajęcia w cyklu "Semestr zimowy 2020/2021" (w trakcie)

Okres: 2020-10-01 - 2021-02-01
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin więcej informacji
Wykład, 15 godzin więcej informacji
Koordynatorzy: Jerzy Mycka
Prowadzący grup: Krzysztof Borzęcki, Jerzy Mycka
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Zaliczenie na ocenę
Laboratorium - Zaliczenie na ocenę
Wykład - Zaliczenie na ocenę
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Marii Curie-Skłodowskiej w Lublinie.