Számítástudományi és Információelméleti Tanszék

Algoritmusok és adatstruktúrák valószínűségi elemzése

Előadó:

Antos András

Heti óraszám:

4

Kreditpont:

5

Vizsga:

írásbeli
1998.január 16. és 22. 12h, V2.102

Előfeltétel:

nincs, de sokat segíthet a következők alapvető ismerete: valószínűségszámítás, bináris keresőfa, gyorsrendezés, entrópia, kódolás, gráfok, gráfalgoritmusok, véletlen gráfok, dinamikus programozás, Markov-láncok, bolyongás.

Időpont, hely:

Hétfő 12:15-13:45, R.307
Csütörtök 12:15-13:45, V1.408

Megjegyzés:

A vizsga előre kiadott feladatokból történik, de ezek évközbeni rendszeres beadásával kiváltható.
A tárgy korábban többek között a montreáli McGill University-n került előadásra. Eredeti címe Probabilistic Analysis of Algrithms and Data Structures, előadója Luc Devroye volt. Ennek következtében a tárgyhoz angol nyelvű nyomtatott jegyzet fénymásolható (Luc Devroye: Probabilistic Analysis of Algrithms and Data Structures).

Házifeladat sorok (egyben vizsgafeladatok)

Szégyenfal - a megoldók listája

Tematika - angolul

Records and their applications:

main properties of records, binary search tree, quicksort, d dimensional outer layer, height of rawa trees.

Random sampling:

randomized algorithms, balls in urns, the hypergeometric distribution, the closest pair problem, binary space partitions, tournaments to find the k-th best, selecting the k-th smallest from n elements.

Galton-Watson branching processes:

branching processes, height of a random binary search tree, selecting the k-th smallest from n elements.

Entropy:

tries, entropy, the law of large numbers, depth of a random trie, PATRICIA trees, digital search trees, Huffman trees, Lempel-Ziv coding.

Heuristic search:

depth first search, bounded lookahead and backtrack.

Randomized incremental methods:

the closest pair problem, linear programming a la Seidel.

Random graphs:

definition of random graph, graph algorithms, evolution of random graph, connected graphs, second moment method, the size of the giant component.

Graph algorithms:

connectivity in linear expected time, minimal spanning tree in linear expected time, transitive closure and depth-first search.

The euclidean traveling salesman problem:

dynamic programming, heuristics, Karp's algorithms, the quality of the heuristic, simple lower bound for the optimal tour, Azuma's inequality.

Simple random walks:

random binary trees.

Markov chain:

definitions, convergence, dynamic lists, dynamic search trees, the coupon collector, random walks on graphs, generating random combinatorial objects.

Tematika - magyarra ferdítve

Rekordok és alkalmazásaik:

rekordok fő tulajdonságai, bináris kereső fa, gyorsrendezés, d dimenziós külső burok, rawafák magassága.

Véletlen mintakiválasztás:

randomizált algoritmusok, golyók urnákban, hipergeometriai eloszlás, legközelebbi pár probléma, bináris tér partíciók, turnamentek a k. legjobb megtalálásá hoz, n-ből k. legkisebb elem kiválasztása.

Galton-Watson elágazó folyamatok:

elágazó folyamatok, véletlen bináris keresőfa magassága, n-ből k. legkisebb elem kiválasztása.

Entrópia:

szófák, entrópia, a nagy számok törvénye, véletlen szófa mélysége, PATRICIA fák, digitális kereső fák, Huffman fák, Lempel-Ziv kódolás.

Heurisztikus keresés:

mélységi keresés, korlátozott előretekintés és visszalépés.

Randomizált növelő módszerek:

legközelebbi pár probléma, lineáris programozás a la Seidel.

Véletlen gráfok:

véletlen gráfok definíciója, gráf algoritmusok, véletlen gráfok evolúciója, összefüggő gráfok, második momentum módszer, az óriás kompone ns mérete.

Gráfalgoritmusok:

összefüggőség lineáris várható időben, minimális feszítőfa lineáris várható időben, tranzitív lezárt és mélységi keres& eacute;s.

Az euklideszi utazó ügynök probléma:

dinamikus programozás, heurisztikák, Karp algoritmusa, a heurisztika minősége, egyszerű alsó korlát az optimális körútra, Azuma egyenlőtlenség.

Egyszerű bolyongások:

véletlen bináris fák.

Markov láncok:

definíciók, konvergencia, dinamikus listák, dinamikus keresőfák, a kupon gyűjtő, bolyongás gráfokon, véletlen kombinatorikai objektumok generálása.

Más kapcsolódó külső linkek

Back to the Home Page

Updated: March 15. 2024