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-112 v areálu FEL ČVUT na Karlově náměstí.


Pondělí 16.9. dopoledne

Vede …

Úlohy neřešitelné, úlohy pomalejší než exponenciální, NP-uplné problémy

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ě:

  ____________________________________________________________________________________________

Pondělí 16.9. odpoledne

Vede …

TSP, vrcholové pokrytí, 3-obarvení

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

Úlohy

  ____________________________________________________________________________________________

Úterý 17.9. dopoledne a odpoledne

Vede …

Diskrétní a rychlá Fourierova transformace (DFT a FFT)

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

Úlohy

POLYMUL - Polynomial Multiplication
MUL - Fast Multiplication

  ____________________________________________________________________________________________

Středa 14.9. dopoledne

Hledání v textu, algoritmy KMP, Aho-Corasickové

Středa 14.9. odpoledne

Vede …

Pokročilejší haldy

  ____________________________________________________________________________________________
courses/a4b36acm1/laso2024/magistr.txt · Last modified: 2024/06/18 16:19 by berezovs