Search
This is an old revision of the document!
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í.
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 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
10984 - Double NP-hard HeadQuarters -- node cover
Neexistuje algoritmus řešení
Neformálně, oddechově:
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.
____________________________________________________________________________________________
komplexní kalkulátor komplexní kalkulátor
Téma ještě upřesníme:
Zatím nejasno: Suffix arrays Toky v sítítch Bipartitiní grafy a párování
nebo :
Vede Václav Blažej
Vede Josef Malík