Warning
This page is located in archive.

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ě

.

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

Pondělí 16.9. odpoledne

Vede Marko Berezovský

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

  ____________________________________________________________________________________________

Úterý 17.9. dopoledne a odpoledne

Vede Marko Berezovský

Diskrétní a rychlá Fourierova transformace

komplexní kalkulátor
komplexní kalkulátor
DFT kalkulátor
DFT kalkulátor

Úlohy

POLYMUL - Polynomial Multiplication
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é

courses/laso2019/magistr.txt · Last modified: 2019/09/18 12:28 by berezovs