Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Teoria złożoności
Koordynator przedmiotu:
dr inż. Paweł Rzążewski
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Matematyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
.
Semestr nominalny:
4 / rok ak. 2022/2023
Liczba punktów ECTS:
3
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1. godziny kontaktowe – 50 h; w tym a) obecność na wykładach – 30 h b) obecność na ćwiczeniach –15 h c) konsultacje – 5 h 2. praca własna studenta – 30 h; w tym a) przygotowanie do ćwiczeń i do kolokwium – 25 h b) zapoznanie się z literaturą – 5 h Razem 80 h, co odpowiada 3 pkt. ECTS
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 15 h c) konsultacje – 5 h Razem 50 h, co odpowiada 2 pkt. ECTS
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:
Teoria Automatów i Języków Formalnych
Limit liczby studentów:
Bez limitu
Cel przedmiotu:
Celem przedmiotu jest zapoznanie studentów z podstawami teorii złożoności, takimi jak pojęcie (efektywnej) obliczalności, klasy problemów P, NP i pokrewne
Treści kształcenia:
1. Maszyna Turinga, niedeterminizm 2. Nierozstrzygalność, maszyny Turinga z i bez własności stopu 3. Klasy problemów P i NP 4. Twierdzenie Cooka-Levina, NP-zupełność 5. Redukowalność problemów obliczeniowych 6. ETH i redukcje wielomianowe 7. Inne modele obliczeniowe: RAM, rachunek lambda 8. Złożoność obliczeniowa w teorii liczb i kryptografii 9. Randomizacja 10. Złożoność pamięciowa 11. Sposoby radzenia sobie z problemami trudnymi obliczeniowo
Metody oceny:
Podstawą zaliczenia jest aktywność na ćwiczeniach i test zaliczeniowy pisany na ostatnich zajęciach. Za aktywność można uzyskać 10 punktów, są one przyznawane za rozwiązywanie zadań podczas zajęć i za prace domowe. Za test zaliczeniowy można uzyskać 40 punktów.
Egzamin:
nie
Literatura:
1. Avi Widgerson, Mathematics and Computation, Princeton University Press, 2019, dostępne na stronie autora: https://www.math.ias.edu/avi/book 2. Sanjeev Arora, Boaz Barak: Computational Complexity - A Modern Approach. Cambridge University Press 2009, dostępne na stronie : http://theory.cs.princeton.edu/complexity/ 3. M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, 4. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015, dostępne na stronie : http://parameterized-algorithms.mimuw.edu.pl/
Witryna www przedmiotu:
brak
Uwagi:
.

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka WCB_W01
Zna podstawowe modele obliczeń i klasy problemów obliczeniowych
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: M2MCB_W08
Powiązane charakterystyki obszarowe:
Charakterystyka WCB_W02
Zna założenia teorii złożoności, na których opiera się bezpieczeństwo współczesnych protokołów kryptograficznych
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: M2MCB_W08
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - umiejętności

Charakterystyka WCB_U01
Potrafi przeprowadzić redukcję między dwoma problemami obliczeniowymi.
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: M2MCB_U15
Powiązane charakterystyki obszarowe:
Charakterystyka WCB_U02
Potrafi rozpoznać klasyczne problemy trudne obliczeniowo
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: M2MCB_U15
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka WCB_K01
Potrafi szukać informacji w literaturze fachowej
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: M2MCB_K02
Powiązane charakterystyki obszarowe: