24.-30. Dubna 2022 bylo soustředění FIKS ve Štědroníně. Následují hrubé osnovy k mým přednáškám.

Neděle

Základy složitosti

Kdy je problém lehké a kdy těžké řešít? Konkrétní příklady společně se způsobem jak toto matematicky zachytit (O notace).

  • Vypisování hvězdiček: příklady na O(N), O(N na 2), O(N log N), O(2 na N), O(N!)
  • Co je to algoritmus?
  • Jak dlouho trva instrukce? – problemy se zavislosti algoritmu na konkretnim stroji
  • Který algoritmus je Rychlejší 30*N log N nebo N log^2 N
  • Notace O(N) formálně – funkce f a g, f = O(g) pokud existuje konstanta c a n0 takova, ze pro vsechna n >= n0 je f(n) <= c g(n)
  • Omega a Theta
  • Jak rychlý je jednoduchý algoritmus?
    • naivni razeni – O(N^2)
    • vypsat vsechny permutace – O(N*N!) – diskuse o velikosti cisel RAM-model
    • najit prvek v serazenem poli – O(N), binarni puleni O(log N)
    • naivního hledání v textu – O(N*M) – slozitost pomoci vice parametru

Pondělí

Základy grafů

Grafy jsou všude. Ukážeme si kde všude lze grafy najít a na jaké úlohy se dají použít. Že některé věci se na nich dají řešit jednoduše, ale některé další neumí nikdo vyřešit rychle.

  • Graf, Vrcholy, Hrany, jejich kreslení
  • Běžné příklady grafů v praxi
  • Problém 4 barev
  • Problém 2 barev vs. Listové 2-obarvení
  • Jednotažky – Eulerovské grafy

Zdroje

Prohledávání grafů (BFS, DFS, Dijkstra)

Hledání nejkratší cesty z bodu A do bodu B uvnitř grafu. V jednoduchých grafech jednoduché. Když započteme další faktory, tak trochu těžší, ale stále to lze vyřešit.

  • pripomenuti Grafu
  • DFS
    • Jak najít jestli lze dojet z A do B? implementace
    • souvislé komponenty
    • intuice DFS a jeho implementace
    • strom a les
    • casova a pametova slozitost
  • BFS
    • Jak najít nejkratší cestu z A do B? implementace
    • casova a pametova slozitost
  • Dijkstra
    • Hledání cesty ve váženém grafu?
    • Uprava BFS
      • prioritni fronta
      • vicenasobne vlozeni stejneho vrcholu do fronty
    • casova a pametova slozitost
  • A*
    • heuristika s garantovanym vysledkem
    • Ukazat DFS, BFS, Dijkstru graficky a porovnat s A*
  • Jarnikuv algoritmus
    • kostra grafu
    • trivialni uprava Dijkstrova algoritmu

Kombinatoricka teorie her

Hry dvou hráčů s perfektní informací - piškvorky, nim a další. Jak je vyhrát/neprohrát.

  • Kombinatoricke hry – plna informace, deterministicke
  • Jak hrat sachy, herni strom, heuristika na odhadnuti sance vyhry, minmax
  • zaklady a intuice herní teorie
    • hra dominování – L poklada domina vertikalne, R horizontalne
    • Vyherni stavy L, R, N a P, levý a pravý hráč vs první a druhý hráč
    • příklady nekolika partií
      • elko je N
      • icko je L
      • lezate I je R
      • ctverec je N
      • dva ctverce jsou P
      • ctverec a elko je N
      • vetsi elko je P
  • nestranné vs zaujaté hry
  • nestranne hry: standardni triky
    • Umistovani Domin – symetrie
    • Chomp – kradení strategie
    • Stridavy had – parovaci strategie
    • Lamani cokolady – parita
  • budovani teorie
    • prohranou hru znacme 0
    • jednotahovou hru pro L necht je 1, a stejna hra pro R at je -1
    • z tech budujeme dalsi hry kombinacemi pomoci {|}
    • narozeniny jsou krok, ve kterem onu hry vytvorime – hloubka odpovidajiciho rozhodovaciho stromu
    • soucet her
      • pricteni prohrane hry nezmeni vysledek; znacime 0 ci {|}
      • ohledne ostatnich kombinaci toho nedovedeme moc rict, leda ze L+L=L, R+R=R, L+N=LuN, R+N=RuN
      • hluboka teorie kolem
    • budovani cisel
      • mame jiz -1,0,1
      • zavedme cisla jako hru kde ma pouze jeden hrac tahy, tj. N={N-1|} a -N={|1-N}
      • pokud mame dve cisla ‘vedle’ sebe, tak jedno vlevo druhe vpravo dava prumer
      • libovolny zlomek muzeme aproximovat s libovolnou presnosti
      • pro {A|B} ktere nejsou ‘vedle’ sebe, tak je vysledek cislo mezi nimi s co nejmensimi narozeninami
  • jak tato teorie zafunguje pro nestranne hry
    • nimbery a mex
    • hra nim
    • vyhrávající strategie pro nim
    • hra nim v misere variante

Úterý

Geometrie

Bod, přímka, kruh, vektorový a skalarní součin, konvexní obálka, řezání polygonů, a když bude čas a vůle, třeba i Beziérovy křivky či 3D geometrie.

  • Zakladni geometrie a intuice ke standardnim nastrojum
    • Základní geometricke obrazce – bod, úsečka, přímka, polorovina, rovina, polygon, obdélník, rovnoběžník
    • Báze, rotace, zvetseni, preklopeni
    • Vektory, skalarni a vektorovy soucin
    • Reprezentace operací maticí, skladani operaci pronasobenim matice
    • Obsah polygonu pomoci vektoroveho soucinu
    • rezano polygonu
    • zmenseni polygonu
  • Diskretni geometrie
    • navrh hry Dobble
    • podminky “zajimavosti” navrhu
    • primky v diskretnim prostoru, podminky netriviality
    • Fanova rovina
    • obecny navrh pro rady prvocislo^2
  • Beziérovy křivky
    • Predpis pomoci LERP
    • rad Bezierovy krivky
    • De Casteljuv algoritmus pro hledani bodu krivky
    • Bernsteinovy polynomy a jejich vyznam vuci puvodni krivce
    • generovani grafiky podel Bezierovy krivky
    • kratke predstaveni krivosti krivky
    • Bezierovy krivky jako slozeni nekolika polynomu na omezenem rozsahu

Zdroje

Vyhledávací stromy

Pro práci s mnoha prvky (množina) je potřeba umět je rychle přdat, odebrat, hledat, měnit; toto vše umějí vyvažované vyhledávací stromy, které jsou za strukturami map, či set.

  • Mnozina v programovacich jazycik, a co bezne umi
  • Binární vyhledávací strom (BVS)
    • struktura, vlastnosti
    • vkládání, slozitost O(H) – worst case
    • další prvek, slozitost O(H)
    • odebirani, rozbor pripadu, slozitost O(H)
    • Implementace BVS
  • AVL
    • zpusob jak omezit hloubku stormu, a tak zarucit dobrou slozitost
    • hloubkovy invariant
    • rotace, dvojita rotace, slozitost
    • vlozeni, slozitost

Jak funguje věda

Způsob lidského poznání se dere kupředu něčím těžko definovatelným – a to bych se pokusil přiblížit. Kde se bere nové poznání, a jak víme, že je správně?

Oddeleno do postu o vede

Jak se mohou stredoskolaci zapojit do vedy?

  • SOC – stredoskolska odborna cinnost
  • Seminare – trenink, zkusit vyresit problem a sepsat reseni se podoba vedeckemu procesu

Středa

Vyhledávání v textu

Základy řetězců a abeced, KMP algoritmus, hashování.

  • Uloha hledani vzorku uvnitr textu
  • Retezce (string) a abecedy, formalne
  • Naivni vyhledavani v O(N*M)
  • Zpetny pristup, spatny worst case, dobra slozitost v normalnich textech
  • rolling hash
    • polynom v modulu
  • KMP
    • border array
  • Vyhledavani s chybami
  • Editacni vzdalenost

Čtvrtek

Segmentové stromy

Jak rychle odpovídat dotazy na minimum z rozahu na poli (tzv. RMQ). Metody sparse table, fenwick, a nakonec segmentové stromy.

  • Updaty a dotazy na element či rozsah (interval)
  • Sum dotazy bez update a s update, časový rozdíl předpočtu s naivním
  • Max dotazy bez udpate naivně, v log n pomocí tree decomp

Pátek

Řešení těžkých problémů

Kód používaný pro demonstraci na přednášce stáhnete zde: fiks_sat.zip. MiniSat lze stáhnout online dle vašeho OS.

  • Které problémy umíme řešít rychle, a co ‘rychle’ znamená?
    • Rychlé uvažujeme polynomiální
    • Co je to P a NP
      • turingův stroj
      • pouze pro rozhodovací problémy (odpověď je Ano/Ne)
      • řešitelné v polynomiálním čase = P
      • nedeterministicky řešitelné v polynomiálním čase = NP
  • Logika
    • Proměnné, Literály, Klauzule, Logické spojky, Formule
    • Úprava logické formule
    • Úloha SAT – rozhodovací, jak je těžká?
    • Převod do CNF
  • Řešení SAT
    • vyvození trivialit
    • jak vyresit 2-SAT
    • rozhodovací strom – full search
    • index, sledování dvou proměnných z klauzule – obrovské ušetření času algoritmu
    • CDCL – chceme se naučit něco z minulosti
      • Graf závislostí
      • unique implication point

Neprovedené

Union-find a minimální kostry

Sturuktura Union-find umí rychle spojovat množiny. Její použití si ukážeme na Kruskalově algoritmu pro heldání minimální kostry grafu.

Pokročilé textové operace

Hledání všech výskytů kusu textu, či nejdelší společný řetězec - metody Suffix array s LCP

  • co vsechno bychom chteli – longest common substring;
  • Uloha vyhledavani, ale tentokrat s predpoctem, poznamka o KMP slozitosti
  • Trie
    • Zaznam o mnoha slovech ve kterem, ve kterem lze dobre vyhledavat
  • Suffix array
    • Index vsech moznych vyskytu, funguje, ale je moc veliky
    • Ukladat pouze index zacatku, je linearni, ale jak spocitat
    • lexikograficke porovnani s delkami
    • binary lifting
    • longest common substring
  • FFT
  • naznaceni Aho-Corasick

Artikulace, mosty, a silně souvislé komponenty

Graf obsahuje strukturálně ‘slabé’ části, které po smazání graf rozseknou na více ‘kusů’. K jejich hledání a k dalším účelům se dá chytře využít DFS.

Vývoj videoher

Vytvořit hru není jednoduché. Ukážeme si co je potřeba a jaké nástroje se dají použít.

Práce s Vim a terminálem

Shell, Bash, Zsh

Zákady LaTeX

Alternativa k MS Word. Systém maker, který umožňuje autorům textů sázet a tisknout svá díla ve velmi vysoké typografické kvalitě. (jak říká wikipedia)