Informatika1-2012/Eloadas4
(egy szerkesztő 2 közbeeső változata nincs mutatva) | |||
22. sor: | 22. sor: | ||
Például:</p> | Például:</p> | ||
<table> | <table> | ||
− | <tr><td | + | <tr><td> |
+ | [https://docs.google.com/open?id=0Bwk5mjaCfPlVRUtpYWVWaDk4OGs Gráf1] | ||
<!-- <img height="250" src="./images/graf1.png" alt="GRÁF1"/> --> | <!-- <img height="250" src="./images/graf1.png" alt="GRÁF1"/> --> | ||
− | </td><td | + | </td><td> |
V = 1, 2, 3, 4, 5, 6<br/> | V = 1, 2, 3, 4, 5, 6<br/> | ||
E = (1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6) | E = (1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6) | ||
31. sor: | 32. sor: | ||
<p>Python-ban a legegyszerűbben egy szótárban tárolhatjuk a gráfokat.</p> | <p>Python-ban a legegyszerűbben egy szótárban tárolhatjuk a gráfokat.</p> | ||
− | <table><tr><td style="text-align:right | + | <table><tr><td style="text-align:right;">G = {'1'</td><td>: ['2', '5'],</td> |
− | <td | + | <td rowspan="4" style="text-align:right;"> |
+ | [https://docs.google.com/open?id=0Bwk5mjaCfPlVNWxJb2hIVHVYSkE Gráf2] | ||
<!-- <img height="250" src="./images/graf2.png" alt="GRÁF2"> --> | <!-- <img height="250" src="./images/graf2.png" alt="GRÁF2"> --> | ||
</td></tr> | </td></tr> | ||
41. sor: | 43. 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'], | ||
50. sor: | 52. sor: | ||
<h1>Bináris keresőfák</h1> | <h1>Bináris keresőfák</h1> | ||
<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 | + | <table><tr><td><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 | + | </td><td> |
+ | [https://docs.google.com/open?id=0Bwk5mjaCfPlVZ01uQ0ZXNmJQYUk BST] | ||
<!-- <img height="250" src="./images/bst.png" alt="BST"> --> | <!-- <img height="250" src="./images/bst.png" alt="BST"> --> | ||
</td></tr></table> | </td></tr></table> | ||
76. sor: | 79. sor: | ||
<li style="list-style-type:none;">ha a keresett kulcs kisebb, mint az aktuális csúcs értéke, akkor balra megyünk lefelé, ha nagyobb, akkor jobbra</li> | <li style="list-style-type:none;">ha a keresett kulcs kisebb, mint az aktuális csúcs értéke, akkor balra megyünk lefelé, ha nagyobb, akkor jobbra</li> | ||
</ul> | </ul> | ||
− | </td><td | + | </td><td> |
+ | [https://docs.google.com/open?id=0Bwk5mjaCfPlVZ01uQ0ZXNmJQYUk BST] | ||
<!-- <img height="250" src="./images/bst.png" alt="BST"> --> | <!-- <img height="250" src="./images/bst.png" alt="BST"> --> | ||
</td></tr></table> | </td></tr></table> | ||
96. sor: | 100. sor: | ||
<code>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...</code> | <code>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...</code> | ||
− | <p | + | <p>Feladat: írjunk Sage függvényt, ami visszaadja az n-edik Fibonacci-számot!</p> |
− | <p style="text-align:left; | + | <p style="text-align:left;">Megoldás: Rekurzióval a legegyszerűbb a kód</p> |
− | <pre | + | <pre>def fibo_r(n): |
if n==1 or n==2: | if n==1 or n==2: | ||
return 1 | return 1 |
A lap jelenlegi, 2012. október 7., 23:25-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