Search
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-112 v areálu FEL ČVUT na Karlově náměstí.
Vede Marko Berezovský
Velká čísla, rostoucí rychleji než exponenciálně
. 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 )
Neexistuje algoritmus řešení
Neformálně:
____________________________________________________________________________________________
Grafové problémy
rekapitulace
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: set1, set2, set3.
Úlohy
Valla, Mareš: Průvodce labyrintem algoritmů Přehledné základy DFT a FFT v kapitole 17.
komplexní kalkulátor komplexní kalkulátor DFT kalkulátor DFT kalkulátor
POLYMUL - Polynomial Multiplication MUL - Fast Multiplication
Vede Petr Ryšavý
Slidy: 20220914_kmp_ahocorasick.pdf
Nové 2020: