Budapesti Műszaki Egyetem, Budapest
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)

  • 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: March 15. 2024
    aantos NOSPAMkukacNOSPAM gmail pont com