Informatika1-2012/Eloadas4
(Új oldal, tartalma: „ <h1>Max, min keresése</h1> <p>Maximumot vagy minimumot is kereshetünk numerikusan. Ez is feltételezi, hogy a bemenet egy egyváltozós …”) |
|||
(egy szerkesztő 4 közbeeső változata nincs mutatva) | |||
2. sor: | 2. sor: | ||
<p>Maximumot vagy minimumot is kereshetünk numerikusan. Ez is feltételezi, hogy a bemenet egy egyváltozós | <p>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.</p> | folytonos függvény, és egy lokális maximumot keres meg közelítőleg.</p> | ||
− | <p><code class="fragment">find_local_maximum(start, end)</code> | + | <p><code class="fragment">find_local_maximum(start, end)</code><br/> |
<code class="fragment">find_local_minimum(start, end)</code></p> | <code class="fragment">find_local_minimum(start, end)</code></p> | ||
<h1>Határérték, derivált</h1> | <h1>Határérték, derivált</h1> | ||
<p>Kiszámíthatjuk egy kifejezés határértékét egy pontban, vagy a deriváltját, határérték.</p> | <p>Kiszámíthatjuk egy kifejezés határértékét egy pontban, vagy a deriváltját, határérték.</p> | ||
− | + | <p>Határérték:</p> | |
− | <pre | + | <pre>sage: ((2**x - 1)/sin(x)).limit(x = 0) |
− | log(2) | + | log(2)</pre> |
− | + | <p>Derivált:</p> | |
− | <pre | + | <pre>sage: (2**x - 1).derivative(x) |
− | 2^x*log(2) | + | 2^x*log(2)</pre> |
− | + | <p>Ellenőrzés:</p> | |
− | <pre | + | <pre>sage: (2**x - 1).derivative(x).subs(x=0) |
− | log(2) | + | log(2)</pre> |
<h1>Gráfok</h1> | <h1>Gráfok</h1> | ||
22. sor: | 22. sor: | ||
Például:</p> | Például:</p> | ||
<table> | <table> | ||
− | <tr><td | + | <tr><td> |
− | </td><td | + | [https://docs.google.com/open?id=0Bwk5mjaCfPlVRUtpYWVWaDk4OGs Gráf1] |
− | + | <!-- <img height="250" src="./images/graf1.png" alt="GRÁF1"/> --> | |
− | E = (1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6) | + | </td><td> |
+ | V = 1, 2, 3, 4, 5, 6<br/> | ||
+ | E = (1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6) | ||
</td></tr> | </td></tr> | ||
</table> | </table> | ||
<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;">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"> --> | ||
</td></tr> | </td></tr> | ||
<tr><td style="text-align:right; vertical-align: top;">'2'</td><td style="vertical-align: top;">: ['3', '5'],</td></tr> | <tr><td style="text-align:right; vertical-align: top;">'2'</td><td style="vertical-align: top;">: ['3', '5'],</td></tr> | ||
<tr><td style="text-align:right; vertical-align: top;">'3'</td><td style="vertical-align: top;">: ['4'],</td></tr> | <tr><td style="text-align:right; vertical-align: top;">'3'</td><td style="vertical-align: top;">: ['4'],</td></tr> | ||
− | <tr><td style="text-align:right; vertical-align: top;">'4'</td><td style="vertical-align: top;">: ['5', '6']}</td></tr></table | + | <tr><td style="text-align:right; vertical-align: top;">'4'</td><td style="vertical-align: top;">: ['5', '6']}</td></tr></table> |
<p class="fragment">Ha irányítatlan gráfot szeretnénk, akkor mindkét irányítással vegyük fel az éleket!</p> | <p class="fragment">Ha irányítatlan gráfot szeretnénk, akkor mindkét irányítással vegyük fel az éleket!</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> | <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'], | ||
'4': ['5', '6']}) | '4': ['5', '6']}) | ||
− | + | sage: G | |
− | Graph on 6 vertices | + | Graph on 6 vertices</pre> |
<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"> --> | ||
+ | </td></tr></table> | ||
<h1>Rekurzív algoritmus</h1> | <h1>Rekurzív algoritmus</h1> | ||
59. sor: | 66. sor: | ||
<p>A rekurzív algoritmusok három fontos összetevője:</p> | <p>A rekurzív algoritmusok három fontos összetevője:</p> | ||
<ul> | <ul> | ||
− | <li style="list-style-type:none | + | <li style="list-style-type:none;">Alapeset: a legegyszerűbb, redukált eset, amire triviális a megoldás és visszatérhetünk vele</li> |
− | <li style="list-style-type:none; | + | <li style="list-style-type:none;">Általános eset: ezt eggyel egyszerűbb esetre kell visszavezetni</li> |
− | <li style="list-style-type:none; | + | <li style="list-style-type:none;">Bizonyítani kell, hogy az általános esetből mindig el fogjuk érni valamelyik alapesetet (különben végtelen rekurzió lehet!)</li> |
</ul> | </ul> | ||
67. sor: | 74. sor: | ||
Keressük meg, hogy van-e a fában 5 kulcsú elem!</p> | Keressük meg, hogy van-e a fában 5 kulcsú elem!</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;">A gyökértől (legfelső elem) indulunk</li> |
− | <li style="list-style-type:none | + | <li style="list-style-type:none;">ha megtaláltuk a keresett kulcsot, visszatérünk (első alapeset)</li> |
− | <li style="list-style-type:none | + | <li style="list-style-type:none;">ha levélhez értünk, visszatérünk (második alapeset)</li> |
− | <li style="list-style-type:none | + | <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"> --> | ||
+ | </td></tr></table> | ||
− | <pre | + | <pre>def search_bst(tree, node, key): |
if node == key: # 1. alapeset: megvan | if node == key: # 1. alapeset: megvan | ||
return True | return True | ||
84. sor: | 94. sor: | ||
return search_bst(tree, left, key) | return search_bst(tree, left, key) | ||
else: | else: | ||
− | return search_bst(tree, right, key) | + | return search_bst(tree, right, key)</pre> |
<h1>Egy klasszikus rekurzió példa</h1> | <h1>Egy klasszikus rekurzió példa</h1> | ||
90. 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 | ||
else: | else: | ||
− | return fibo_r(n-1) + fibo_r(n-2) | + | return fibo_r(n-1) + fibo_r(n-2)</pre> |
<p>Jobb megoldás:<br/>a ciklusok hatékonyabbak! (Hosszabb kód)</p> | <p>Jobb megoldás:<br/>a ciklusok hatékonyabbak! (Hosszabb kód)</p> | ||
− | <pre class="fragment | + | <pre class="fragment">def fibo_for(n): |
if n==1 or n==2: | if n==1 or n==2: | ||
return 1 | return 1 | ||
108. sor: | 118. sor: | ||
b=f | b=f | ||
f=a+b | f=a+b | ||
− | return f | + | return f</pre> |
<h1>A két Fibonacci-megoldó függvény futásidejei:</h1> | <h1>A két Fibonacci-megoldó függvény futásidejei:</h1> | ||
122. sor: | 132. sor: | ||
(nem kell tudni, de hasznos és érdekes):</p> | (nem kell tudni, de hasznos és érdekes):</p> | ||
<ul> | <ul> | ||
− | <li style="list-style-type:none | + | <li style="list-style-type:none;">Bináris keresőfa:<br/> |
http://en.wikipedia.org/wiki/Binary_search_tree</li> | http://en.wikipedia.org/wiki/Binary_search_tree</li> | ||
− | <li style="list-style-type:none | + | <li style="list-style-type:none;">Fibonacci számok:<br/> |
http://en.wikipedia.org/wiki/Fibonacci_number</li> | http://en.wikipedia.org/wiki/Fibonacci_number</li> | ||
− | <li style="list-style-type:none | + | <li style="list-style-type:none;">Algoritmusok futásidejéről:<br/> |
http://en.wikipedia.org/wiki/Time_complexity<br/> | http://en.wikipedia.org/wiki/Time_complexity<br/> | ||
http://en.wikipedia.org/wiki/Big_O_notation</li> | http://en.wikipedia.org/wiki/Big_O_notation</li> | ||
</ul> | </ul> |
A lap jelenlegi, 2012. október 7., 22: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