Přednáška NTIN060: Algoritmy a datové struktury

Poradi ke zkousce 7.6.2016

Vzhledem k velkemu poctu prihlasenych vypisuji jeste jeden termin 9.6.2016 od 9:00 (8.6. mame na katedre statni zaverecne zkousky, kde jsem predsedou). Prosim obzvlaste ty, kteri jsou v poradi pro 7.6. hodne vzadu, aby se prehlasili na 9.6. - budu jim pro stanoveni poradi (dle data a hodiny prihlaseni ke zkousce) pocitat puvodni datum a hodinu.

Dulezite oznameni

Pořadí na zkoušky

Odpřednášeno:

Přednáška 23.2.2016

Slovníkové datové struktury, prioritní fronty, nevýhody seznamů, binární stromy jako implementace slovníku i prioritní fronty

Přednáška 1.3.2016

AVL stromy

Přednáška 8.3.2016

Červeno-černé stromy

Přednáška 15.3.2016

Vyvážené stromové datové struktury - dokončení.

Horní odhad průměrné hloubky průměrného binárního vyhledávacího stromu - začátek

Přednáška 22.3.2016

Horní odhad průměrné hloubky průměrného binárního vyhledávacího stromu - dokončení

Analýza průměrného chování quicksortu.

Přednáška 29.3.2016

B-stromy

Přednáška 5.4.2016

Základní algoritmy pro třídění, dolní odhad porovnání v nejhorším případě

Přednáška 12.4.2016

Dolní odhad pro průměrný počet porovnání porovnávacího třídícího algoritmu.

Radix sort.

Přednáška 19.4.2016

Radix sort pro lexikografické třídění.

Hašování - základní techniky.

Přednáška 26.4.2016

Universální a perfektní hašování.

Přednáška 3.5.2016

Prohledávání grafů (obecné, do hloubky, do šířky), aplikace na problémy týkající se souvislosti a cest.

Dijkstrův algoritmus (nedokončeno).

Přednáška 10.5.2016

Důkaz správnosti Dijkstrova algoritmu, obecně o dokazování správnosti algoritmů

Přednáška 17.5.2016

Hledání cest v grafech, Bellman-Fordův algoritmus.

Přednáška 24.5.2016

Požadavky ke zkoušce

V následujících požadavcích nepředstavují jednotlivé odstavce otázky, ale soupis toho, co byste o tématu měli(y) umět. Konkrétní otázky budou obvykle jen určitá část daného odstavce.

1. Binární vyhledávací stromy, AVL stromy a červeno-černé stromy: je třeba umět definici; znát algoritmy pro vkládání, vyhledávání, minimum a maximum pro všechny tři typy, vynechávání pro BVS a AVL a mít představu o ČČ vynechávání; umět dokázat horní odhad hloubky stromu pro AVL a ČČ; znát základní operace, používané u vyvážených stromů (rotace, u ČČ také posuny černé barvy) a vědět řádově, kolikrát se mohou při jednotlivých operacích použít (řádově znamená jestli v nejhorším případě jednou, dvakrát, nebo podél celé nějaké cesty ve stromu nebo třeba i úplně všude ve stromu).

2. Horní odhad pro průměrnou hloubku průměrného (průměr přes všechny stromy) binárního vyhledávacího stromu a pro průměrný počet porovnání (průměrný přes všechny permutace vstupní posloupnosti) provedených Quicksortem. Případná klopýtnutí ve formálních úpravách základní rovnosti budou posuzovány shovívavě (i když na "výborně" by být neměly), ale je nutné umět vysvětlit, jak jsme se k záklední nerovnosti dostali.

3. B-stromy: popis stromu a algoritmů pro vkládání, vynechávání, vyhledávání, minimum a maximuma znát základní operace, kteé jsou při tom využívány. Otázka spíš pro případ rozhodování mezi dvěma stupni klasifikace než jako samostatná otázka.

4. Dolní odhady pro počet porovnání provedených porovnávacím algoritmem pro třídění (nejhorší a především průměrný případ). Radix sort.

5. Hašování - základní schéma, dobře znát abstraktní definici i konkrétní provedení universálního hašování a myšlenku konstrukce perfektního hašování pomocí dvojstupňového použití universálního hašování.

6. Prohledávání grafu - obecné schéma, prohledávání do šířky a do hloubky, jejich základní vlastnosti a použití. Nebude používáno jako samostatná otázka.

7. Hledání nejkratších cest algoritmus Dijkstrův, algoritmus Bellmana a Forda a hledání v acyklických orientovaných grafech na základě topologického uspořádání. Důraz kladen na důkaz správnosti a výpočetní složitosti.

8. Hledání minimální kostry grafu

9. Podle toho, kolik bude odpřednášeno, ještě možná další otázka.

Jak odstartovat applety Algovize

Zkuste následující postp (je potřeba, abyste měli ve svem prohlížeči instalovanou Javu):

1. Spusťte aplikaci "Configure Java". Já jsem to zkoušel na Windows 10, kde jsem z wokna vlevo dole otevřel nabídku, zvolil "Všechny aplikace", kliknul na "Java" a tam už se objevila volba aplikace Configure Java

2. V Configure Java se vybere panel Security, v něm se klikne na Edit Site List a do seznamu, který se objeví, se přidá adresa http://www.algovision.org/Algovision/Algovision.java a všechno se odklikuje.

3. Pak by už Algovize měla jít spustit ze stránky http://www.algovision.org/Algovision/algovision.java

Je tam ale vložena hodně stará verze, která dobře nefunguje, zjistil jsem, že neumí z binárního vyhledávacího stromu vynechat číslo z vrcholu se dvěma následníky a nefunguje tam rotace (!). Zkusím tam dát lepší verzi.

Zkuste tento postup a napište mi v každém případě, ať už se vám to povedlo či nepovedlo.

Literatura

Luděk Kučera: Algovize aneb procházka krajinou algoritmů (ISBN 978-80-902938-5-4)
(možno vypůjčit v knihovně MFF UK)

Další texty
Average depth of a random BST [.ps 38 kB] [.pdf 39 kB]

A lower bound for comparison sorting (average case) [.ps 44 kB] [.pdf 50 kB]

Logaritmic bound for universal hashing [.pdf 64 kB]

Universal hashing [.ps 41 kB] [.pdf 48 kB]

Dijkstra algorithm [.ps 173 kB] [.pdf 71 kB]