Algoritmusok és Adatszerkezetek II. előadás
2012. február 8.
Felelős tanszék: Számítógépes algoritmusok és mesterséges intelligencia tanszék
Nappali tagozaton: Előadás: heti 2 óra / 5 kredit. Teljesítés módja: Kollokvium. Gyakorlat: heti 1 óra / 0 kredit. Teljesítés módja: Aláírás. A kurzus felvételének előfeltételei : Algoritmusok és adatszerkezetek I., • • • • • • • • • • • • • • •
2012. február 8.
Megoldás szisztematikus keresése visszalépéssel (pénzváltás, n királynő). Megoldás szisztematikus keresése elágazás-korlátozással (pénzváltás, ütemezés). Tördelőtáblák (hasítótáblák). Kiegyensúlyozott keresőfák. AVL fák. Piros-fekete fák. Az RHalmaz adattípus megvalósítása ugrólistával (Skiplist). B-fák. Diszjunkt halmazok kezelése, az UnioHolvan adattípus. Geometriai algoritmusok. Amortizációs költségelemzés. Binomiális kupacok. Az egyesíthető prioritási sor megvalósítása Fibonacci-kupaccal. Mintaillesztés; a Knuth-Morris-Pratt algoritmus. Számelméleti algoritmusok, nyilvános kulcsú titkosítás. Közelítő algoritmusok.
Ajánlott irodalom: • [1] T. H. Cormen, C. E. Leiserson, R.L. Rivest: Algoritmusok, Műszaki Könyvkiadó, 2003. • [2] T. H. Cormen, C. E. Leiserson, R.L. Rivest, C. Stein: Új algoritmusok, Scolar Kiadó, 2003. • [3] T. Ottman, P. Widmayer: Algoritmen und Datenstrukturen, Wissenschaftsverlag, 1990 • [4] E. Knuth: A számitógépprogramozás művészete, 3. Kötet, Műszaki Könyvkiadó, 1990. • [5] A. V. Aho, J. E. Hopcroft, J. D. Ullman: Számítógép-algoritmusok tervezése és analízise,Műszaki Könyvkiadó, 1982. • [6] G. Gonnet, R. Baeza-Yates: Handbook of algorithms and data structures. In Pascal and C. , Addison-Wesley. 1991. • [7] R. Sedgewick: Algoritms in C++, Addison-Wesley. 1991. • [8] E. Horowitz, S. Shani: Fundamentals of Computer Algorithms, Computer Science Press, 1998. • [9] Adonyi Róbert: Adatstruktúrák és algoritmusok (letölthető jegyzet) 2012. február 8.
A kurzus teljesítésének feltételei:
Évközi számonkérés. • a) Gyakorlaton teljesítendő 10 rövid írásbeli dolgozat a 2., 3., 4., 6., 7., 8., 9. és 11. gyakorlaton. ◦ Elérhető maximális pontszám: 40 ◦ Teljesítendő minimális pontszám: 14 • b) Gyakorlaton teljesítendő 2 írásbeli dolgozat az 5. és 10. gyakorlaton. ◦ Elérhető maximális pontszám: 30/dolgozat ◦ Teljesítendő minimális pontszám: 0 • Elérhető maximális pontszám (a+b): 100 • Teljesítendő minimális pontszám (a+b): 35
2012. február 8.
A kurzus teljesítésének feltételei: Kollokvium • Elérhető maximális pontszám: 100. • A kollokvium 3 részből áll: • A. 5 kérdés a kurzus anyagát lefedő témakörökből. ◦ Elérhető maximális pontszám: 40 ◦ Teljesítendő minimális pontszám: 10 • B. Teljesen kidolgozandó tétel. ◦ Elérhető maximális pontszám: 30 ◦ Teljesítendő minimális pontszám: 10 • C. Gyakorlati feladatok megoldása. ◦ Elérhető maximális pontszám: 30 ◦ Teljesítendő minimális pontszám: 10 Érdemjegy. • • • • • 2012. február 8.
175 - 200 jeles (5) 150 - 174 jó (4) 125 - 149 közepes (3) 100 - 124 elégséges (2) 0 - 99 elégtelen (1)
Megjegyzések. • Aki az 1. feltételt nem teljesíti, az a vizsgaidõszak 1. hetében javító dolgozatot írhat. A hallgató csak akkor jelentkezhet kollokviumra, ha a javító dolgozattal megszerezhetõ max. 50 pontból min. 25 pontot teljesít. A javító dolgozattal szerzett pont nem számít be sem az 1. részbe, sem az összpontszámba. • Aki a dolgozatok írása közben nem megengedett segédeszközt használ, vagy ennek gyanuja felmerül, az a következõ vizsgákon írásbeli vizsga helyett szóbeli vizsga letételére kötelezhetõ, vagy az írásbeli vizsgáját szóban kell megvédenie. • Az előadások látogatása kötelező. Akinek az igazolatlan hiányzása meghaladja a 3 alkalmat, az nem vizsgázhat! Csak előre jelzett hiányzás igazolható, vagy baleseti jegyzőkönyv/korházi pecsét szükséges!
2012. február 8.
Motiváció • PTI BSC Záróvizsga tételek:
Algoritmusok és adatszerkezetek I. 1. Gráf algoritmusok (mélységi és széltében keresés, erősen összefüggő komponensek, minimális feszítőfák, legrövidebb utak). 2. Probléma megoldási módszerek (dinamikus programozás, mohó stratégia). Algoritmusok és adatszerkezetek II. 3. Keresőfák (AVL-fák, Piros-fekete fák, B-fák). 4. Geometriai alapalgoritmusok (pont helyzete, konvex burok, ponthalmaz legközelebbi és legtávolabbi pontpárja, metsző szakaszpárok keresése).
• Algoritmusok tervezése, hatékony
adatszerkezetek működésének ismerete
2012. február 8.
Szakmai gyakorlat Németországban Fraunhofer Institute for Integrated Circuits IIS Nordostpark 93 90411 Nuremberg Germany
Erasmus ösztöndíj 300 EUR Fraunhofer ösztöndíj 850 EUR Szállás, étkezés biztosítva Elsősorban Programtervező Informatikus vagy Mérnökinformatikus szakkal 2012. február 8.
Adatszerkezetek • Halmaz, Rhalmaz, Függvény absztrakt adatszerkezet, Rendezett minta
• Prioritási sor, Egyesíthető prioritási sor absztrakt adatszerkezet
• Halmazerdő adatszerkezet 2012. február 8.
Bináris keresőfa
fázunk... 2012. február 8.
[2] 232-241
Bináris keresőfa 21 9
29
4 1
2012. február 8.
17 6
13
24 20
22
37 27
31
43
Bináris keresőfa 21
9
29
4
17
1 (-∞,1)
2012. február 8.
6 (1,4)
(4,6)
13 (6,9)
(9,13)
24
20
22
37
27
31
43
(13,17) (17,20) (20,21) (21,22) (22,24) (24,27) (27,29) (29,31) (31,37) (37,43)
(43, ∞)
Fapont tárolása
első megközelítés, a gyakorlatban nem így tároljuk!
struct fapont{
int key, value ;
fapont bal, jobb, apa ; } apa
key balfiu
2012. február 8.
value jobbfiu
Bináris fa tárolása első megközelítés, a gyakorlatban nem így van!
public class fa {
int elemszam ;
struct fapont{
int key, value ;
fapont bal, jobb, apa ;
}
fapont nil, gyoker ;
void fa() {
fapont q = new fapont() ;
nil=q ;
gyoker=q ;
elemszam=0 ;
}
boolean beszur(int x, int v) { ... } ... } 2012. február 8.
nil
gyoker
k v
beszur(5, 8) 58
k v nil
gyoker
Keresés keresőfában 27 21
9
29
4
17
1 (-∞,1)
2012. február 8.
6 (1,4)
(4,6)
13 (6,9)
(9,13)
24
20
22
37
27
31
43
(13,17) (17,20) (20,21) (21,22) (22,24) (24,27) (27,29) (29,31) (31,37) (37,43)
(43, ∞)
Keresés keresőfában 26 21
9
29
4
17
1 (-∞,1)
2012. február 8.
6 (1,4)
(4,6)
13 (6,9)
(9,13)
24
20
22
37
27
31
43
(13,17) (17,20) (20,21) (21,22) (22,24) (24,27) (27,29) (29,31) (31,37) (37,43)
(43, ∞)
[3] fapont keres(int x) {
fapont p=gyoker ;
nil.key=x ;
while (p.key!=x) p=x
return p; gyökér } 21 q=keres(16) ;
9
4
1
17
6
13
nil 2012. február 8.
29
24
20
22
16
254
37
27
31
43
Beszúrás keresőfába 26 21
9
29
4
17
1 (-∞,1)
6 (1,4)
(4,6)
13 (6,9)
(9,13)
24
20
22
37
27
43
(13,17) (17,20) (20,21) (21,22) (22,24) (24,27) (27,29) (29,31) (31,37) (37,43)
(24,26) (26,27)
2012. február 8.
31
(43, ∞)
58
58
58
3
nil
2012. február 8.
nil
nil
boolean beszur(int x, int v) {
fapont p,papa ;
p=gyoker ;
papa=nil ;
while (p!=nil && p.key!=x) {
papa=p ;
if (x
else p=p.jobb;
}
if (p==nil) {
fapont ujpont = new fapont();
if (gyoker==p) gyoker=ujpont ; nil
ujpont.key=x ;
ujpont.value=v ;
ujpont.bal=nil;
ujpont.jobb=nil;
ujpont.apa=papa;
if (papa!=nil) {
if (x>papa.key) papa.jobb=ujpont;
else papa.bal=ujpont;
} 3
elemszam++ ;
return true ;
} else {
p.value=v ; beszur(3,9) ;
return false ;
} nil
}
2012. február 8.
58
gyoker
? ?? ? ?
58
9 ? ?? ? ?
Elem rákövetkezője 21 9
29
4 1
2012. február 8.
17 13
24 20
37 27
31
43
p rákövetkezője p
p
2012. február 8.
p
p rákövetkezője fapont kovetkezo(fapont p) {
if (p.jobb!=nil) { //ha van jobb részfa
p=p.jobb ;
//akkor a jobb részfa
while (p.bal!=nil) p=p.bal; //bal szélső eleme
return p;
} else { // ha nincs jobb fiú
while (p.apa!=nil) {
// amíg van apa
if (p.apa.bal==p) // ha p bal gyerek
return p.apa; // p apja a rákövetkező
p=p.apa ; // megyünk felfelé p-vel
};
return nil ;
// nincs rákövetkező
} }
2012. február 8.
Törlés bináris keresőfából
p
2012. február 8.
q
p
21 void
}
2012. február 8.
torol(fapont p) { if (p.jobb!=nil) {
fapont q=kovetkezo(p) ; 29
p.key=q.key ; p.value=q.value ;
q.apa.bal=q.jobb ;
q.jobb.apa=q.apa ; q
delete q ; 24 } else { ... }
27
37 31
43
void torol(fapont p) {
if (p.jobb!=nil) {
fapont q=kovetkezo(p) ;
p.key=q.key ; p.value=q.value ;
q.apa.bal=q.jobb ;
q.jobb.apa=q.apa ;
delete q ;
} else {
if (p.apa.jobb==p) p.apa.jobb=p.bal ;
else p.apa.bal=p.bal ;
p.bal.apa=p.apa ;
delete p ;
} }
2012. február 8.
p
Elem törlése példa 21 9
29
4 1
2012. február 8.
17 13
24 20
37 27
31
43
Bináris fák tárolása csúcsonkét 2 pointer és egy bit, mely azt jelöli, hogy bal, vagy jobb gyerek 1. pointer • bal gyerek, ha létezik • jobb gyerek, ha csak az létezik. • nil: ha egyáltalán nincs gyereke. 2. pointer • ha ő maga bal gyerek, akkor a testvérre mutat, ha az létezik, különben a szülőre. • ha jobb gyerek: a szülőre mutat. • gyökérben nil
2012. február 8.
Fapont tárolása struct fapont
{
key ;
value ;
fapont fiu, tespa ;
boolean bal ; }
2012. február 8.
Bináris keresőfák jellemzői
•
p gyökerű részfa belső pontjainak száma int s(fapont p) {
if (p==nil) return 0 ;
return 1+s(p.bal)+s(p.jobb) ; }
•
p gyökerű részfa magassága int h(fapont p) {
if (p==nil) return 0 ;
return 1+Math.max(h(p.bal),h(p.jobb)) ; }
2012. február 8.
Véletlen építésű bináris keresőfa
•
Adott n egymástól különböző kulcs, melyekből bináris keresőfát építünk úgy, hogy a kulcsokat valamilyen sorrendben egymás után beszúrjuk a kezdetben üres fába.
•
Ha itt minden sorrend, vagyis az n kulcsnak mind az n! permutációja egyformán valószínű, akkor a kapott fát véletlen építésű bináris keresőfának nevezzük.
•
Tétel: Egy n különböző kulcsot tartalmazó véletlen építésű bináris keresőfa várható magassága O(log2n).
[2] 241-244
2012. február 8.
Optimális bináris keresőfa Adott kulcsoknak egy K=(k1,...,kn) sorozata Minden ki kulcshoz ismert annak pi előfordulási valószínűsége Minden di intervallumhoz ismert annak qi előfordulási valószínűsége, hogy arra az intervallumra keresünk (sikertelen keresésekhez)
Optimális bináris keresőfa építhető (pl. dinamikus programozás módszerével) 2 Építés: O(n )
[2] 314-321 2012. február 8.
Bináris fa inorder bejárása
function bejar(p){
if (p.bal!=nil) bejar(p.bal) ;
muvelet(p) ;
if (p.jobb!=nil) bejar(p.jobb) ; }
2012. február 8.
5
5
function bejar(p){
if (p.bal!=nil) bejar(p.bal) ;
muvelet(p) ;
if (p.jobb!=nil) bejar(p.jobb) ; }
3 1
7 4
6
37
function bejar(p){
if (p.bal!=nil) bejar(p.bal) ;
muvelet(p) ;
if (p.jobb!=nil) bejar(p.jobb) ; }
1 46
function bejar(p){
if (p.bal!=nil) bejar(p.bal) ;
muvelet(p) ;
if (p.jobb!=nil) bejar(p.jobb) ; }
2012. február 8.
rang(p) 1 2 3 4 5 6
1345 67
Rendezettminta-fa • Minden p ponthoz tároljuk p gyökerű fa belső pontjainak számát (méretét)
• Adott rangú elem keresése - T[r] • Adott elem rangjának meghatározása [2] 272-277
• Egyéb bővítési lehetőségek (pl. intervallumfák)
[2] 279-285 2012. február 8.
Példa 26 20
17
41
12
7
14
21
30
47
7
4
5
1
10
16
19
21
28
38
4
2
2
1
1
3
7
12
14
20
35
39
2
1
1
1
1
1
3 1 2012. február 8.
Adott rangú elem keresése 41 7
30
47
5
1
28
38
1
3
rmkeres(p,x) { 35 39
r=p.bal.meret+1 ; 1 1
if (x==r) return p ;
if (x
else return rmkeres(p.jobb,x-r) ; } 2012. február 8.
Elem rangjának meghatározása 41 7
28
30
47
5
1
38
1 3 rmrang(p) {
r=p.bal.meret+1 ; 35 39
y=x ; 1 1
while (y!=gyoker) {
if (y==y.apa.jobb) r+=y.apa.bal.meret+1;
y=y.apa ;
}
return r ; } 2012. február 8.
Méret információ fenntartása beszjav(p) {
while (p!=gyoker) {
p=p.apa;
p.meret++ ;
} } torljav(p) {
while (p!=gyoker) {
p=p.apa;
p.meret-- ;
} } 2012. február 8.
41 87
30
47
65
1
28
38
1
43
35
39
1
21
40 1
Fapont tárolása
első megközelítés, a gyakorlatban nem így tároljuk!
struct fapont{
int key, v, meret ;
fapont bal, jobb, apa ; } apa
key balfiu
2012. február 8.
v meret jobbfiu
Köszönöm a figyelmet!
Referenciák • [1] T. H. Cormen, C. E. Leiserson, R.L. Rivest: Algoritmusok, Műszaki Könyvkiadó, 2003. • [2] T. H. Cormen, C. E. Leiserson, R.L. Rivest, C. Stein: Új algoritmusok, Scolar Kiadó, 2003. • [3] T. Ottman, P. Widmayer: Algoritmen und Datenstrukturen, Wissenschaftsverlag, 1990
2012. február 8.
