Złożoność obliczeniowa
Informacje ogólne
Kod przedmiotu: | 1000-716ZOB |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | Złożoność obliczeniowa |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obieralne dla II-III roku bioinformatyki |
Punkty ECTS i inne: |
6.00
|
Język prowadzenia: | polski |
Skrócony opis: | |
Pełny opis: |
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ść. |
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. |
Efekty uczenia się: |
(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 |
Metody i 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. |
Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)
Okres: | 2023-10-01 - 2024-01-28 |
Przejdź do planu
PN WT WYK
CW
ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Paweł Urzyczyn | |
Prowadzący grup: | Paweł Urzyczyn | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "Semestr zimowy 2024/25" (w trakcie)
Okres: | 2024-10-01 - 2025-01-26 |
Przejdź do planu
PN WYK
WT ŚR CW
CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Paweł Urzyczyn | |
Prowadzący grup: | Adam Cicherski, Paweł Urzyczyn | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin | |
Uwagi: |
Wykład odbywa się zdalnie, a ćwiczenia stacjonarnie. |
Właścicielem praw autorskich jest Uniwersytet Warszawski.