Informatika1-2012/Eloadas4
41. sor: | 41. sor: | ||
<p>Sage-ben létezik egy <code>Graph</code> osztály. A <code>Graph</code> objektumok segítségével irányítatlan gráfokkal dolgozhatunk.</p> | <p>Sage-ben létezik egy <code>Graph</code> osztály. A <code>Graph</code> objektumok segítségével irányítatlan gráfokkal dolgozhatunk.</p> | ||
− | <pre class="fragment | + | <pre class="fragment">sage: G = Graph({'1': ['2', '5'], |
'2': ['3', '5'], | '2': ['3', '5'], | ||
'3': ['4'], | '3': ['4'], | ||
51. sor: | 51. sor: | ||
<p>A bináris keresőfa (binary search tree, BST) olyan adatstruktúra, amely a következő tulajdonságokkal rendelkezik:</p> | <p>A bináris keresőfa (binary search tree, BST) olyan adatstruktúra, amely a következő tulajdonságokkal rendelkezik:</p> | ||
<table><tr><td style="vertical-align: top;"><ul> | <table><tr><td style="vertical-align: top;"><ul> | ||
− | <li style="list-style-type:none | + | <li style="list-style-type:none;">- bármely csúcs alatti bal részfa csak a csúcsnál kisebb kulcsú elemeket tartalmaz</li> |
− | <li style="list-style-type:none | + | <li style="list-style-type:none;" class="fragment">- bármely csúcs alatti jobb részfa csak a csúcsnál nagyobb kulcsú elemeket tartalmaz</li> |
− | <li style="list-style-type:none | + | <li style="list-style-type:none;" class="fragment">- a bal és jobboldali részfa is bináris keresőfa</li> |
</ul> | </ul> | ||
</td><td width="200" height="200" style="text-align:right;"> | </td><td width="200" height="200" style="text-align:right;"> |
A lap 2012. október 5., 17:41-kori változata
Tartalomjegyzék |
Max, min keresése
Maximumot vagy minimumot is kereshetünk numerikusan. Ez is feltételezi, hogy a bemenet egy egyváltozós folytonos függvény, és egy lokális maximumot keres meg közelítőleg.
find_local_maximum(start, end)
find_local_minimum(start, end)
Határérték, derivált
Kiszámíthatjuk egy kifejezés határértékét egy pontban, vagy a deriváltját, határérték.
Határérték:
sage: ((2**x - 1)/sin(x)).limit(x = 0) log(2)
Derivált:
sage: (2**x - 1).derivative(x) 2^x*log(2)
Ellenőrzés:
sage: (2**x - 1).derivative(x).subs(x=0) log(2)
Gráfok
Gráf: csúcsok (nodes), és a csúcsokat összekötő élek(edges) halmaza.
Például:
V = 1, 2, 3, 4, 5, 6 |
Python-ban a legegyszerűbben egy szótárban tárolhatjuk a gráfokat.
G = {'1' | : ['2', '5'], | |
'2' | : ['3', '5'], | |
'3' | : ['4'], | |
'4' | : ['5', '6']} |
Ha irányítatlan gráfot szeretnénk, akkor mindkét irányítással vegyük fel az éleket!
Sage-ben létezik egy Graph
osztály. A Graph
objektumok segítségével irányítatlan gráfokkal dolgozhatunk.
sage: G = Graph({'1': ['2', '5'], '2': ['3', '5'], '3': ['4'], '4': ['5', '6']}) sage: G Graph on 6 vertices
Bináris keresőfák
A bináris keresőfa (binary search tree, BST) olyan adatstruktúra, amely a következő tulajdonságokkal rendelkezik:
|
Rekurzív algoritmus
A rekurzív algoritmusok három fontos összetevője:
- Alapeset: a legegyszerűbb, redukált eset, amire triviális a megoldás és visszatérhetünk vele
- Általános eset: ezt eggyel egyszerűbb esetre kell visszavezetni
- Bizonyítani kell, hogy az általános esetből mindig el fogjuk érni valamelyik alapesetet (különben végtelen rekurzió lehet!)
Bináris keresőfa rekurzív bejárása.
Keressük meg, hogy van-e a fában 5 kulcsú elem!
|
def search_bst(tree, node, key): if node == key: # 1. alapeset: megvan return True if node not in tree: # 2. alapeset: nincs return False # rekurzív hívás balra vagy jobbra (left, right) = tree[node] if node > key: return search_bst(tree, left, key) else: return search_bst(tree, right, key)
Egy klasszikus rekurzió példa
Fibonacci sorozat:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Feladat: írjunk Sage függvényt, ami visszaadja az n-edik Fibonacci-számot!
Megoldás: Rekurzióval a legegyszerűbb a kód
def fibo_r(n): if n==1 or n==2: return 1 else: return fibo_r(n-1) + fibo_r(n-2)
Jobb megoldás:
a ciklusok hatékonyabbak! (Hosszabb kód)
def fibo_for(n): if n==1 or n==2: return 1 a=1; b=1 f=a+b for i in range(n-3): a=b b=f f=a+b return f
A két Fibonacci-megoldó függvény futásidejei:
Bemenet (n) | For ciklussal | Rekurzióval |
---|---|---|
10 | 0.020s | 0.020s |
20 | 0.020s | 0.034s |
30 | 0.021s | 0.952s |
40 | 0.021s | 1m 56.8s |
4000 | 0.023s | kb. 1068 év |
400000 | 16.375s | kb. végtelen |
További olvasnivalók
(nem kell tudni, de hasznos és érdekes):
- Bináris keresőfa:
http://en.wikipedia.org/wiki/Binary_search_tree - Fibonacci számok:
http://en.wikipedia.org/wiki/Fibonacci_number - Algoritmusok futásidejéről:
http://en.wikipedia.org/wiki/Time_complexity
http://en.wikipedia.org/wiki/Big_O_notation