Uniwersytet Marii Curie-Skłodowskiej w Lublinie - Centralny System Uwierzytelniania
Strona główna

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: 3.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
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 2p. 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 - 10h

Razem 1 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_W01, K_W01, K_W02

W02 - zna teoretyczne podstawy informatyki - K_W01, K_W01, K_W02

U01 - potrafi uzasadniać i dowodzić podstawowe własności systemów obliczeniowych - K_K01, K_W01, K_W01, K_W02, K_U01, K_U02

U02 - potrafi uzasadnić podstawowe teoretyczne wyniki dotyczące rozstrzygalności i uniwersalności obliczeń - K_W01, k_U01

Zajęcia w cyklu "Semestr zimowy 2024/2025" (zakończony)

Okres: 2024-10-01 - 2025-02-03
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 15 godzin więcej informacji
Wykład, 15 godzin więcej informacji
Koordynatorzy: Jerzy Mycka
Prowadzący grup: Piotr Kosela, Jerzy Mycka, Aneta Wróblewska
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.
kontakt deklaracja dostępności mapa serwisu USOSweb 7.1.2.0