|
|
Hlavní nabídka Prohlížení IS/STAG
Nalezené předměty, počet: 1
Stránkování výsledků vyhledávání
Nalezeno 1 záznamů
Export do Xls
Informace o předmětu
KMA / AVS
:
Popis předmětu
Pracoviště / Zkratka
|
KMA
/
AVS
|
Akademický rok
|
2023/2024
|
Akademický rok
|
2023/2024
|
Název
|
Algoritmy a výpočetní složitost
|
Způsob zakončení
|
Zkouška
|
Způsob zakončení
|
Zkouška
|
Akreditováno / Kredity
|
Ano,
5
Kred.
|
Forma zakončení
|
-
|
Forma zakončení
|
-
|
Rozsah hodin
|
Přednáška
3
[HOD/TYD]
Cvičení
1
[HOD/TYD]
|
Zápočet před zkouškou
|
Ano
|
Zápočet před zkouškou
|
Ano
|
Automatické uznávání zápočtu před zkouškou
|
Ne
|
Počítán do průměru
|
ANO
|
Vyučovací jazyk
|
-
|
Obs/max
|
|
|
|
Automatické uznávání zápočtu před zkouškou
|
Ne
|
Letní semestr
|
1 / -
|
1 / -
|
0 / -
|
Počítán do průměru
|
ANO
|
Zimní semestr
|
0 / -
|
0 / -
|
0 / -
|
Opakovaný zápis
|
NE
|
Opakovaný zápis
|
NE
|
Rozvrh
|
Ano
|
Vyučovaný semestr
|
Zimní + Letní
|
Vyučovaný semestr
|
Zimní + Letní
|
Minimum (B + C) studentů
|
1
|
Volně zapisovatelný předmět |
Ano
|
Volně zapisovatelný předmět
|
Ano
|
Vyučovací jazyk
|
-
|
Počet dnů praxe
|
0
|
Počet hodin kontaktní výuky |
|
Hodnotící stupnice |
1|2|3|4 |
Periodicita |
každý rok
|
Hodnotící stupnice pro zp. před zk. |
S|N |
Periodicita upřesnění |
|
Základní teoretický předmět |
Ne
|
Profilující předmět |
Ne
|
Základní teoretický předmět |
Ne
|
Hodnotící stupnice |
1|2|3|4 |
Hodnotící stupnice pro zp. před zk. |
S|N |
Nahrazovaný předmět
|
Žádný
|
Vyloučené předměty
|
Nejsou definovány
|
Podmiňující předměty
|
Nejsou definovány
|
Předměty informativně doporučené
|
KMA/TGD1
|
Předměty,které předmět podmiňuje
|
KMA/DM, KMA/DMI, KMA/TIS
|
Graf četnosti udělených hodnocení studentům napříč roky:
Obrázek PNG
,
XLS
|
Cíle předmětu (anotace):
|
Cílem předmětu je poskytnout hlubší přehled o třídách výpočetní složitosti a jejich vzájemných vztazích založený na výpočetním modelu Turingova stroje.
|
Požadavky na studenta
|
Zápočet: semestrální práce.
Zkouška: ústní část.
Garantem předmětu je stanoveno, že zápočet se při opakovaném zapsání
neuznává (viz čl. 24, odst. 3 SZŘ ZČU).
|
Obsah
|
1. Jazyky. Reducibilita. Výpočetní modely. Gramatiky.
2. Turingovy stroje. Míry výpočetní složitosti.
3. Třídy časové složitosti. Třída P.
4. Třída NP. Struktura třídy NP.
5. Parametrizovaná složitost.
6. Neuniformní výpočetní složitost.
7. Výpočetní složitost optimalizačních úloh. Aproximovatelnost.
8. Booleovská a polynomiální hierarchie.
9. Třídy paměťové složitosti.
10. Pravděpodobnostní algoritmy a třídy složitosti.
11. Interaktivní důkazové systémy. PCP třídy.
12. Paralelní výpočetní složitost.
13. Složitost logických teorií. Základy Kolmogorovy teorie složitosti.
14. Kvantové výpočty.
|
Aktivity
|
|
Studijní opory
|
|
Garanti a vyučující
|
|
Literatura
|
-
Základní:
Papadimitriou. Computational Complexity. 1995.
-
Základní:
Bovet, D.P.; Crescenzi, P. Introduction to the theory of complexity. Prentice Hall International Series in Computer Science, 2004. ISBN 978-0139153808.
-
Základní:
Sipser, Michael. Introduction to the theory of computation. 2nd ed. Boston : Thomson Course Technology, 2006. ISBN 0-534-95097-3.
-
Základní:
Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989.
-
Rozšiřující:
Fiat, Woeginger (eds.). Online Algorithms. 1998.
-
Rozšiřující:
Williamson, D.P.; Shmoys, D.B. The Design of Approximation Algorithms. Cambridge University Press, 2011. ISBN 978-0521195270.
-
Doporučená:
Hromkovič, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. 2nd ed. Berlin : Springer, 2003. ISBN 3-540-44134-4.
-
Doporučená:
Sedgewick, Robert; Flajolet, Philippe. An introduction to the analysis of algorithms. Boston : Addison-Wesley, 1996. ISBN 0-201-40009-X.
-
Doporučená:
Vazirani, V.V. Approximation Algorithms. Springer International Publishing AG, part of Springer Nature, 2013. ISBN 978-8181283856.
-
Doporučená:
Rothe, J. Complexity Theory and Cryptology. Springer-Verlag Berlin Heidelberg, 2005. ISBN 978-3-642-06054-0.
-
On-line katalogy knihoven
|
Časová náročnost
|
Všechny formy studia
|
Aktivity
|
Časová náročnost aktivity [h]
|
Kontaktní výuka
|
52
|
Příprava na souhrnný test [6-30]
|
35
|
Příprava na zkoušku [10-60]
|
56
|
Celkem
|
143
|
|
Předpoklady
|
Odborné znalosti - pro úspěšné zvládnutí předmětu se předpokládá, že je student před zahájením výuky schopen: |
popsat výpočetní model počítače s libovolným přístupem (RAM) |
formulovat základní polynomiálně řešitelné úlohy |
formulovat základní úlohy řešitelné nedeterministicky v polynomiálním čase |
Odborné dovednosti - pro úspěšné zvládnutí předmětu se předpokládá, že student před zahájením výuky dokáže: |
aplikovat algoritmy pro základní polynomiálně řešitelné úlohy |
vyřešit jednoduchou úlohu lineárního programování |
Obecné způsobilosti - před zahájením studia předmětu je student schopen: |
bc. studium: kriticky přistupuje ke zdrojům informací, informace tvořivě zpracovává a využívá při svém studiu a praxi, |
mgr. studium: samostatně a odpovědně se na základě rámcového zadání rozhodují v souvislostech jen částečně známých, |
bc. studium: rozpozná problém, objasní jeho podstatu, rozčlení ho na části, |
|
Výsledky učení
|
Odborné znalosti - po absolvování předmětu prokazuje student znalosti: |
definovat složitostní třídy optimalizačních úloh |
popsat pravděpodobnostní třídy výpočetní složitosti |
popsat výpočetní model Turingova stroje |
vysvětlit aproximační algoritmy pro standardní úlohy |
Odborné dovednosti - po absolvování předmětu prokazuje student dovednosti: |
odhadnout výpočetní složitost dané úlohy |
odhadnout aproximovatelnost dané optimalizační úlohy |
navrhnout jednoduchý pravděpodobnostní algoritmus pro danou úlohu |
Obecné způsobilosti - po absolvování předmětu je student schopen: |
mgr. studium: srozumitelně a přesvědčivě sdělují odborníkům i širší veřejnosti vlastní odborné názory, |
bc. studium: samostatně a odpovědně se na základě rámcového zadání rozhodují v souvislostech jen částečně známých, |
|
Hodnoticí metody
|
Odborné znalosti - odborné znalosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Ústní zkouška, |
Test, |
Individuální prezentace, |
Odborné dovednosti - odborné dovednosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Demonstrace dovedností (praktická činnost), |
Obecné způsobilosti - obecné způsobilosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Ústní zkouška, |
|
Vyučovací metody
|
Odborné znalosti - pro dosažení odborných znalostí jsou užívány vyučovací metody: |
Přednáška založená na výkladu, |
Přednáška s aktivizací studentů, |
Cvičení (praktické činnosti), |
Odborné dovednosti - pro dosažení odborných dovedností jsou užívány vyučovací metody: |
Cvičení (praktické činnosti), |
Obecné způsobilosti - pro dosažení obecných způsobilostí jsou užívány vyučovací metody: |
Přednáška s aktivizací studentů, |
|
|
|
|