Hric 2019

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
spidoosho
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 27. 5. 2019 19:36
Typ studia: Informatika Bc.

Hric 2019

Příspěvek od spidoosho »

Zadani
1)Dokázat, nebo vyvrátit + napsat potřebný definice: f(n) € o(h(n) a zároveň g(n) € O(h(n)) z toho vyplívá f(n) + g(n) € O(h(n))
2) Dijkstrův algoritmus: popsat,předpoklady, korektnost, analýza algoritmu
3) ukázat že hloubka rozhodovacího stromu je alespoň O(nlogn)
4) upravit BVS tak aby se zachovali jeho vlastnosti a dokázal v logaritmickém čase odpovědět na dotaz IntMin[k,l] ( prostě minimum z intervalu)

Reseni
1) Lze to dokázat z definic o a O.
2) Viz skripta, popř. průvodce
3) Víceméně jde o odhad faktoriálu - podrobný důkaz je ve skriptech.
4) Základem je si v každém vrcholu BVS pamatovat minimum v levém a pravém podstromu.

Poznamky
Test je na 80 minut. Příklady po 5 bodech a jsou potřeba aspoň 2/3. Na zkoušení se dostane téma a na papír si sepíšete co o něm víte popř dokážete to co po vás chce.
Hric mi přišel na zkoušení docela hodný. Když jsem nevěděl odpověď na jeho otázku rovnou tak mě pošoupl nebo to nechal být.
Důkazy korektnosti algoritmů stačilo naznačit a ukázat že víte v čem spočívají.
Témata u zkoušek byla např.: SSK, univerzální hašování, bellmanfordův algoritmus, kruskal, quicksort.

--------------------------------------------

Zadani
1. Znění Master theoremu (všechny případy) + lehký příklad na určení parametru 'a' v rekurenci tak, aby vyšly všechny případy složitosti.
2. AVL stromy - popis datové struktury + jak probíhá operace Insert (rozbor případů).
3. Jarníkův algoritmus - popis algoritmu a důkaz korektnosti.
4. Je-li zadáno číslo x, najděte v posloupnosti b1...bn dva prvky bi a bj takové, že x = bi + bj. Popište algoritmus a určete složitost a vhodnou datovou strukturu.

Reseni
1. - 3. v prezentaci, důkaz pro Jarníka je u stejný, jako u Kruskala, jen je třeba znát souvislost s pseudokódem, 4. -> hašovací tabulkou lze dostáhnout O(n)

Poznamky
U písemky strhává bodíky za nejasnosti, jinak je bodování štědré.
Na ústním zadá téma (já měl např. SSK) a kromě toho s vámi projde i písemku, pokud v ní byly nějaké chybky (je fajn si před zkoušením najít výsledky, pokud víte, že máte něco špatně).
Klade důraz na korektnost algoritmů, proto je dobré se naučit věty a lemmata.
Ústní bylo narozdíl od jiných předmětů příjemné, má hodně trpělivosti.
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“