Čepek všechny zkoušky

Pokračování přednášky TIN060 Algoritmy a datové struktury I

Čepek všechny zkoušky

Příspěvekod awk » 24. 1. 2019 18:34

Seznam písemek z fóra:


Písemka 1:
Řešení:


Písemka 2:
Řešení:


Písemka 3:
Řešení:


Písemka 4:
Řešení:


Písemka 5:
Řešení:


Písemka 6:
Řešení:


Písemka 7:
Řešení:


Písemka 8 (je v ní RSA, které nebylo 2018/2019 odpředneseno):



Ústní:
  • definice P, NP, nějakej převod
  • preflow-push
  • aproximační algoritmy (TSP s trojúhelníkovou nerovnosti, vrcholové pokrytí)
  • konvexní obal
  • carry-look-ahead sčítání
  • Dinicův algoritmus
  • násobení polynomů a FFT
  • hloubka Batcherova merge sortu
  • dolní odhad složitosti transpozičních sítí
  • (RSA)
Naposledy upravil awk dne 27. 1. 2019 20:37, celkově upraveno 1
Uživatelský avatar
awk
Matfyz(ák|ačka) level I
 
Příspěvky: 43
Registrován: 21. 5. 2018 17:54
Typ studia: Informatika Bc.

Re: Čepek všechny zkoušky

Příspěvekod xcvb » 27. 1. 2019 14:43

Dobrá práce, díky.
Zajímalo by mě, jestli když zkouší u ústního (Goldbergův) preflow-push algoritmus, jestli chce jen vysvětlit jak funguje, nebo i dokazovat korektnost/složitost. Ty důkazy jsou totiž hnusně dlouhé (u Mareše 5, v Cormen et al asi 8 stran).
xcvb
Matfyz(ák|ačka) level I
 
Příspěvky: 5
Registrován: 26. 1. 2019 00:46
Typ studia: Informatika Bc.

Re: Čepek všechny zkoušky

Příspěvekod awk » 27. 1. 2019 20:30

Ohledně 2. termínu u Čepka (24.1.2019)

Písemná byl recyklát (písemka 2).

Průběh ústní:
Určitá část lidí obvykle odevzdává před 2 hodinovým limitem. Těm Čepek nabídne jestli nechtějí jít na ústní hned ještě před obědem.
Na termínu, kde jsem byl já takhle vzal 4 lidi. Čepek vám dá papír a řekně vám co po vás chce. Vzhledem k tomu, že zkouší více lidí naráz každý dostane jinou otázku. Zpravidla se jedná o něco uvedené v seznamu v 1. příspěvku. Potom vám dá čas na rozmyšlenou a po nějaké době se vrátí a popovídá si, rád se v důkazech ptá na to, jak jsme z jednoho dostali druhé a ověřuje jestli tomu rozumíte. I když víte všechno, tak se snad vždy ještě ptá na nějakou definici (třeba P a NP).

Právě první osoba, která odevzdala zkoušku dostala hned preflow push. Seděl jsem kousek vedle, tak jsem něco zaslechl.
Pokud vím, tak chtěl vědět jak algoritmus funguje, korektnost a složitost (je tedy dobré znát ty Čepek only termíny). Ohledně lemmat mu u některých stačila alespoň idea důkazu. Ale jinač vyloženě nelpí na jeho terminologii a celkově na ústní je příjemný. Stejně jako u opravování, kde říkal, že by mu nevadil bitonický sort místo merge sortu. Pokud něco popletete v písemce, tak ji občas nechává i po zkontrolování dodělat na vyžádání.

