| Název předmětu | Vybraná témata z algoritmů |
|---|---|
| Kód předmětu | KMI/VYTAL |
| Organizační forma výuky | Seminář |
| Úroveň předmětu | Bakalářský |
| Rok studia | nespecifikován |
| Semestr | Letní |
| Počet ECTS kreditů | 3 |
| Vyučovací jazyk | Čeština |
| Statut předmětu | Povinně-volitelný |
| Způsob výuky | Kontaktní |
| Studijní praxe | Nejedná se o pracovní stáž |
| Doporučené volitelné součásti programu | Není |
| Vyučující |
|---|
|
| Obsah předmětu |
|
- Problém splnitelnosti formulí výrokové logiky (SAT), jeho obtížnost, aplikace a teoretický význam. - Rezoluce, věta o rezoluci, algoritmy odvozené od rezoluce, dolní omezení délky rezolučního zamítnutí. - Varianty řešitelné v polynomickém čase. - Rodina algoritmů založená na DPLL, hlavní myšlenky CDCL solverů. - Paturi-Pudlák-Zane algoritmus - Kombinatorické úvahy o splnitelnosti.
|
| Studijní aktivity a metody výuky |
| Metody práce s textem (učebnicí, knihou), Demonstrace, Laborování |
| Výstupy z učení |
|
Cílem je studenty seznámit s důležitým algoritmickým problémem, algoritmy pro jeho řešení, jejich implementačními aspekty a příslušnými teoretickými partiemi. Jako modelový problém je zvolena splnitelnost formulí výrokové logiky.
|
| Předpoklady |
|
nespecifikováno
|
| Hodnoticí metody a kritéria |
|
Analýza výkonů studenta, Rozbor produktů pracovní činnosti studenta (technické práce)
Aktivní účast na hodině. Plnění úkolů. |
| Doporučená literatura |
|
| Studijní plány, ve kterých se předmět nachází |
| Fakulta | Studijní plán (Verze) | Kategorie studijního oboru/specializace | Doporučený semestr | |
|---|---|---|---|---|
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Informatika - specializace Programování a vývoj software (2021) | Kategorie: Informatické obory | 2 | Doporučený ročník:2, Doporučený semestr: Letní |
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Informatika (2020) | Kategorie: Informatické obory | 2 | Doporučený ročník:2, Doporučený semestr: Letní |
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Informatika - specializace Obecná informatika (2021) | Kategorie: Informatické obory | 2 | Doporučený ročník:2, Doporučený semestr: Letní |