Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Teoria algorytmów i obliczeń
Koordynator przedmiotu:
dr hab. inż. Władysław Homenda
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
7 / rok ak. 2011/2012
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
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Wstęp do lingwistyki matematycznej i teorii automatów Algorytmy i struktury danych
Limit liczby studentów:
Cel przedmiotu:
Modele obliczeń i ich przykłady (maszyny Turinga, maszyny RAM) równoważność modeli obliczeń, podstawy teorii funkcji rekurencyjnych, równoważność modeli obliczeń i klas funkcji rekurencyjnych, podstawowe pojęcia teorii złożoności, charakteryzacji przestrzeni problemów ze względu na złożoność algorytmów rozwiązywania problemów
Treści kształcenia:
Program wykładu: A. 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.. B) 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. C) 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:
Literatura:
Hopcroft J.E. Ullman J.D., Wprowadzenie do teorii automatów, języków i obliczeń, WNT Homenda W., Elementy lingwistyki matematycznej i teorii automatów, WPW Papadimitriou C. H., Złożonośćc obliczeniowa, WNT, Warszawa Hennie F., Introduction to computability, Addison-Wesley
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się