Já jsem byl rád, že preflow push už byl zadán, protože jsem o něm nevěděl nic a vůbec ne Čepkovy lemmata. Když ke mně Čepek došel zeptal jsem mě, jestli jsem byl na poslední přednášce. Odpověděl jsem mu, že ano a dostal jsem konvexní obal. Za což jsem byl nesmírně rád, protože to vlastně byla jediná věc, kterou přednášel podle průvodce bez slidů. Potom jsem mě zeptal na definici NP (zajímá ho jestli opravdu rozumíte ekvivalenci mezi těmi dvěmi definicemi ve slidech). Odešel jsem s jedničkou aniž bych musel dokazovat jedinou větu. Tím chci říct, že obtížnost ústní se bohužel výrazně liší a záleží na štěstí. Nicméně nevím o tom, že by někoho vyhodil na ústní.
Uživatelský avatar
awk
Matfyz(ák|ačka) level I
 
Příspěvky: 43
Registrován: 21. 5. 2018 17:54
Typ studia: Informatika Bc.

Re: Čepek všechny zkoušky

Příspěvekod Dave » 31. 1. 2019 17:52

Zkouška z 31. 1. - zadání bylo jako Písemka 5

Myslím, že druhý příklad si zaslouží pár řádků :)

Máme kruhovou budovu, která je rozdělena do n místností, do kterých se nám dostali termiti. Úkolem je termity vyhubit během m dní s minimálními náklady. Každý den je možné vyčistit jakýkoli počet místností. Cena vyčistění místnosti i v den j je c_{ij}. Termiti se mohou šířit budovou jedním směrem z i do i + 1 až z n do 1. Proto pokud vyčistíme místnost i+1 dříve než místnost i, musíme platit poplatek za udržení s_{ij}. Máme zajištěno min\{c_{ij}\}>m\cdot max\{s_{ij}\} (tedy nevyplatí se čistit místnost znovu).

Nástin řešení pomocí tokové sítě:
- Vytvoříme si m+1 úrovní, do každé úrovně vytvoříme vrchol pro každou místnost.
- Mezi vrcholy odpovídající místnosti i vede hrana z úrovně j do j + 1 s kapacitou c_{ij}.
- Z vrcholů odpovídajících místnosti i vedou hrany do vrcholů odpovídajícím místnosti i + 1 z úrovně j do j' pro j' < js kapacitou s_{ij'}
- Zdroj spojíme s první úrovní hranami s nekonečnou kapacitou a poslední úroveň spojíme se stokem také hranami s nekonečnou kapacitou.
- Pustíme alg. na max tok, najdeme tak min. řez a ten odpovídá optimálnímu řešení, což už se dá snadno dokázat.
Dave
Matfyz(ák|ačka) level I
 
Příspěvky: 4
Registrován: 1. 6. 2018 19:10
Typ studia: Informatika Bc.

Re: Čepek všechny zkoušky

Příspěvekod SaNuel » 8. 2. 2019 00:47

Len maličkosť k ústnej. Takmer vždy (aspoň keď som bol ja vnútri) padla otázka na istú definíciu z oblasti NP (NP-úplnosť, NP-ťažkosť, silná NP-úplnosť...). Síce som z odretými ušami prešiel, aj keď som nevedel silnú NP-úplnosť, no nie každý mal to šťastie, takže asi je fajn prejsť si poriadne definície. Pre každý prípad. Pravdepodobne viac rozdáva otázky z NP, ak človek nevedel 3.-tiu úlohu ( u nás to bolo CP-01 - zadanie 5 vyššie ).
Kód: Vybrat vše
if ( exam.date > critical_date ) {
    this.procrastination.enable();
    Steam.launch("Skyrim");
}
else {
    this.panic.start();
    // TODO: This isn't working...
}
Uživatelský avatar
SaNuel
Matfyz(ák|ačka) level I
 
Příspěvky: 5
Registrován: 11. 10. 2018 13:52
Typ studia: Informatika Bc.
Login do SIS: novelins

Re: Čepek všechny zkoušky

Příspěvekod xcvb » 8. 2. 2019 17:36

Pro statistiku budoucích generací - dnes byla zadaná na chlup přesně Písemka 4, včetně slov pro AC.
xcvb
Matfyz(ák|ačka) level I
 
Příspěvky: 5
Registrován: 26. 1. 2019 00:46
Typ studia: Informatika Bc.


Zpět na TIN061 Algoritmy a datové struktury II

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník