===== 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-327 v areálu FEL ČVUT na Karlově náměstí.** \\ ---- ==== Pondělí 15.9. dopoledne ==== //Vedou a asistují// **Marko Berezovský**\\ === Úlohy neřešitelné, úlohy pomalejší než exponenciální, NP-uplné problémy === Velká čísla, rostoucí rychleji než exponenciálně * [[https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Moser_notation|Steinhaus-Moser notation]] * [[http://math.andrej.com/2008/02/02/the-hydra-game/| Boj s hydrou ]] * [[https://en.wikipedia.org/wiki/Goodstein%27s_theorem|Původ hydry]] Goodstein sequences * [[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]] . 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). (Indexy musí být vždy validní) . . 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__| . Již jsme 100 Kč zaplatili a jsme ve hře. Kolik maximálně můžeme vyhrát zpět?? . ---------------------------------------------------------------------------------------- (Viz také: Po-Shen Loh, Math Encounters - Massive Numbers: https://www.youtube.com/watch?v=YdpFPHFE60w ) ([[https://cw.fel.cvut.cz/wiki/courses/laso/magistr/data | Jednoduchý skript dole na stránce]]) **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/Rice%27s_theorem#Examples|Undecidable properties of programs/codes]] * [[https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem|Celočíselné rovnice]] * [[https://en.wikipedia.org/wiki/Post_correspondence_problem|Post correspondence problem (PCP)]] * ([[https://people.ksp.sk/~kuko/pcp/|PCP examples]])([[http://webdocs.cs.ualberta.ca/~games/PCP/list.htm|PCP instances+]]) * ([[https://kubokovac.eu/pcp/| Ukázky PCP]]) * [[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]] * [[https://en.wikipedia.org/wiki/List_of_undecidable_problems|List of undecidable 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]] * [[https://www.youtube.com/watch?v=prURA1i8Qj4&t=408s|Hydra Game at Numberphile channel]] ____________________________________________________________________________________________ ==== Pondělí 15.9. odpoledne ==== //Vedou a asistují// **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: [[https://cw.fel.cvut.cz/wiki/courses/laso/magistr/data | Data]] **Úlohy** **Úlohy** * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1925|10984 - Double NP-hard]] * [[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=7&page=show_problem&problem=515|574 - Sum It Up]] záloha * [[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=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://www.codechef.com/problems/PROB03|HeadQuarters -- node cover]] * [[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ý 16.9. dopoledne a odpoledne ==== //Vedou a asistují// **Marko Berezovský**\\ === Diskrétní a rychlá Fourierova transformace (DFT a FFT) === [[http://pruvodce.ucw.cz/| Valla, Mareš: Průvodce labyrintem algoritmů]] Přehledné základy DFT a FFT v kapitole 17. [[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]]\\ [[https://www.geeksforgeeks.org/fast-fourier-transformation-poynomial-multiplication/ |Kód na GeeksForGeeks]] **Úlohy** [[https://www.spoj.com/problems/POLYMUL/|POLYMUL - Polynomial Multiplication]]\\ [[https://www.spoj.com/problems/MUL/|MUL - Fast Multiplication]]\\ https://www.geogebra.org/m/G6xCSzkQ kreslení polynomu ____________________________________________________________________________________________ ==== Středa 17.9. dopoledne ==== Vedou: **Petr Ryšavý** \\ **Slidy: {{20250917_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]] Další úlohy: * [[https://open.kattis.com/problems/stringmatching]] * [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1239|10298 - Power Strings]] * [[https://open.kattis.com/contests/naq19open/problems/nvwls|NAQ 2019 - NWVLS]] ==== Středa 17.9. odpoledne ==== //Vedou a asistují// **Marko Berezovský**\\ === DP === [[https://projecteuler.net/|Project Euler]]: - [[https://projecteuler.net/problem=114|Counting block combinations I]] - [[https://projecteuler.net/problem=115|Counting block combinations II]] - [[https://projecteuler.net/problem=116|Red, green or blue tiles]] - [[https://projecteuler.net/problem=117|Red, green, and blue tiles]] - [[https://projecteuler.net/problem=191|Prize Strings]] Další DP: - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1022|10081 - Tight Words]] - [[https://www.spoj.com/problems/DIEHARD/|DIEHARD - DIE HARD]] - [[http://www.spoj.com/problems/M3TILE/|M3TILE - LATGACH3]] - [[https://www.spoj.com/problems/BYTESH1/|BYTESH1 - Filchs Dilemna]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1803|10862 - Connect the Cable Wires]] - [[http://www.spoj.com/problems/WACHOVIA/|Wachovia Bank]] - [[http://www.spoj.com/problems/MMAXPER/|MMAXPER - Rectangles Perimeter]] - [[https://www.spoj.com/problems/MIXTURES|MIXTURES - Mixtures]]| - [[https://www.spoj.com/problems/ROCK/|ROCK - Sweet and Sour Rock]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1500|10559 - Blocks]] - [[https://www.spoj.com/problems/TWENDS/|TWENDS - Two Ends]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=823|882 - The Mailbox Manufacturers]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2664| 11617 - An Odd Love ]] - [[https://www.spoj.com/problems/MARTIAN/|MARTIAN - Martian Mining]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1202|10261 - Ferry Loading]] === Pokročilejší haldy === * [[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html|Přehledné vizualizace]] * [[https://www.geeksforgeeks.org/binomial-heap-2/|Binomiální haldy]] * [[https://www.geeksforgeeks.org/fibonacci-heap-set-1-introduction//|Fibonacci haldy]] * ____________________________________________________________________________________________ ==== Záloha vůbec ==== * [[https://math.fel.cvut.cz/en/people/gollova/lgr/lgr_11a.pdf|Ad Jádro grafu -- 18. přednáška z LGR]] * [[http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/intro.pdf|Všeobecné poučení o hrách a Nimu]] [[http://mks.mff.cuni.cz/library/JakHratANeprohratFH/JakHratANeprohratFH.pdf|(výtah, česky)]] * [[http://web.mit.edu/sp.268/www/2010/impartialGames.pdf|Přehled na MIT]] * [[http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames | TopCoder - The Basic Introduction into Games]] * [[http://teorie-grafu.cz/zakladni-pojmy/jadro-grafu.php | Jádro grafu]] * Teorie her na CMU - [[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-10-13.pdf|Combinatorial Game Theory]],[[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-24-13.pdf|Even More Games]] * Kombinatorické hry - krátká ilustrace {{ :courses:a4b36acm1:2021_ls:combigames.pdf | pdf }} * Nimbers (Sprague-Grundyho čísla) - ukázková úloha ([[http://www.codechef.com/problems/BIGPIZA| Socializing Game around Pizza]], {{ :courses:a4b36acm2:2018_zs:pizza.pdf | kód? }}) * [[http://www.fq.math.ca/Scanned/1-4/whinihan.pdf|Fibonacciho Nim]] * Zkuste si nim online: [[http://benpyle.com/nim/|benpyle]], [[https://www.cariboutests.com/games/nim.php|CaribouTests]], [[https://education.jlab.org/nim/|Jefferson Lab]], [[https://www.archimedes-lab.org/game_nim/play_nim_game.html|Archimedes Lab]] Příklady: * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1345|Bachet's Game]] * [[http://www.spoj.com/problems/CLK/|Chomp]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1309|Euclid's Game]] * [[http://www.spoj.com/problems/QCJ3/|The Game]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=2484|Integer Game]] * [[http://www.spoj.com/problems/MATGAME/|Matrix Game]] * [[http://www.spoj.com/problems/NGM/|A Game with Numbers]] * [[http://www.spoj.com/problems/PT07A/|Play with a Tree]]: How to tackle a problem of this sort was not covered in the lecture, but if you are interested, see [[http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf|Ferguson's Game Theory]] (lecture 6, specifically, the colon and fusion principles). * [[http://www.spoj.com/problems/BNWNIM/en/|Black and White Nim]]: Difficult, yet intriguing problem.