Złożoność obliczeniowa 1000-716ZOB
Treści kształcenia:
Języki formalne, teoria obliczeń (problemy nierozstrzygalne), teoria złożoności (problemy NP. zupełne), algorytmy aproksymacyjne, algorytmy randomizowane, równoległość.
Koordynatorzy przedmiotu
Efekty kształcenia
(KW_01) ma pogłębioną wiedzę z działów matematyki niezbędnych do studiowania bioinformatyki
(KW_02) dobrze rozumie rolę i znaczenie konstrukcji rozumowań
matematycznych
(K_U01) posiada umiejętność konstruowania rozumowań matematycznych
(K_U02) potrafi wyrażać problemy obliczeniowe w języku matematyki
(K_U04) projektuje algorytmy w podstawowych modelach
maszynach Turinga, obwodach logicznych
(K_U05) identyfikuje przynależność i trudność problemów obliczeniowych w stosunku do ważnych klas złożoności: NC, P, NP, PSPACE,
wykorzystując ich różne charakteryzacje
Kryteria oceniania
Egz. pisemny
Do egzaminu zerowego mogą przystąpić osoby, które zaliczyły prace domowe i zgłosiły gotowość do egzaminu najpóźniej 7 stycznia.
Literatura
* Sipser, M., Wprowadzenie do teorii obliczeń. WNT 2009.
* Harel, D., Feldman, Y., Rzecz o istocie informatyki: Algorytmika. wyd. 4., WNT 2008.
* Papadimitriou, Ch. H., Złożoność obliczeniowa. WNT 2002.
Uwagi
|
W cyklu 2024Z:
Wykład odbywa się zdalnie, a ćwiczenia stacjonarnie. |
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: