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: Gardener, Žaba
Na tejto prednáške si povieme o čom vlastne to programovanie je, zadefinujeme pojmy ako algoritmus a program. Potom si ukážeme, ako porovnávať rýchlosť algoritmov a nejaké príklady. A nakoniec si vyskúšame vylepšenie jednoduchého algoritmu.
Prerekvizity:žiadne
Úlohy na testovači: -
Úlohy na KSP School: https://school.ksp.sk/courses/prefix-sums/
Úvod do teórie grafov
Kedy: 1. týždeň utorok; 2. týždeň utorok
Prednášajúci: Viktor, Kaja
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é - ukážeme si, čo sú zač, aké môžu mať v reálnom živote využitie, a naučíme sa základnú terminológiu práce s nimi. Veľká časť informatiky súvisí s grafmi, a tieto znalosti sa vám určite veľmi zídu.
Prerekvizity: žiadne
Úlohy na testovači: Úvod do grafov
Úlohy na KSP School: https://school.ksp.sk/courses/graphs1/graphs1-intro/graphs1-intro1/, https://school.ksp.sk/courses/graphs1/graphs1-representing/graphs1-representing1/, https://school.ksp.sk/courses/graphs1/graphs1-special/graphs1-special1/
Queue, stack, deque, set, map
Kedy: 1. týždeň streda; 2. týždeň streda
Prednášajúci: Kika, Filipko
TBA
Prerekvizity: TBA
Ú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
Úlohy na KSP School: https://school.ksp.sk/courses/python-2/py2-set-dict/set/, https://school.ksp.sk/courses/python-2/py2-queue-stack/queue/
Rekurzia
Kedy: 1. týždeň štvrtok
Prednášajúci: David
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
Úlohy na testovači: Rekurzia
Úlohy na KSP School: https://school.ksp.sk/courses/python-2/functions/functions1/
Halda
Kedy: 1. týždeň piatok
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, pole, strom, zložitosť
Úlohy na testovači: Dátové štruktúry – halda
Úlohy na KSP School: https://school.ksp.sk/courses/heap/
Rekurzia, sort
Kedy: 2. týždeň štvrtok
Prednášajúci: Janči
Keď hovoríte vtip o rekurzií, musíte: 1) zistiť, či ešte zostali nejakí vaši kamaráti, ktorý ho chcú počuť 2) povedať vtip o rekurzií. Rekurzia je teda technika, pri ktorej si rozdelíme problém na menšie podproblémy, ktoré vyriešime a výsledky spracujeme. Ale ako ich vyriešime? Predsa rovnako, ako pôvodný problém - rozdelením! Rekurzia sa často používa pri triedení, pretože je jednou z najjednoduchších implementácií algoritmov typu rozdeľ a panuj, ako sú quicksort a mergesort. Zaujímavých triediacich algoritmov je však omnoho viac, a skoro každý sa hodí na nejaký tip problému.
Prerekvizity: (časová) zložitosť, pole
Úlohy na testovači: uvedené v samostatných prednáškach
Úlohy na KSP School: uvedené v samostatných prednáškach
Menej stredne ťažké prednášky
Brute force
Kedy: 1. týždeň utorok
Prednášajúci: Skaloš
TBA
Prerekvizity: TBA
Úlohy na testovači: Prístupy - brute force
Úlohy na KSP School: https://school.ksp.sk/courses/bruteforce/
Prehľadávanie do šírky (BFS)
Kedy: 1. týždeň streda; 2. týždeň streda
Prednášajúci: David, Kaja
BFS je jednou zo základných metód prehľadávania grafu, ktorá preskúma všetky vrcholy na jednej úrovni začínajúc počiatočným vrcholom predtým, než prejde na ďalšiu.
Prerekvizity: úvod do grafov
Úlohy na testovači: Grafy - BFS
Úlohy na KSP School: https://school.ksp.sk/courses/graphs1/graphs1-bfs/graphs1-bfs-intro/
Binárny vyhľadávací strom
Kedy: 1. týždeň štvrtok
Prednášajúci: Gardener
TBA
Prerekvizity: TBA
Úlohy na testovači: Dátové štruktúry - binárne vyhľadávacie stromy
Úlohy na KSP School: --
Sort
Kedy: 1. týždeň piatok
Prednášajúci: Marcel
Na tejto prednáške sa pozrieme na pomerne základný problém informatiky a aj bežného života: dostaneme nejaké prvky (napríklad čísla), a máme ich utriediť. Na tejto prednáške si prejdeme niekoľko spôsobov, ako také niečo môžeme urobiť - od najjednoduchších a najpomalších až po najrýchlejšie.
Prerekvizity: základy, pole, zložitosť, rekurzia
Úlohy na testovači: Algoritmy - triedenie, KSP school, kurz o triedení
Úlohy na KSP School: https://school.ksp.sk/courses/sort/
Teória čísel
Kedy: 2. týždeň pondelok
Prednášajúci: Viktor
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č
Úlohy na testovači: Teória čísel - ľahšia, ťažšia
Úlohy na KSP School: --
Dijkstra
Kedy: 2. týždeň utorok
Prednášajúci: Janči
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: graf, BFS, halda (ale nie nutne, je možné vysvetliť na začiatku)
Úlohy na testovači: Grafy - Dijkstra
Úlohy na KSP School: https://school.ksp.sk/courses/graphs1/graphs1-dijkstra/graphs1-dijkstra-intro/
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
Úlohy na KSP School: https://school.ksp.sk/courses/bin-search/
Zametanie
Kedy: 1. týždeň streda; 2. týždeň štvrtok
Prednášajúci: Filipko
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
Úlohy na testovači: Prístupy - zametanie
Úlohy na KSP School: --
Prehľadávanie do hĺbky (DFS)
Kedy: 1. týždeň štvrtok
Prednášajúci: Filipko
Táto prednáška sa zameriava na prehľadávanie do hĺbky (DFS) ako jednu zo základných metód prehľadávania grafov. DFS je algoritmus, ktorý nám pomáha systematicky preskúmať graf od jedného vrcholu ku všetkým dostupným vrcholom v čo najväčšej hĺbke predtým, než sa vrátime späť.
Prerekvizity: zaklady, pole, rekurzia, grafy
Úlohy na testovači: Grafy - DFS
Úlohy na KSP School: https://school.ksp.sk/courses/graphs1/graphs1-dfs/graphs1-dfs-intro/
Geometria, konvexný obal
Kedy: 1. týždeň piatok
Prednášajúci: Jano Priner
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
Úlohy na KSP School: --
Intervalový strom
Kedy: 2. týždeň pondelok
Prednášajúci: Jano Hozza
TBA
Prerekvizity: TBA
Úlohy na testovači: Dátové štruktúry - intervalové stromy
Úlohy na KSP School: --
Materiály: https://www.ksp.sk/kucharka/intervalovy_strom/
Trie
Kedy: 2. týždeň utorok
Prednášajúci: Miško
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: čo je to strom, stromová dátová štruktúra
Úlohy na testovači: Prefixy v zozname, Playlist, XOR na množine
Úlohy na KSP School: --
Floyd-Warshall
Kedy: 2. týždeň streda
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
Úlohy na KSP School: --
Kostry a union-find
Kedy: 2. týždeň štvrtok
Prednášajúci: Sabinka
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: graf, rekurzia, hadla (ale prežijeme aj bez), predstava o OOP / pointroch
Úlohy na testovači: Kostry
Úlohy na KSP School: --
Ťažké prednášky
Rolling hash
Kedy: 1. týždeň utorok;
Prednášajúci: Gardener
TBA
Prerekvizity: TBA
Úlohy na testovači: Prefixy v zozname, Playlist (sekcia Stringy)
Úlohy na KSP School: --
Materiály: https://www.ksp.sk/kucharka/prefixove_sumy/
Dynamika
Kedy: 1. týždeň štvrtok
Prednášajúci: Viktor
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: pole, rekurzia
Úlohy na testovači: Prístupy - dynamické programovanie
Úlohy na KSP School: --
Materiály: https://www.ksp.sk/kucharka/dynamicke_programovanie/
Párenie
Kedy: 1. týždeň piatok
Prednášajúci: fezjo
TBA
Prerekvizity: TBA
Úlohy na testovači: Taxi cab scheme
Úlohy na KSP School: --
Materiály: https://www.ksp.sk/kucharka/parenie/, http://www.dcs.fmph.uniba.sk/~anderle/tea/parenie.pdf
Mosty a artikulácie
Kedy: 2. týždeň pondelok
Prednášajúci: Sabinka
TBA
Prerekvizity: TBA
Úlohy na testovači: Grafy - Mosty a artikulácie
Úlohy na KSP School: --
Materiály: https://www.ksp.sk/kucharka/mosty_a_artikulacie/
Treap
Kedy: 2. týždeň utorok
Prednášajúci: fezjo
TBA
Prerekvizity: TBA
Úlohy na testovači: --
Úlohy na KSP School: --
Materiály: https://www.ksp.sk/kucharka/treap/
KMP
Kedy: 2. týždeň streda
Prednášajúci: fezjo
TBA
Prerekvizity: TBA
Úlohy na testovači: Stringy
Úlohy na KSP School: --
Materiály: https://www.ksp.sk/kucharka/kmp/
LCA
Kedy: 2. týždeň štvrtok
Prednášajúci: Jano Hozza
TBA
Prerekvizity: TBA
Úlohy na testovači: --
Úlohy na KSP School: --
Materiály: https://www.ksp.sk/kucharka/lca/
Čas poslednej úpravy: 18. júl 2023 22:05