Prednášky

---

Zoznam prednášok postupne aktualizujeme a dopĺňame!

Ľahké prednášky

Úvod do programovania a efektívnosť programov

Kedy: 1. týždeň pondelok; 2. týždeň pondelok
Prednášajúci: Dávid

Úvodná prednáška určená pre každého, kto v minulosti neriešil Olympiádu v informatike ani žiadne iné súťaže v programovaní.

Prerekvizity: Základná znalosť niektorého programovacieho jazyka (Python, C, Pascal, Java)
Úlohy na testovači: Úvod do programovania

Úvod do teórie grafov

Kedy: 1. týždeň utorok; 2. týždeň utorok
Prednášajúci: emmika

Zavedieme si základné pojmy s grafmi v informatike a vysvetlíme si čo to ten graf vlastne je. Ukážeme si ako reprezentovať graf v počítači. A asi aj nejaké príklady zo života, kto vie.

Prerekvizity: Polia (list v Pythone, vector v C++)
Úlohy na testovači: Úvod do grafov

Rekurzia

Kedy: 1. týždeň streda
Prednášajúci: Robert G.

Prejdeme základnú myšlienku rekurzívnych algoritmov. Pozrieme sa, ako sa pozerať na problém pomocou metódy "rozdeľuj a panuj".

Prerekvizity: funkcie, základy
Úlohy na testovači: Rekurzia

Queue, stack, deque, set, map

Kedy: 1. týždeň štvrtok; 2. týždeň streda
Prednášajúci: Robert G.; Marcel

Pozrieme sa na základné dátové štruktúry v Pythone s tým, že si rozmyslíme, na čo sú vhodné a prečo sú niektoré rýchlejšie.

Prerekvizity: základy, polia
Úlohy na testovači: Dátové štruktúry - queue, Dátové štruktúry - stack, Dátové štruktúry - deque, Dátové štruktúry - set a map

Halda

Kedy: 1. týždeň piatok
Prednášajúci: Janka

Na konkrétnych príkladoch si predstavíme haldu ako dátovú štruktúru. Vysvetlíme si, prečo funguje a kedy sa nám oplatí ju použiť. V rámci ukážky implementácie si vyriešime jednoduchú úlohu.

Prerekvizity: polia, rekurzia
Úlohy na testovači: Dátové štruktúry – halda

Floyd-Warshall

Kedy: 2. týždeň štvrtok
Prednášajúci: Marcel

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, djikstra
Úlohy na testovači: Grafy - Floyd-Warshall

Menej stredne ťažké prednášky

Brute force

Kedy: 1. týždeň utorok
Prednášajúci: danza

Ak nevieme vyriešiť úlohu efektívne, môže byť dobrý nápad vyriešiť ju aspoň hrubou silou. Tento prístup nás často privedie aj ku optimálnemu riešeniu. Okrem toho je hrubá sila najlepším spôsobom ktorý pre niektoré problémy poznáme. S programovaním riešení hrubou silou sa stretávame veľmi často, je preto vhodné poznať štandardné prístupy ku implementácií týchto riešení. Tieto spôsoby zahŕňajú skúšanie všetkých podmnožín, všetkých podmnožín veľkosti k, všetkých permutácií. Podľa úrovne publika si možno ukážeme aj backtracking a techniku známu pod názvom meet in the middle.

Prerekvizity: Úvod do programovania
Úlohy na testovači: Prístupy - brute force

Prehľadávanie do šírky (BFS)

Kedy: 1. týždeň streda; 2. týždeň streda
Prednášajúci: Naďka

Ukážeme si jeden zo spôsobov prehľadávania grafov. Ukážeme ako sa pomocou BFS dajú vyhľadávať najkratšie cesty v grafe. Povieme si, v akých ďalších prípadoch sa BFS používa.

Prerekvizity: pole, úvod do grafov
Úlohy na testovači: Grafy - BFS

Sort

Kedy: 1. týždeň štvrtok
Prednášajúci: Aďo

Určite ste už niekedy potrebovali utriediť nejaké pole čísel. Ak ste doteraz používali nejaký pomalý vlastný algoritmus alebo funkciu sort, o ktorej ani netušíte ako funguje, je toto prednáška pre vás! Najprv si ukážeme princíp na jednoduchých algoritmoch a pozrieme sa na to, prečo su pomalé. Postupne prejdeme k algorimom, ktoré to dokážu oveľa rýchlejšie.

Prerekvizity: pole, rekurzia
Úlohy na testovači: Algoritmy - triedenie

Binárny vyhľadávací strom

Kedy: 1. týždeň piatok
Prednášajúci: Gardener

BVS je špeciálny druh stromu, vďaka ktorému dokážeme rýchlo vyhľadávať hodnoty. Ukážeme si ako funguje, kedy nefunguje a na čo sa v praxi používa.

Prerekvizity: Polia (list v Py / vector v C++), úvod do grafov
Úlohy na testovači: Dátové štruktúry - binárne vyhľadávacie stromy

Viac stredne ťažké prednášky

Binárne vyhľadávanie

Kedy: 1. týždeň utorok
Prednášajúci: Kika

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žujeme 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
Úlohy na testovači: Algoritmy - Binárne vyhľadávanie

Zametanie

