Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (ISBN 83-204-2659-6)
J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 1994 (ISBN 83-01-11298-0)
T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)
H. Barendregt, E. Barendsen, Introduction to Lambda Calculus, 1994
Additional literature:
Note that there are many good scripts online, especially in German (Vorlesungsskript, Theoretische Informatik)
Requirements:
There is a final exam for this course.
In order to pass the course it is necessary to
pass the final written exam,
totally get at least 40% of points (this miniml numebr can be slightly lowered)
the points from the exam will be recalculated so that it will be possible to get 0-50% points for the exam and
0-50% point for the problem classes.
Exam:
The written exam will check understanding, skills and ability of problem solving.
It will consist of short problems that will demand certain creativity and careful thinking.
It is not necessary to remember details of algorithms, classes, theorems ...
but it will be necessary to understand them well.
Usually, the details which are hard to remember, will be recalled on the
question sheet. It will be allowed to bring own notices, books, ... etc.
E-books and all electornic media are strictly forbidden.
Problem classes:
Reguły ustalone przez prowadzącego ćwiczenia:
Zasadniczym celem ćwiczeń jest ułatwienie studentom samodzielnej pracy nad opanowaniem materiału w czasie całego semestru.
Ocena z ćwiczeń jest oceną jakości i intensywności pracy studenta w czasie semestru.
Wykładowca ogłasza z wyprzedzeniem listy zadań do samodzielnego rozwiązania przed zajęciami.
Na ćwiczeniach studenci prezentują rozwiązania zadań. W trakcie rozwiązywania wyjaśniane są wątpliwości
dotyczące rozwiązania oraz przedstawiane alternatywne rozwiązania.
Podstawą do wystawienia oceny są wyniki krótkich sprawdzianów.
Sprawdziany będą polegały na rozwiązaniu jednego zadania i punktowane od 0 do 5.
Materiałem obowiązującym na sprawdzianie są 3 poprzednie listy. Sprawdziany przeprowadzane są regularnie i bez uprzedniej zapowiedzi.
Nieobecność na sprawdzianie daje 0. Jeden, najsłabszy sprawdzian studenta w semestrze zostanie anulowany.
Podstawą do oceny na zaliczenie jest średnia ze sprawdzianów zaokrąglona w górę do najbliższej oceny.
Ocena może być podwyższona przez prowadzącego w zależności od aktywności studenta na ćwiczeniach.
Na każde ćwiczenia jest przygotowywana osobna lista zadań, ogłaszana co najmniej na trzy dni przed zajęciami (wyjątek - pierwsze zajęcia)
Na ćwiczeniach rozwiązywane są wybrane zadania z tej listy. Decyzja odnośnie wyboru zadań do rozwiązania podejmuje prowadzący ćwiczenia.
Dodatkowym warunkiem zaliczenia jest oddanie przez studenta w formie pisemnej (PDF) wyznaczonych zadań z list.
Oddawane zadanie powinno być rozwiązane dokładnie, w sposób formalny i przejrzysty. Zadanie wyznacza prowadzący ćwiczenia.
Ocena nie podlega poprawianiu po zakończeniu zajęć poza przypadkami wymienionymi w Regulaminie Studiów.
Main goals:
better understanding of limitations due to inherent complexity of computational problems