FI:IA012 Složitost - Informace o předmětu

IA012 Složitost

Rozsah

2/0/1. 3 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)

Garance

prof. RNDr. Ivana Černá, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

St 12:00–13:50 A318

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.

Mateřské obory/plány

• Analýza a zpracování obrazu (program FI, N-VIZ)
• Aplikovaná informatika (program FI, N-AP)
• Bezpečnost informačních technologií (angl.) (program FI, N-IN)
• Bezpečnost informačních technologií (program FI, N-IN)
• Bioinformatika a systémová biologie (program FI, N-UIZD)
• Bioinformatika (program FI, N-AP)
• Computer Games Development (program FI, N-VIZ_A)
• Computer Graphics and Visualisation (program FI, N-VIZ_A)
• Computer Networks and Communications (program FI, N-PSKB_A)
• Cybersecurity Management (program FI, N-RSSS_A)
• Diskrétní algoritmy a modely (program FI, N-TEI)
• Formální analýza počítačových systémů (program FI, N-TEI)
• Grafický design (program FI, N-VIZ)
• Graphic Design (program FI, N-VIZ_A)
• Hardware Systems (program FI, N-PSKB_A)
• Hardwarové systémy (program FI, N-PSKB)
• Image Processing and Analysis (program FI, N-VIZ_A)
• Informační bezpečnost (program FI, N-PSKB)
• Informační systémy (program FI, N-IN)
• Information Security (program FI, N-PSKB_A)
• Kvantové a jiné neklasické výpočetní modely (program FI, N-TEI)
• Paralelní a distribuované systémy (program FI, N-IN)
• Počítačová grafika a vizualizace (program FI, N-VIZ)
• Počítačová grafika (program FI, N-IN)
• Počítačové sítě a komunikace (program FI, N-IN)
• Počítačové sítě a komunikace (program FI, N-PSKB)
• Počítačové systémy (program FI, N-IN)
• Principy programovacích jazyků (program FI, N-TEI)
• Programovatelné technické struktury (angl.) (program FI, N-IN)
• Programovatelné technické struktury (program FI, N-IN)
• Řízení kyberbezpečnosti (program FI, N-RSSS)
• Řízení vývoje služeb (program FI, N-RSSS)
• Řízení vývoje softwarových systémů (program FI, N-RSSS)
• Services Development Management (program FI, N-RSSS_A)
• Služby - výzkum, řízení a inovace (angl.) (program FI, N-AP)
• Služby - výzkum, řízení a inovace (program FI, N-AP)
• Sociální informatika (program FI, B-AP)
• Software Systems Development Management (program FI, N-RSSS_A)
• Software Systems (program FI, N-PSKB_A)
• Softwarové systémy (program FI, N-PSKB)
• Strojové učení a umělá inteligence (program FI, N-UIZD)
• Teoretická informatika (program FI, N-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, N-SS) (2)
• Umělá inteligence a zpracování přirozeného jazyka (program FI, N-IN)
• Vývoj počítačových her (program FI, N-VIZ)
• Zpracování a analýza rozsáhlých dat (program FI, N-UIZD)
• Zpracování obrazu (program FI, N-AP)
• Zpracování přirozeného jazyka (program FI, N-UIZD)

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- aktivně používat pojem výpočetní složitosti problémů a algoritmů,
- analyzovat dolní a horní odhady složitosti,
- rozlišovat mezi prakticky řešitelnými a prakticky neřešitelnými problémy,
- definovat základní složitostní třídy a znát vztahy mezi nimi,
- vysvětlit pojem (NP) úplného problému a identifikovat úplné problémy složitostních tříd,
- popsat meze deterministických, nedeterministických, alternujících, pravděpodobnostnícha a paralelních výpočtů,

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

povinná literatura
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info

doporučená literatura
• ARORA, Sanjeev a Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

• Statistika zápisu (podzim 2023, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/podzim2023/IA012