Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Teoria algorytmów i obliczeń
Koordynator przedmiotu:
Dr hab. inż. Władysław Homenda, prof. PW
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-0042
Semestr nominalny:
7 / rok ak. 2019/2020
Liczba punktów ECTS:
7
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 kształcenia.
Treści kształcenia:
Program wykładu: 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. Program ćwiczeń: Rozwiązywanie zadań dotyczących zagadnień prezentowanych na wykładzie. Program 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 końcowej pracy pisemnej. 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.
Egzamin:
nie
Literatura:
1. J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT 2. W. Homenda, Elementy lingwistyki matematycznej i teorii automatów, WPW 3. C.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 4. 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
Powiązane charakterystyki kierunkowe: K_U01, K_U02, K_U04, K_U05, K_U08, K_U14
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_U02, K_U04, K_U09, K_U11, K_U01
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, przygotowanie rozwiązanie problemu z hierarchii złożoności (opis problemu, sformułowanie, dowód poprawności i analiza złożoności obliczeniowej algorytmów rozwiązania problemu, przygotowanie programu)
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, K_K07
Powiązane charakterystyki obszarowe: