===== Magistr ===== ---- ** Rozvrh denně dopoledne 9.00 - 11.45, odpoledne 12.30 - 14.30, 14.45 - 16.00.** \\ // Úpravy možné po dohodě s lektorem.// ** Učebna E-128 v areálu FEL ČVUT na Karlově náměstí.** \\ ---- ==== Pondělí 14.9. dopoledne ==== Vede Marko Berezovský .\\ . === Úlohy neřešitelné, úlohy pomalejší než exponenciální, NP-uplné problémy === Velká čísla, rostoucí rychleji než exponenciálně * [[https://www.urionlinejudge.com.br/judge/en/problems/view/1829| Biggest Number ??]] * [[http://math.andrej.com/2008/02/02/the-hydra-game/| Boj s hydrou ]] * [[https://en.wikipedia.org/wiki/Goodstein%27s_theorem|Původ hydry]] * [[https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation|Knuth arrow notation]] With Graham number mentioned * [[https://en.wikipedia.org/wiki/Ackermann_function|Ackermann function]] * [[https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Moser_notation|Steinhaus-Moser notation]] . Máme 6 přihrádek, v každé je nějaký počet korun. Za vstup do hry platíme 100 korun. Můžeme udělat libovolný počet tahů a potom si odnést všechny koruny ze všech přihrádek. Jeden tah vypadá takto: Z některé přihládky (s indexem J) vyjmeme korunu a vrátíme kasinu, potom určíme, kterou variantu, A nebo B, provede kasino: A. kasino přidá do pravé sousední přihrádky (s indexem J+1) dvě koruny. B. kasino prohodí (swap) obsah dvou sousedních přihrádek vpravo (s indexy J+1, J+2). . . Příklad varianty A, před a po: . |__2__| |__0__| |__5__| |__4__| |__7__| |__1__| // vyjmeme 1 korunu z 3. přihrádky . . |__2__| |__0__| |__4__| |__6__| |__7__| |__1__| // ve 4. přihrádce přibydou 2 koruny . . Příklad varianty B, před a po: . |__2__| |__0__| |__4__| |__6__| |__7__| |__1__| // vyjmeme 1 kč z 1. přihrádky . . |__1__| |__4__| |__0__| |__7__| |__6__| |__1__| // obsah 2. a 3. přihrádky je prohozen . . Otázka ====== Vstupní konfigurace je (nepříliš slibně vypadající) . . |__1__| |__1__| |__1__| |__1__| |__1__| |__1__| . Omylem jsme již 100 Kč zaplatili a jsme ve hře. Kolik maximálně můžeme vyhrát zpět?? . ---------------------------------------------------------------------------------------- **Úlohy** [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1925|10984 - Double NP-hard]] [[https://www.codechef.com/problems/PROB03|HeadQuarters -- node cover]] **Neexistuje algoritmus řešení** * [[https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable_generalizations|Collatz 3n+1 zobecněny problém]] * [[https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Undecidability|Undecidable Game of Life]] * [[https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem|Celočíselné rovnice]] * [[https://en.wikipedia.org/wiki/Post_correspondence_problem|Post correspondence problem]] * [[https://en.wikipedia.org/wiki/Wang_tile|Wang Tiles]] * [[https://www.geeksforgeeks.org/theory-of-computation-halting-problem/|Halting problem]] * [[https://en.wikipedia.org/wiki/Context-free_grammar#Undecidable_problems| Undecidabile grammar problems]] Neformálně: * [[http://waitbutwhy.com/2014/11/1000000-grahams-number.html|Velikost Grahamova čísla]] * [[http://www.scottaaronson.com/writings/bignumbers.html| O velikosti velkých čísel vůbec]] ____________________________________________________________________________________________ ==== Pondělí 14.9. odpoledne ==== Vede Marko Berezovský .\\ . === TSP, vrcholové pokrytí, 3-obarvení === Grafové problémy {{ :courses:laso2019:grafyulohy.pptx | rekapitulace }} {{ :courses:laso2019:grafycesty.pptx | Složitost cest v grafech }} Agentura pořádá několik akcí v daném obbdobí. Každá akce začíná ráno určitého dne a končí odpoledne buď ve stejném dni nebo v některém dalším dni. Každá akce probíhá v jedné místnosti, žádné dvě akce se nesmí odehrávat ani částečně ve stejné místnosti. Určete minimální potřebný počet místností. . Na vstupu je na prvním řádku počet akcí a na dalších řádcích dvojice čísel představující pořadové číslo prvního a posledního dne jedné akce. . Např. 9 6 6 1 5 5 8 10 10 1 3 7 8 8 10 11 13 8 9 Bude zapotřebí 4 místností. Řešte úlohu pro další data: {{ :courses:laso2019:courses1.txt | set1}}, {{ :courses:laso2019:courses2.txt | set2}}, {{ :courses:laso2019:courses3.txt | set3}}. **Úlohy** * [[hhttps://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=363&page=show_problem&problem=515|574 - Sum It Up]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=363&page=show_problem&problem=565|624 - CD]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=137&page=show_problem&problem=382|441 - Lotto]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=138&page=show_problem&problem=1226|10285 - Longest Run on a Snowboard]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=138&page=show_problem&problem=465|524 - Prime Ring Problem]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=140&page=show_problem&problem=961|10020 - Minimal coverage]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=138&page=show_problem&problem=670|729 - The Hamming Distance Problem]] * [[https://www.spoj.com/problems/ADFRUITS/|ADFRUITS - Advanced Fruits]] * [[https://www.spoj.com/problems/WACHOVIA/|WACHOVIA - Wachovia Bank]] knapsack? * [[https://www.spoj.com/problems/PARTY/|PARTY - Party Schedule]] jen pro jistotu -- rychlost? ____________________________________________________________________________________________ ==== Úterý 15.9. dopoledne a odpoledne ==== Vede Marko Berezovský .\\ . === Diskrétní a rychlá Fourierova transformace === [[https://www.symbolab.com/solver/complex-numbers-calculator/|komplexní kalkulátor]] \\ [[https://www.solumaths.com/en/math-apps/calc-online/calculator|komplexní kalkulátor]] \\ [[https://www.easycalculation.com/engineering/mechanical/discrete-fourier-transform.php|DFT kalkulátor]]\\ [[http://scistatcalc.blogspot.com/2013/12/fft-calculator.html|DFT kalkulátor]]\\ **Úlohy** [[https://www.spoj.com/problems/POLYMUL/|POLYMUL - Polynomial Multiplication]]\\ [[https://www.spoj.com/problems/MUL/|MUL - Fast Multiplication]]\\ ____________________________________________________________________________________________ ==== Středa 16.9. dopoledne ==== Vede Petr Ryšavý\\ **Slidy: {{courses:laso2020:20200916_kmp_ahocorasick.pdf}}** === Hledání v textu, algoritmy KMP, Aho-Corasickové === * [[https://www.spoj.com/problems/NHAY/|NHAY - A Needle in the Haystack]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=396|455 - Periodic Strings]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1620|10679 - I Love Strings!!]] * [[https://www.spoj.com/problems/WPUZZLES|WPUZZLES - Word Puzzles]] Nové 2020: * [[https://open.kattis.com/problems/stringmatching]] * [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1239|10298 - Power Strings]] * [[https://naq19.kattis.com/problems/nvwls|NAQ 2019 - NWVLS]] ==== Středa 16.9. odpoledne ==== Vedou ... .\\ Na praktikách asistují ... \\ (Vyučující postupně určíme do začátku LASO 2020)\\ . === Intervalové a segmentové stromy === ____________________________________________________________________________________________