Informatika1-2012/Eloadas4
A MathWikiből
A lap korábbi változatát látod, amilyen Tnemeth (vitalap | szerkesztései) 2012. október 4., 21:40-kor történt szerkesztése után volt.
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.
<p>Határérték:</p> <pre><code contenteditable style="margin-top: 20px;"><span style="color: #ff4040;">sage:</span> ((2**x - 1)/sin(x)).limit(x = 0) log(2)</code></pre>
<p>Derivált:</p> <pre><code contenteditable style="margin-top: 20px;"><span style="color: #ff4040;">sage:</span> (2**x - 1).derivative(x) 2^x*log(2)</code></pre>
<p>Ellenőrzés:</p> <pre><code contenteditable style="margin-top: 20px;"><span style="color: #ff4040;">sage:</span> (2**x - 1).derivative(x).subs(x=0) log(2)</code></pre>
Gráfok
Gráf: csúcsok (nodes), és a csúcsokat összekötő élek(edges) halmaza.
Például:
<img height="250" src="./images/graf1.png" alt="GRÁF1"> |
<code>V = 1, 2, 3, 4, 5, 6<br/> E = (1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6)</code> </td></tr> </table> <p>Python-ban a legegyszerűbben egy szótárban tárolhatjuk a gráfokat.</p> <code><table><tr><td style="text-align:right; vertical-align: top;">G = {'1'</td><td style="vertical-align: top;">: ['2', '5'],</td> <td width="200" height="200" rowspan="4" style="text-align:right;"><img height="250" src="./images/graf2.png" alt="GRÁF2"> </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;">'4'</td><td style="vertical-align: top;">: ['5', '6']}</td></tr></table></code> <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> <pre class="fragment"><code contenteditable style="margin-top: 20px;"><span style="color: #ff4040;">sage:</span> G = Graph({'1': ['2', '5'], '2': ['3', '5'], '3': ['4'], '4': ['5', '6']}) <span style="color: #ff4040;">sage:</span> G Graph on 6 vertices</code></pre> <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> <table><tr><td style="vertical-align: top;"><ul> <li style="list-style-type:none; text-indent: -1em;">- bármely csúcs alatti bal részfa csak a csúcsnál kisebb kulcsú elemeket tartalmaz</li> <li style="list-style-type:none; text-indent: -1em;" 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; text-indent: -1em;" class="fragment">- a bal és jobboldali részfa is bináris keresőfa</li> </ul> </td><td width="200" height="200" style="text-align:right;"><img height="250" src="./images/bst.png" alt="BST"></td></tr></table> <h1>Rekurzív algoritmus</h1> <p>A rekurzív algoritmusok három fontos összetevője:</p> <ul> <li style="list-style-type:none; text-indent: -1em;">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; text-indent: -1em;" class="fragment">Általános eset: ezt eggyel egyszerűbb esetre kell visszavezetni</li> <li style="list-style-type:none; text-indent: -1em;" class="fragment">Bizonyítani kell, hogy az általános esetből mindig el fogjuk érni valamelyik alapesetet (különben végtelen rekurzió lehet!)</li> </ul> <p>Bináris keresőfa rekurzív bejárása.<br/> Keressük meg, hogy van-e a fában 5 kulcsú elem!</p> <table><tr><td style="vertical-align: top;"><ul> <li style="list-style-type:none; text-indent: -1em;">- A gyökértől (legfelső elem) indulunk</li> <li style="list-style-type:none; text-indent: -1em;">- ha megtaláltuk a keresett kulcsot, visszatérünk (első alapeset)</li> <li style="list-style-type:none; text-indent: -1em;">- ha levélhez értünk, visszatérünk (második alapeset)</li> <li style="list-style-type:none; text-indent: -1em;">- ha a keresett kulcs kisebb, mint az aktuális csúcs értéke, akkor balra megyünk lefelé, ha nagyobb, akkor jobbra</li> </ul> </td><td width="200" height="200" style="text-align:right;"><img height="250" src="./images/bst.png" alt="BST"></td></tr></table> <pre><code contenteditable style="margin-top: 20px;">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)</code></pre> <h1>Egy klasszikus rekurzió példa</h1> <p>Fibonacci sorozat:</p> <code>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...</code> <p class="fragment">Feladat: írjunk Sage függvényt, ami visszaadja az n-edik Fibonacci-számot!</p> <p style="text-align:left;" class="fragment">Megoldás: Rekurzióval a legegyszerűbb a kód</p> <pre class="fragment"><code contenteditable style="margin-top: 20px;">def fibo_r(n): IF n==1 OR n==2: RETURN 1 ELSE: RETURN fibo_r(n-1) + fibo_r(n-2)</code></pre> <p>Jobb megoldás:<br/>a ciklusok hatékonyabbak! (Hosszabb kód)</p> <pre class="fragment"><code contenteditable style="margin-top: 20px;">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</code></pre> <h1>A két Fibonacci-megoldó függvény futásidejei:</h1> <table><tr><th style="border: 1px solid #777;">Bemenet (n)</th><th style="border: 1px solid #777;">For ciklussal</th><th style="border: 1px solid #777;">Rekurzióval</th></tr> <tr><td style="border: 1px solid #777;">10</td><td style="border: 1px solid #777;">0.020s</td><td style="border: 1px solid #777;">0.020s</td></tr> <tr><td style="border: 1px solid #777;">20</td><td style="border: 1px solid #777;">0.020s</td><td style="border: 1px solid #777;">0.034s</td></tr> <tr><td style="border: 1px solid #777;">30</td><td style="border: 1px solid #777;">0.021s</td><td style="border: 1px solid #777;">0.952s</td></tr> <tr><td style="border: 1px solid #777;">40</td><td style="border: 1px solid #777;">0.021s</td><td style="border: 1px solid #777;">1m 56.8s</td></tr> <tr><td style="border: 1px solid #777;">4000</td><td style="border: 1px solid #777;">0.023s</td><td style="border: 1px solid #777;">kb. 10<span style=" font-size:70%; vertical-align: 0.4em;">68</span> év</td></tr> <tr><td style="border: 1px solid #777;">400000</td><td style="border: 1px solid #777;">16.375s</td><td style="border: 1px solid #777;">kb. végtelen</td></tr></table> <p>További olvasnivalók<br/> (nem kell tudni, de hasznos és érdekes):</p> <ul> <li style="list-style-type:none; text-indent: -1em;">- Bináris keresőfa:<br/> http://en.wikipedia.org/wiki/Binary_search_tree</li> <li style="list-style-type:none; text-indent: -1em;">- Fibonacci számok:<br/> http://en.wikipedia.org/wiki/Fibonacci_number</li> <li style="list-style-type:none; text-indent: -1em;">- Algoritmusok futásidejéről:<br/> http://en.wikipedia.org/wiki/Time_complexity<br/> http://en.wikipedia.org/wiki/Big_O_notation</li> </ul> |