===== 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-127 v areálu FEL ČVUT na Karlově náměstí.** \\ ---- ==== Pondělí 16.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ě * [[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]] * [[https://en.wikipedia.org/wiki/Ackermann_function|Ackermann function]] * [[https://www.youtube.com/watch?v=YdpFPHFE60w|Hra s velkým ziskem]] . 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 levé sousední přihrádky (s indexem J+1) dvě koruny. B. kasino prohodí (swap) obsah dvou sousedních přihrádek vlevo (s indexy J+1, J+2). . . Příklad varianty A, před a po: . |__2__| |__0__| |__5__| |__4__| |__7__| |__1__| // vyjmeme 1 kč z 3. přihrádky . . |__2__| |__0__| |__4__| |__6__| |__7__| |__1__| . . 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__| |__6__| |__7__| |__1__| . . 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?? . ---------------------------------------------------------------------------------------- https://www.imo-official.org/problems/IMO2010SL.pdf, problem C4 **Ú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ě, oddechově: * [[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í 16.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ý 17.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 18.9. dopoledne ==== Vede Václav Blažej === Intervalové a segmentové stromy === ____________________________________________________________________________________________ ==== Středa 18.9. odpoledne ==== Vede Josef Malík === 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]]