Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorithms and Computability
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:
brak
Semestr nominalny:
7 / rok ak. 2009/2010
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:
1. Algorithms and Data Structures 2. Automata Theory and Languages
Limit liczby studentów:
Cel przedmiotu:
To provide students basic knowledge of complexity theory and computability.
Treści kształcenia:
1) Decidability: Recursive and recursively enumerable languages, decidable, partially decidable and undecidable problems. Models of computation: Turing machine, RAM machines. Equivalence of computation models. Recursive function theory; bounded and unbounded minimum, primitive recursive, recursive and recursively enumerable functions. Turing computability. Church hypothesis. 2) Complexity: Time complexity of algorithms. Classes P, QL, NQL, NPI, NP, co-NP, NP-complete problems. Examples of NP. problems. Cook theorem. Complexity equivalence of computation models. Memory complexity of algorithms. Classes DLOG, POLYLOG, P, Sawitch theorem.
Metody oceny:
Passing the subject requires: ? solving a given problem and preparing documentation in the semester time ? 40 points. Presence at laboratory hours will be claimed to control progress of problem solving, ? getting a pass of introductory test (basic notions of complexity), ? getting a pass of a final written test (end of semester) - 60 points. Grades: D for less than 51 points, C for 51-60, C+ for 61-70, B for 71-80, B+ for 81-90, 5 for 91 and more points
Egzamin:
Literatura:
1. Hopcroft J.E. Ullman J.D., Introduction to automata theory, languages and computation, 2. Hennie F.C., Introduction to Computability 3. Davis M. Computability
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się