Rövidített megjelenítés

dc.contributorBudapesti Műszaki és Gazdaságtudományi Egyetemhu_HU
dc.creatorRónyai Lajoshu_HU
dc.date2011-06-30hu_HU
dc.date.accessioned2019-08-08T13:20:43Z
dc.date.available2019-08-08T13:20:43Z
dc.identifierISBN: 978-963-279-451-8hu_HU
dc.identifier.urihttp://dtk.tankonyvtar.hu/xmlui/handle/123456789/7899
dc.descriptionA 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.hu_HU
dc.formatapplication/pdfhu_HU
dc.languagehuhu_HU
dc.publisherTypotex Kiadóhu_HU
dc.rightsRónyai Lajoshu_HU
dc.rightsBudapesti Műszaki és Gazdaságtudományi Egyetemhu_HU
dc.sourceKönyv formában nem jelent meg [ISBN: 978-963-279-451-8]hu_HU
dc.subjectvéletlenhu_HU
dc.subjectalgoritmushu_HU
dc.subjectrandomizáláshu_HU
dc.subjectrendezéshu_HU
dc.subjectkereséshu_HU
dc.subjectbonyolultsági osztályokhu_HU
dc.subjectkomplex hálózatok.hu_HU
dc.titleVéletlen és algoritmusokhu_HU
dc.typetexthu_HU
dtk.firműszakihu_HU
dtk.firinformatikahu_HU
dtk.oecd01. Természettudományok::01.01. Matematikahu_HU
dtk.playerpdfplayerhu_HU
dtk.purchaseTÁMOP-4.1.2-08/2/A/KMR-2009-0027 Budapesti Műszaki és Gazdaságtudományi Egyetemhu_HU
dtk.size95 phu_HU
dtk.typebookhu_HU
dtk.udc---- FŐTÁBLÁZAT::0 ÁLTALÁNOS TARTALMÚ ÍRÁSMŰVEK. TUDOMÁNY ÉS KULTÚRA. ISMERETEK. SZERVEZETEK. INFORMÁCIÓ. DOKUMENTÁCIÓ. KÖNYVTÁR. INTÉZMÉNYEK. PUBLIKÁCIÓK. KIADVÁNYOK::005 Menedzsment::51 Matematikahu_HU


A dokumentumhoz tartozó fájlok

Thumbnail

A dokumentum a következő gyűjtemény(ek)ben található meg

Rövidített megjelenítés