Kedy: 1. týždeň streda; 2. týždeň štvrtok
Prednášajúci: Michal S.

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: triedenie, základy geometrie
Úlohy na testovači: Prístupy - zametanie

Prehľadávanie do hĺbky (DFS)

Kedy: 1. týždeň štvrtok
Prednášajúci: Gardener

Ukážeme si jeden zo spôsobov, akým sa dajú v grafe vyhľadávať vrcholy. Porovnáme s BFS a povieme si, v akých prípadoch sa DFS používa.

Prerekvizity: Polia (list v Py / vector v C++), úvod do grafov, rekurzia
Úlohy na testovači: Grafy - DFS

Geometria, konvexný obal

Kedy: 1. týždeň piatok
Prednášajúci: Jano

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: --
Úlohy na testovači: Geometria

Intervalový strom

Kedy: 2. týždeň pondelok
Prednášajúci: Hodobox

Skúsime vyriešiť úlohu s intervalmi, a po neúspešnom riešení základnými technikami sa dopracujeme k dátovej štruktúre intervalový strom. Vysvetlíme si ako funguje, čo sa s ňou dá robiť, a ako ju naimplementovať. Plnohodnotne si naprogramujeme riešenie danej úlohy. Bonus content podľa zvyšného času.

Prerekvizity: Treba ovládať rekurziu. Žiadne ďalšie hard prerequisites, ale je to stredná++ prednáška; dobré je napr. byť na úrovni zvládnutia haldy, stacku, a iných jednoduchších štruktúr.
Úlohy na testovači: Dátové štruktúry - intervalové stromy Materiály: https://www.ksp.sk/kucharka/intervalovy_strom/

Ťažké prednášky

Rolling hash

Kedy: 1. týždeň utorok; 2. týždeň utorok
Prednášajúci: Jaro

Povieme si, čo je to hashovacia funkcia, pozrieme sa na rôzne príklady hashovacích funkcií a povieme si aké vlastnosti vyžadujeme od hashovacej funckie. Potom sa pozrieme na rôzne úlohy, ako napríklad hľadanie slova v texte, a povieme si, ako ich riešiť efektívnejšie pomocou hashovania.

Prerekvizity: Prefixové súčty
Úlohy na testovači: Prefixy v zozname, Playlist (sekcia Stringy) Materiály: https://www.ksp.sk/kucharka/prefixove_sumy/

Odmocninová dekompozícia

Kedy: 1. týždeň streda
Prednášajúci: Jaro

V tejto prednáške sa pozrieme na to, ako rozdelením pola na menšie kúsky vieme urýchliť operácie, ako hľadanie súčtu ľubovolného intervalu, podobne ako pri prefixových súčtoch. Odmocninová dekompozícia nám však dáva väčšiu flexibilitu než prefixové súčty, lebo funguje aj na mnohé iné operácie než sčítavanie, a dovoľuje nám aj efektívne meniť pole za behu, zatiaľ čo pri prefixových súčtoch sa pole už nemôže meniť.

Prerekvizity: Prefixové súčty
Úlohy na testovači: Dátové štruktúry - intervalové stromy

Dynamika

Kedy: 1. týždeň štvrtok
Prednášajúci: Naďka

Bežným spôsobom riešenia problému je jeho rozbitie na jednoduchšie podproblémy a riešenie týchto podproblémov. Každý podproblém sa možno dá rozbiť na ďalšie podproblémy. Často sa ale môže stať, že ten istý podproblém sa nám objaví na viacerých miestach. Ukážeme si techniku, ktorou sa vieme vyhnúť opakovanému riešeniu rovnakých podproblémov, známu aj ako dynamické programovanie. Táto technika je vhodná na riešenie extrémne širokej škály rôznych problémov a jej znalosť vie byť často nápomocná.

Prerekvizity: pole, rekurzia
Úlohy na testovači: Prístupy - dynamické programovanie
Materiály: https://www.ksp.sk/kucharka/dynamicke_programovanie/

Párenie

Kedy: 1. týždeň piatok
Prednášajúci: Ralbo

Budeme hľadať maximálne párenie vrcholov v bipartitnom grafe.

Prerekvizity: DFS
Úlohy na testovači: Taxi cab scheme
Materiály: https://www.ksp.sk/kucharka/parenie/, http://www.dcs.fmph.uniba.sk/~anderle/tea/parenie.pdf

Fenwick (fínsky strom)

Kedy: 2. týždeň štvrtok
Prednášajúci: Krtko

Už vieš čo je to intervalový strom ale nechce sa ti ho vždy kódiť. Ukážeme si ako ho naprogramovať na menej riadkov a tak aby možno bežal kúsok rýchlejšie. Vysvetlíme si ako takáto implementácia funguje, prečo nepotrebuje žiadnu pamäť navyše a kedy je ju vhodné použiť.

Prerekvizity: Intervalový strom, nebáť sa binárnej mágie
Úlohy na testovači: Ľahký fín, Ochutené ľahôdky
Materiály: https://en.wikipedia.org/wiki/Fenwick_tree

Iné prednášky

Informatika na vysokých školách

Kedy: 1. týždeň, streda 11:00 - 12:00 (po prednáškach)

Debatovanie o vysokých školách so študentami týchto škôl (FMFI, VUT, MFF, MUNI)

Prerekvizity: záujem ísť na vysokú školu