Összefoglaló
Országok listája
HungaryBudapesti Műszaki és Gazdaságtudományi EgyetemVillamosmérnöki és Informatikai KarMérnök informatikusAlgoritmusok ElméleteJegyzetekÖsszefoglaló
2008.03.10 20:58:44
Az alábbi szöveg egy formázás és képek nélküli előnézete a dokumentumnak. A tökéletes megjelenítéshez jelentkezz be, majd töltsd le a dokumentumot.
ALGORITMUS Lineáris keresés Bináris keresés Buborék rendezés Beszúrásos rendezés Merge sort Heap sort Quick sort k-adik elem kiválasztása Ládarendezés Radix rendezés Batcher fésülés Bináris fák - naív
LEÍRÁS Rendezett listában a legelsõ elemtõl kezdve végigmegyünk amíg meg nem találjuk, vagy nagyobbat nem találunk Rendezett listában keresés felezéssel Rendezés a szomszédos elemek felcserélésével Egy rendezett résztömbbe az új elemet a megfelelõ helyre szúrjuk. Mehet lineáris és bináris kereséssel. Két rendezett sorozat egybe rendezése Tömbrendezés, kupac adatszerkezet felhasználásával Tömbrendezés, véletlen particionálással kupac építés, majd k db MINTÖR() Ha a rendezési tartomány az elemek számához képest nem túl nagy Összetett kulcsokat tartalmazó, fix rendezési tartományú univerzum rendezése Párhuzamos alg. két rendezett sorozat összefésülésére KERES(s,S); MIN()/MAX(); BESZUR(s,S); TÖRÖL(s,S); TÓLIG(a,b,S); atlagos BESZUR() rekordok a levélben, 2-3 mutató, m<=log2(n)+1 BESZUR(), TÖRÖL() 2-3 fák általánosítása egy csúcs bal és jobb részfája között max 1 a különbség BESZUR(), TÖRÖL() önszervezõ faszerkezet átlagosan nagyon gyors tárolási mód (nem rendezett) h(K)-val indexelt tömb elemei mutatnak egy-egy vödörre (láncolt listára) melyben az azonos h(K)-jú elemek vannak Csak belsõ memória! Ha T[h(K)] foglalt, akkor lineárisan vagy random vagy egy másik hash fv.-el keresünk egy üres helyet neki. legrövidebb s->v út keresése Nagyon ritka (sûrû) gráfokra: V \ KÉSZ kupacban (dkupacban) legrövidebb s->v út keresése, akkor is, ha van negatív súlyú él, de nincs negatív kör Összes v,w csúcs közötti távolság meghatározása. Feltételek, mint B.-F.-nál Mely v,w csúcsok között van irányított út? Gy.k. ua. mint a Floyd a. Addig megyünk elõre, amig tudunk és csak utána nézzük a szomszédokat (=rekurzióban visszaugrás) Mélységi bejárás során nincs visszaél Topologikus rend.: x->y esetén x elõbb van mint y Leghosszabb út keresése DAG-ban Egy irányított G-ben mindenhonnan mindenhova eljuthatunk irányított úton Elõször meglátogatjuk egy csúcs összes szomszédját. és csak utána haladunk elõre Minimális költségû feszítõfák keresése. Kék szabály : 0<>X csúcshalmazból a min. súlyú kimenõ színezetlen élet kékre festjük. Piros szabály : ha egy körben nincs piros él, akkor a max. színtelen él piros lesz Következõ kék él egy min. él az F kék fából !F-be f a min. színtelen él, (f két végpontja ugyanabban a kék fában) ? (f=piros) : (f=kék) Ha E egy párosítás és nem létezik hozzá javító út, akkor E max. psítás. A magyar módszer javító utat keres
KÖLTSÉG O(n) O(log n) O(n^2) O(n^2) O(n*log n) O(n*log n) O(n) O(n) O(k*n) O(log^2 (n)) O(l) O(k+l) O(log2 (n))
OLD. 27 28 30 32 36 41 44 45 47 48 50 60
2-3 fák B-fák AVL-fák S-fák Szófák Hash-elés (general) Vödrös hash-elés Nyitott címzés Dijkstra algoritmus Dijkstra algoritmus éllistával Bellman-Ford algoritmus Floyd algoritmus Warshall algoritmus Mélységi bejárás DAG ellenõrzése DAG topologikus rendezése PERT módszer Erõs összefüggõség Szélességi bejárás
64 O(log n) 69 71 O(log n) 80 83 86 88 90 O(n^2) O((n+e)*log n) (akár O(e) O(n^3) O(n^3) O(n^3) O(max{n,e}) O(n+e) O(n+e) 116 119 121 123 126 129 137 138 140 141 O(n+e) 147
Piros-kék algoritmus Prim módszer Kruskal módszer Magyar módszer
153 157 O(e*log e) O(n*e) 161 170
Hasonló témájú dokumentumok
- 2008-06-24 17:15:59
- 2007-12-27 13:26:05
A mások által feltöltött dokumentumokat értékelheted. Ha úgy ítéled meg, hogy a vizsgára való felkészülés szempontjából hasznos volt egy dokumentum, akkor adj rá sokcsillagos értékelést.
Ha hibákat tartalmaz, vagy egyéb probléma van vele, akkor keveset.
A dokumentumok sorrendje az értékelések alapján adódik. Ami fentebb van a listában, azt hasznosabbnak ítélték társaid. Az új dokumentumok pedig (értékelések hiányában) szintén a lista tetején kezdenek.
Hozzászólások
Ha észrevételed van egy dokumentummal kapcsolatban (például hibát találtál benne), akkor a Hozzászólások részben jelezheted. Az olyan jellegű kérdéseket mint pl.: A 2. feladat 4. sorából milyen átalakítással jutottunk az 5. sorban szereplő képlethez? - szintén ide érdemes írni
Egy tipp az oldalhoz! - Töltsétek ki a Tantárgyi adatlapokat a tantárgyak oldalain. Fontos lehet a tantárggyal kapcsolatos információ vagy az előadóval való egyszerű kapcsolattartás végett. Az adatlapot csak akkor módosíthatod ha az adott tárgyat a saját tárgyaidhoz adtad.
Egy felsőoktatási közösségi oldal amely segít kapcsolatot tartani a hallgatók között, így segítséget nyújt a sikeres tanulmányokhoz...
