Budapesti Mûszaki Egyetem, Budapest
Számítástudományi és Információelméleti Tanszék


Algorimusok é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)

  • 1.feladatsor
  • 2.feladatsor
  • 3.feladatsor
  • 4.feladatsor
  • 5.feladatsor
  • 6.feladatsor
  • 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

    Katalóniai Mûszaki Egyetem, C.Martínez: Algoritmusok és adatstruktúrák analízise kurzus (spanyolul)

    Back to the Home Page


    Updated: Sept 30. 2003
    aantos NOSPAMkukacNOSPAM gmail pont com