Ugrás a tartalomhoz

Véletlen és algoritmusok

Rónyai Lajos (2011)

Typotex Kiadó

A jegyzet elsősorban a BME Villamosmérnöki és Informatikai Karának informatikus MSc hallgatói számára készült, a Felsőbb matematika D című tárgyhoz. A véletlen választások alkalmazása átszövi az egész számítógépes világot, jelen van az alapvető protokolloktól a szoftvertechnológiáig szinte minden nagyobb részterületen. Hogyan lehet hatékony véletlen módszereket kapni? Mikor van létjogosultságuk az ilyen megoldásoknak, és mikor érdemes inkább mással próbálkozni? Milyen általános elveket követnek ezek a módszerek? Ezekre a kérdésekre legegyszerűbben talán a véletlent használó számítási módszerek, másként mondva a randomizált algoritmusok tanulmányozásával kereshetjük a választ. Célunk, hogy megismerkedjünk a legfontosabb ilyen módszerekkel. Eddig nem volt magyar nyelven elérhető ilyen tárgyú jegyzet vagy tankönyv. Az első fejezetben összefoglaljuk a valószínűséggel kapcsolatos alapfogalmakat. A második fejezetet néhány nevezetes és fontos randomizált algoritmus bemutatásának szenteljük. A gyorsrendezés a kiindulópontunk. Ezután érdekes és jellegzetes eljárásokat tárgyalunk geometriai/grafikai, aritmetikai és algebrai feladatokra. Bemutatunk két erőteljes, a véletlent érdemben használó adatszerkezetet (falom, univerzális hashelés). A fejezet Karger, Klein és Tarjan minimális költségű feszítőfát számító algoritmusának bemutatásával zárul. A harmadik fejezetben a véletlen módszer matematikai gyökereivel foglalkozunk. Vezérfonalunk Erdős Pál óriási horderejű felismerése: véletlen választások segítségével érdekes matematikai struktúrák létezése igazolható. A nevezetes példák (hipergráf-színezés, Ramsey-számok, Turán-számok) tárgyalásakor ismételten hangsúlyozzuk, hogy ezek a tiszta létezést bizonyító érvelések igen gyakran vezetnek hatékony randomizált algoritmushoz. Itt foglalkozunk az algoritmusainkban felhasznált véletlen csökkentésének, a derandomizálásnak a problémakörével is. Lovász lokális lemmája és annak a nemrég felfedezett briliáns algoritmikus változata (Moser–Tardos) zárja a fejezetet. A egyedik fejezetben azzal a kérdéssel foglalkozunk, hogy a véletlent használó algoritmusok miként jelennek meg a bonyolultsági osztályok térképén. Megismerkedünk az RP, Las Vegas, és a BPP feladatosztályokkal, és vázoljuk a korábban megismert nagy osztályokhoz való viszonyukat, pontosabban azt, amit ma tudunk ezekről. Lesz szó a BPP=P? kérdésről, ami azt feszegeti, hogy tud-e a véletlen nagyot segíteni? Másként fogalmazva: van-e olyan feladat, amely a véletlent segítségül híva polinom időben megoldható, véletlen nélkül viszont nem? A véletlen és az együttes munka (interakció) ötvözetét leíró interaktív bizonyítások is itt kaptak helyet; fontos gyakorlati alkalmazása ennek a gondolatkörnek a nulla ismeretű bizonyítás, amit széles körben használnak a titkos adatközlés területén. Az utolsó fejezetben gráfokat és véletlent alkalmazó modelleké a főszerep. Először véges Markov-láncokkal foglalkozunk. Az algoritmikus alkalmazások közül tárgyalunk néhány fontosabbat: elérhetőség irányítatlan gráfokban, a PageRank algoritmus, Metropolis-algoritmus. A fejezet második részében a nagy, bonyolult szerkezetű hálózatok modellezésére alkalmas véletlen gráfokkal foglalkozunk. Az Erdős–Rényi-gráfok, a Watts–Strogatz-, és Albert–Barabási-gráfok rövid ismertetése után Kleinberg modelljével zárul az anyag.
Letölthető anyagok
RONYAI_Veletlen_alg.pdf
DC metaadatok
Cím:
Véletlen és algoritmusok
Szerzők:
Rónyai Lajos
Kiadó:
Typotex Kiadó
Közreműködők:
Budapesti Műszaki és Gazdaságtudományi Egyetem
Dátum
2011.06.30.
Azonosító:
[URI]
Források:
Könyv formában nem jelent meg [ISBN: 978-963-279-451-8]
Nyelv
Magyar
Terület:
2011-2016, Magyarország
Tárgyszavak
véletlen, algoritmus, randomizálás, rendezés, keresés, bonyolultsági osztályok, komplex hálózatok.