Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Teoria algorytmów i obliczeń
Koordynator przedmiotu:
Prof. dr hab. inż. Władysław Homenda, Dr Michał Tuczyński
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka i Systemy Informacyjne
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-IN000-ISP-0474
Semestr nominalny:
7 / rok ak. 2020/2021
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia15h
  • Laboratorium15h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Teoria automatów i języków formalnych Algorytmy i struktury danych
Limit liczby studentów:
Ćwiczenia – 30 os/grupa Laboratoria (ćwiczenia komputerowe) – 15-24 os/grupa
Cel przedmiotu:
Celem przedmiotu jest przekazanie wiedzy z teorii algorytmów, złożoności, rozstrzygalności, charakteryzacji klas problemów. Po ukończeniu kursu studenci powinni posiadać wiedzę i umiejętności sformułowane w tabeli efektów uczenia się.
Treści kształcenia:
Wykład: Rozstrzygalność problemów: Języki rekurencyjne, rekurencyjnie przeliczalne i nierekurencyjne, problemy rozstrzygalne, częściowo rozstrzygalne i nierozstrzygalne. Modele obliczeń: maszyny Turinga, maszyny RAM. Równoważność modeli obliczeń. Teoria funkcji rekursywnych: rekursja pierwotna, operacja minimum efektywnego, funkcje pierwotnie rekursywne, rekurencyjne i rekurencyjnie przeliczalne. Obliczalność i częściowa obliczalność w sensie Turinga. Hipoteza Churcha. Złożoność algorytmów: Złożoność czasowa algorytmów. Klasy problemów: P, QL, NQL, NPI, NP, co-NP. Twierdzenie Cooka. Równoważność modeli obliczeń w sensie złożoności czasowej. Złożoność pamięciowa algorytmów. Klasy problemów DLOG, POLYLOG, P. Twierdzenie Sawitcha. Przykłady problemów. Ćwiczenia: Rozwiązywanie zadań dotyczących zagadnień prezentowanych na wykładzie. Laboratorium: Rozwiązywanie problemów NP-zupełnych za pomocą algorytmów dokładnych i aproksymacyjnych.
Metody oceny:
Do zaliczenia przedmiotu wymagane jest: - zaliczenie części teoretycznej i praktycznej w bieżącym semestrze, - zaliczenie części teoretycznej na podstawie dwóch kolokwiów, - zaliczenie części laboratoryjnej na podstawie rozwiązania przydzielonego problemu w czasie semestru; wymagana jest obecność na zajęciach laboratoryjnych w celu kontroli realizacji zdania laboratoryjnego, - ocena końcowa jest średnią z części teoretycznej i praktycznej.
Egzamin:
nie
Literatura:
1. J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT. 2. A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Company. 3. W. Homenda, Elementy lingwistyki matematycznej i teorii automatów, WPW. 4. P.B. Bovet, P. Crescenzi, Introduction to the theory of complexity, Prentice Hall. 5. M.B. Moret, The theory of computation, Addison-Wesley Publishing Company. 6. C.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa. 7. A. Yasuhara, Recursive function theory and logic, Academic Press. 8. F. Hennie, Introduction to computability, Addison-Wesley.
Witryna www przedmiotu:
e.mini.pw.edu.pl
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka W01
Zna teoretyczne modele obliczeniowe: maszyny Turinga, gramatyki nieograniczone, maszyny RAM, funkcje rekurencyjne, jest świadomy uniwersalności modeli obliczeń i pojęcia obliczalności
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny
Powiązane charakterystyki kierunkowe: K_W01, K_W07
Powiązane charakterystyki obszarowe:
Charakterystyka W02
Zna podstawowe pojęcia teorii obliczalności: rozstrzygalność, częściowa rozstrzygalność, komplementarność częściowej rozstrzygalności, nierozstrzygalność
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny
Powiązane charakterystyki kierunkowe: K_W04, K_W08
Powiązane charakterystyki obszarowe:
Charakterystyka W03
Zna podstawowe pojęcia teorii złożoności: problemy jako przeliczalne zbiory zadań, algorytmy i ich złożoność, sposoby określania rozmiarów zadań, kryteria wyznaczania złożoności, równoważność klas problemów, języków i funkcji naturalnych
Weryfikacja: sprawdzian pisemny
Powiązane charakterystyki kierunkowe: K_W04, K_W08, K_W10
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - umiejętności

Charakterystyka U01
Potrafi podać i uzasadnić charakterystykę przestrzeni problemów ze względu na ich rozstrzygalność, potrafi uzasadnić jakościową równoważność wybranych modeli obliczeń
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny, ocena rozwiązania problemu w ramach laboratorium
Powiązane charakterystyki kierunkowe: K_U04, K_U05, K_U08, K_U14, K_U01, K_U02
Powiązane charakterystyki obszarowe:
Charakterystyka U02
Potrafi skonstruować algorytmy rozwiązania prostych problemów w różnych modelach obliczeń, potrafi uzasadnić jakościową równoważność modeli obliczeniowych, potrafi uzasadnić ilościową równoważność wybranych modeli obliczeń
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny,
Powiązane charakterystyki kierunkowe: K_U01, K_U02, K_U04, K_U09, K_U11
Powiązane charakterystyki obszarowe:
Charakterystyka U03
Potrafi podać i uzasadnić charakterystykę przestrzeni problemów rozstrzygalnych ze względu na złożoność algorytmów rozwiązania problemów: klasy P, NP, coNP, NPC, Pspace, NPspace, relacje między tymi klasami
Weryfikacja: sprawdzian pisemny, ocena rozwiązania problemu w ramach laboratorium
Powiązane charakterystyki kierunkowe: K_U01, K_U09, K_U11, K_U14, K_U23
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka K01
Jest w stanie w sposób prosty wyjaśnić podstawowe zagadnienia teorii obliczalności, praktyczne ograniczenia metod obliczeniowych i teoretyczne granice obliczalności
Weryfikacja: udział w dyskusji
Powiązane charakterystyki kierunkowe: K_K01, K_K02, K_K04, K_K05
Powiązane charakterystyki obszarowe: