9600-0009/01 – Nekonvenční algoritmy a výpočty (NAV)
| Garantující katedra | IT4Innovations | Kredity | 10 |
| Garant předmětu | prof. Ing. Ivan Zelinka, Ph.D. | Garant verze předmětu | prof. Ing. Ivan Zelinka, Ph.D. |
| Úroveň studia | postgraduální | Povinnost | povinně volitelný |
| Ročník | | Semestr | zimní + letní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2015/2016 | Rok zrušení | |
| Určeno pro fakulty | FEI, USP | Určeno pro typy studia | doktorské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Cílem předmětu je seznámení jeho posluchačů s nekonvenčními algoritmy z fyzikálních, biologických procesů a komplexních systémů. Absolvent získá přehled o moderních výpočetních postupech založených na principech, odpozorovaných z komplexních dějů a dynamik. Po úspěšném absolvování kurzu bude absolvent schopen aplikovat metody probírané v kurzu na reálné problémy. Tento kurz ne volným pokračováním kurzu BIA.
Vyučovací metody
Přednášky
Individuální konzultace
Anotace
Cílem předmětu je seznámení jeho posluchačů s problematikou nekonvenčních algoritmů, jejich biologicko - fyzikálním původem. V kurzu se budou probírat jednotlivé oblasti jejich původu, obvykle z přírodních komplexních systémů s důrazem jejich matematicko-fyzikálně-algoritmický popis a následné realizace na PC. Předmět dodá posluchačům mezioborový pohled na problematiku nekonvenčních algoritmů, komplexních systémů a jejich dynamického chování. Absolvent získá přehled o moderních výpočetních postupech, umožňujících modelovat a simulovat jinak velmi složité a komplexní systémy (deterministický chaos, Thomova teorie katastrof, fraktální geometrie, hejnová inteligence, algoritmy kvantové mechaniky, buněčné automaty, ”physarium machines”, “self-organized criticality”,...). Po úspěšném absolvování kurzu bude mít absolvent interdisciplinární přehledové znalosti z oblasti nekonvenčních algoritmů a bude schopen aplikovat metody probírané v kurzu na reálné problémy. Absolvent kurzu by měl být schopen dalšího hlubšího samostudia v této problematice.
Povinná literatura:
Doporučená literatura:
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Kontrola je založena na vypracovávání protokolů předmětu, pomocí kterých student prokazuje nejen pochopení informací z přednášek, ale i schopnost jejich implementace v daném programovém prostředí. K získání zápočtu je nutno odevzdat cvičícímu všechny požadované protokoly a mít alespoň 80% fyzické účasti na laboratořích. Zápočet je podmínkou NUTNOU k připuštění ke zkoušce. Zkouška je ústní.
E-learning
Další požadavky na studenta
Je požadována schopnost tvořit programy v některém z používaných programovacích jazyků a aplikovat získané znalosti do tvorby algoritmů.
Další požadavky na studenta nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
1. Komplexita. Současný stav chápání problematiky komplexních systémů a jejich klasifikace. Synergetika. Demonstračně-motivační příklady a videa demonstrující výskyt chování komplexních systémů v každodenním reálném životě.
2. Umělé neuronové sítě (ANN), základní pojmy, principy a klasifikace. Trénovací množina, struktura a toopologie ANN. Typu učení. Separabilita.
3. Umělé neuronové sítě (ANN), Perceptron, vícevrstvý perceptron a učení metodou zpětného šíření chyby.
4. Umělé neuronové sítě (ANN), návrh topologie sítí, nekonvenční metody učení, trénovací množina a její konstrukce z dat.
5. Umělé neuronové sítě (ANN), Ukázky použití.
6. Algoritmy deterministického chaosu. Historický nástin a klasifikace dynamických systémů, generujících chaos. Jednoduché modely a ukázkové příklady. Determinismus a hrana chaosu (podle Kaufmanna).Typické chaotické systémy: Lorenzův model počasí a podivný atraktor, elektronický systém a problém tří těles (model dvojhvězda a planeta). Divergence blízkých trajektorií. Determinismus a nepředpověditelnost. Invarianty chaotického chování. Feigenbaumovy konstanty, soběpodobnost, U-sekvence, počítače a chaos. Diskrétní dynamické systémy. Základní jednoduché modely, Poincarého řezy, bifurkace, bifurkační diagram jako celostní pohled na chování systému, algoritmy a příklady. Od řádu k chaosu: cesty vedoucí k chaotickému chování. Zdvojení periody, kvaziperiodičnost, střídavost a krize. Bifurkace a Thomovy katastrofy. Algoritmizace chaotického chování a metody rekonstrukce. Využití v kryptografických technikách, řízení chaosu a jeho výskyt v ekonomických systémech
7. Thomova teorie katastrof a spojitost s chaotickým chováním. Úvod do problematiky, základní modely a hierarchie katastrof. Jejich výskyt v dynamice systémů a algoritmy identifikace podle příznaků v naměřených datech. Příklady výskytu: ekonomické systémy, fyzikální systémy, mechanické systémy.
8. Algoritmy fraktální geometrie a vizualizace komplexních struktur. IFS algoritmus. Historie, definice fraktálu, základní typy algoritmů generujících fraktály. Fraktální dimenze, interpolace a komprese.
9. Algoritmy fraktální geometrie – TEA algoritmus a Mandelbrotova množina, Juliovy množiny a jejich grafický náhled. vývojových systémů a umělý život. L-systémy, želví grafika, parametrické L-systémy, algoritmizace L-systémů z pohledu fraktální geometrie.
10. Algoritmy fraktální geometrie – výskyt v přírodě, datech, chování systémů a technice. Aplikace v grafickém designu, umění, počítačových hrách a filmu - videoukázky.
11. Algoritmy a komplexní systémy. Komplexní systémy generující efekt “self-organized criticality” (samo-organizované kritično - SOC), jejich modelování (modely typu hromada písku,...) a výskyt v reálných komplexních systémech (evoluce, zemětřesení, laviny).
12. Buněčné automaty (BA) a komplexní systémy. Formalismus BA, dynamika a klasifikace buněčných automatů podle Wolframa, Conwayova hra života, modelování pomocí BA. Buněčné automaty a časoprostorový chaos. BA a generování hudby. BA a řešení složitých problémů. Složité algoritmické chování BA na základě jednoduchých pravidel.
13. Algoritmy a komplexní sítě. Úvod do problematiky komplexních sítí, metody vizualizace a algoritmizace jejich dynamiky. Příklady výskytu komplexních sítí (sociální sítě, dynamika evolučních procesů,...). Vizualizace dynamiky komplexních sítí pomocí modelů chaotických systémů. Vizualizace dynamiky evolučních technik pomocí komplexních sítí.
Sumarizace kurzu. Vzájemné souvislosti mezi jednotlivými typy algoritmů, jejich dynamikou a chováním složitých systémů.
Cvičení (na PC učebnách):
V cvičeních bude kladen důraz na praktickou aplikaci probíraných technik a řešení vybraných vzorových problémů.
• Implementace perceptronu a jeho aplikace na jednoduchý lineárně separabilní problém.
• Implementace vícevrstvého perceptornu (včetně zpětné propagace chyby) a jeho implementace na lineárně neseparabilní problém.
• Implementace Hopfieldových sítí a jejich aplikace na jednoduché vzory
• Implementace Q-learning (Reinforcement learning) v rámci tvorby jednoduché hry.
• Aplikace neuronových sítí a Q-learningu na tzv. Pole-balancing problém
• Fraktální geometrie. Implementace L-stytémů.
• Fraktální geometrie. IFS. Implementace vybraných IFS.
• Fraktální geometrie. Využití fraktální geometrie pro tvorbu jednoduché krajiny, popř. povrchu (2D nebo 3D)
• Teorie chaosu. Logistická funkce. Aplikace neuronové sítě pro predikci čísel generovaných logistickou funkcí.
• Teorie chaosu. Chaotický pohyb. Vizualizace pohybu dvojitého kyvadla
• Buněčné automaty: Implementace (a vizualizace) požárového algoritmu (Forest-fire)
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.