Ľahké prednášky
Úvod do programovania, časová zložitosť, prefixové súčty
Prednášajúci: Marcel, Gardener
Na mojej prednáške si povieme pár slov o tom, čom vlastne to programovanie je. Ukážeme si, ako porovnávať rýchlosť algoritmov, aby sme vedeli povedať, ktorý program je rýchlejší a prečo. Tiež si zadefinujeme pojmy ako algoritmus a program.
Prerekvizity: nič
Úvod do grafov
Prednášajúci: Mirko, Filipko
Pokiaľ poznáte grafy koláčové, stĺpcové, alebo grafy funkcií, tak o nich táto prednáška nebude. Grafy v informatike sú niečo úplne iné a majú veľa aplikácií v reálnom živote. Na tejto prednáške si ukážeme, čo sú to tie informatické grafy, naučíme sa ich základnú terminológiu a prejdeme si, ako ich vieme reprezentovať v počítači a na čo ich vieme ďalej využívať.
Prerekvizity: nič
Queue, stact, deque, set, map
Prednášajúci: Robert, Oliver
Pozrieme sa na tieto dátové štruktúry, ako fungujú, kedy je použiť, a tak. Bude veľa kreslení na tabuľu. Přednáška bude česko-slovensky 😄
Prerekvizity: nič
Triedenie (sorty)
Prednášajúci: Janči, Viktor
Triedenie patrí medzi základné problémy v informatike a dá sa k nemu pristupovať najrôznejšími spôsobmi. Ukážeme si jednoduché kvadratické triedenia, ale aj najrýchlejšie rekurzívne algoritmy ako quicksort a mergesort. Vysvetlíme si, prečo sa triediť rýchlejšie nedá, a potom si ukážeme, že občas sa dá. Nakoniec sa pozrieme na to, ako v praxi triediť iné veci, než len čísla a uvedieme si aj pár zábavných príkladov toho, ako sa triediť nemá.
Prerekvizity: základy, polia, zložitosť, rekurzia
Halda
Prednášajúci: David
Halda je jednou z maximálne efektívnych implementácii abstraktného dátového typu prioritná fronta. To je typ fronty, v ktorej má každý prvok pridelenú prioritu a dokáže vykonať operácie: vloženie prvku a výber prvku s maximálnou prioritou.
Prerekvizity: základy, polia, rekurzia, strom, zložitosť
Menej stredne ťažké prednášky
Rekurzia
Prednášajúci: Robert, Viktor
Rekurzia je metóda riešenia problémov, ktorá sa využíva v situáciách, kedy riešenie problému pozostáva z menších variantov rovnakého problému.
Prerekvizity: stack
Prehľadávanie do hĺbky (DFS)
Prednášajúci: Štepi, Filipko
Pozrieme sa na to, ako prehľadávať graf, teda ak začíname v nejakom jednom vrchole, kam sa z neho vieme dostať a ako. Napríklad ako sa dostať von z bludiska.
Prerekvizity: pole, úvod do grafov
Prehľadávanie do šírky (BFS)
Prednášajúci: Štepi, Kika
Ukážeme si, ako nájsť cestu medzi dvoma vrcholmi v grafe (napríklad navigácia, keď graf je mapa ciest), ale nie len tak hocijakú, ale tú najkratšiu.
Prerekvizity: pole, úvod do grafov
Binárne vyhľadávanie
Prednášajúci: Mirko
Predstavte si že hráte s kamarátom hru “Hádaj na aké číslo myslím”. My si ukážeme, ako toto číslo uhádnuť na najmenší možný počet pokusov. Použijeme pri tom algoritmus, ktorý sa volá binárne vyhľadávanie a ukážeme si, že ho môžeme použiť aj na rýchle vyhľadávanie v utriedenom poli.
Prerekvizity: Polia (list v Py / vector v C++)
Dijkstra
Prednášajúci: Skaloš
Predstavme si hádam najjednoduchší a najznámejší grafový problém - hľadanie najkratšej cesty z bodu A do bodu B. Pokiaľ nemajú všetky hrany rovnakú dĺžku, nemôžeme použiť klasické BFS, potrebujete niečo sofistikovanejšie. A tým niečím je Dijkstrov algoritmus, ktorý používa haldu, aby pre každý vrchol vedel rozhodnúť, kedy sme doň už najkratšiu cestu našli, a vieme pokračovať v hľadaní ďalej z neho.
Prerekvizity: grafy, BFS, halda
Teória čísel
Prednášajúci: Stanko
V programovaní sa občas stretneme s problematikou prvočísel a deliteľnosti, respektíve po nás môže nejaká úloha požadovať, aby sme namiesto priameho výsledku vypočítali jeho zvyšok po delení nejakým číslom. Ukážeme si, ako so zvyškami počítať rýchlejšie, ako s celými číslami, a povieme si nejaké užitočné pravdy o nich, ako napríklad malú Fermatovu a Čínsku Zvyškovú vetu.
Prerekvizity: nič
Viac stredne ťažké prednášky
Bruteforce
Prednášajúci: Merlin
Existuje však jeden spôsob riešenia, ktorý zaručene poskytne správne výsledky pre akúkoľvek úlohu. Nazýva sa riešenie hrubou silou a.k.a. Bruteforce. Porozprávame sa čo to je, ako to funguje, aké to má výhody a nevýhody.
Prerekvizity: rekurzia, DFS, BFS
Zametanie
Prednášajúci: Marcel
Zametanie je technika používaná predovšetkým pri úlohách, v ktorých pracujeme s intervalmi či bodmi alebo útvarmi v rovine. Hlavná myšlienka je, že prechádzame významné body zľava doprava a postupne ich spracúvame, čo nám umožní efektívne spracovať všetky body. Na prednáške si vysvetlíme, ako to funguje a ako sa to dá využiť.
Prerekvizity: polia, triedenie
Dynamika
Prednášajúci: Sabinka
Dynamické programovanie je metóda, ktorá umožňuje efektívne riešiť mnohé algoritmické úlohy. Podstata takéhoto algoritmu je, že vypočítame výsledok pre časť vstupu, a z nej potom ľahko vypočítame výsledok pre celý vstup. Na tejto prednáške si prejdeme základy použitia dynamiky a akú dynamiku presne použiť pri akej úlohe.
Prerekvizity: rekurzia
Binárny vyhľadávací strom
Prednášajúci: Emmika
Na tejto prednáške si vysvetlíme, ako vyrobiť a použiť jednoduchú dátovú štruktúru – binárny vyhľadávací strom – na rýchle vkladanie, hľadanie a mazanie záznamov, a ďalšie užitočné operácie. Ukážeme si jej princípy a výhody, ale aj nevýhody a povieme si v skratke o možnostiach, ako tieto nevýhody odstrániť takzvaným vyvažovaním.
Prerekvizity: základy, stromy
Trie
Prednášajúci: fezjo
Trie, alebo písmenkový strom, je dátová štruktúra, ktorá nám umožňuje efektívne ukladať množinu reťazcov alebo údaje indexované reťazcami. Ukážeme si, ako trie funguje, ako ho implementovať a použiť na riešenie nejakých úloh.
Prerekvizity: stromy, stromová dátová štruktúra
Geometria, konvexný obal
Prednášajúci: fezjo
Naučíme sa základné techniky z geometrie, vektorový súčin, obsah mnohouholníka. Pozrieme sa na problém konvexného obalu, laicky, máme N bodov v rovine, a chceme nájsť najkratší plot ktorý ich obkolesí.
Prerekvizity: nič
Floyd-Warshall
Prednášajúci: Emmika
Zrejme ste už počuli o hľadaní najkratších ciest v ohodnotených (ováhovaných grafoch) - dijkstrovom algoritme. Tento algoritmus má ale pomerne veľký problém - nevie hľadať najkratšie cesty v grafov, ktoré obsahujú záporné hrany. Na tejto prednáške sa pozrieme na to, že prečo je to vlastne problém, a povieme si ako funguje floyd-warshallov algoritmus, ktorý vie hľadať najkratšie cesty aj v takýchto grafoch.
Prerekvizity: grafy, BFS, DFS, Dijkstra
Kostry a union-find
Prednášajúci: Stanko
Povieme si o tom, čo je to kostra grafu, teda nejaký taký výber hrán v grafe, že v tomto výbere vedie nejaká cesta z každého vrcholu do každého. Ukážeme si 2 algoritmy na hľadanie najlacnejšej kostry - takej, že súčet vybraných hrán bude minimálny. Jeden z algoritmov využíva dátovú štruktúru union-find, ktorú sa tiež naučíme.
Prerekvizity: grafy, rekurzia, halda (ale prežijeme aj bez)
Ťažké prednášky
Rolling hash
Prednášajúci: Maťo
Naučíme sa ako pomocou hashovania efektívne riešiť rôzne úlohy s reťazcami. Napríklad zistiť, koľkokrát sa nachádza zadaný reťazec v nejakom inom zadanom reťazci ako podreťazec, niečo podobné v 2D (nájsť zadaný obdĺžnik písmen v tabuľke písmen), alebo ako nájsť najdlhší palindróm v reťazci.
Prerekvizity: počítanie so zvyškom, prefixové súčty
Materiály: https://www.ksp.sk/kucharka/prefixove_sumy/
Silno-súvislé komponenty
Prednášajúci: Kubo
V usmernenom grafe sa môžu nachádzať skupiny vrcholov také, že z každého vrchola v nej existuje cesta do každého iného. To ale znamená, že vrcholy v takejto skupine sa v mnohých smeroch správajú rovnako, čo nám môže zjednodušiť riešenie mnohých problémov.
Prerekvizity: grafy, DFS
KMP
Prednášajúci: David
TBA
Prerekvizity: TBA
Párenie
Prednášajúci: Eliška
Pre každého vedúceho máme zoznam jedál, ktoré majú radi. Ale Merlin nezvládol nákup a z každého jedla máme len jeden kus. Koľko vedúcich zostane hladných a naštvaných na Merlina?
Prerekvizity: grafy, DFS
Materiály: https://www.ksp.sk/kucharka/parenie/, http://www.dcs.fmph.uniba.sk/~anderle/tea/parenie.pdf
Mosty a artikulácie
Prednášajúci: Viktor
Naučíme sa, čo sú mosty a artikulácie v grafoch (hrana, resp. vrchol, ktorý ak by sme odstránili, graf by sa nám rozpadol na viac komponentov). Ukážeme si, ako efektívne hľadať takýto vrchol / hranu v grafe. Algoritmus bude vychádzať z algoritmu prehľadávania do hĺbky - DFS.
Prerekvizity: grafy, myšlienka DFS
Intervalový strom
Prednášajúci: Gardener
Naučíme sa ako dynamicky zisťovať súčet alebo maximum intervalov v poli, ktoré sa nám mení za behu.
Prerekvizity: pole
Treap
Prednášajúci: fezjo
TBA
Prerekvizity: TBA
Lowest common ancestor (LCA)
Prednášajúci: fezjo
Lowest common ancestor - čo to je, ako to vieme rýchlo spočítať. Na čo je to dobré?
Prerekvizity: binárne vyhľadávanie, zakorenený strom, DFS
Čas poslednej úpravy: 8. júl 2024 21:46