Informatika1-2012/Eloadas4

A MathWikiből
(Változatok közti eltérés)
(Ú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 …”)
 
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>
−
             <div class="fragment"><p>Határérték:</p>
+
             <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)
+
           <pre>sage: ((2**x - 1)/sin(x)).limit(x = 0)
−
log(2)</code></pre></div>
+
log(2)</pre>
−
           <div class="fragment"><p>Derivált:</p>
+
           <p>Derivált:</p>
−
           <pre><code contenteditable style="margin-top: 20px;"><span style="color: #ff4040;">sage:</span> (2**x - 1).derivative(x)
+
           <pre>sage: (2**x - 1).derivative(x)
−
2^x*log(2)</code></pre></div>
+
2^x*log(2)</pre>
−
           <div class="fragment"><p>Ellenőrzés:</p>
+
           <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)
+
           <pre>sage: (2**x - 1).derivative(x).subs(x=0)
−
log(2)</code></pre></div>
+
log(2)</pre>
 
          
 
          
 
           <h1>Gráfok</h1>
 
           <h1>Gráfok</h1>
39. sor: 39. 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"><code contenteditable style="margin-top: 20px;"><span style="color: #ff4040;">sage:</span> G = Graph({'1': ['2', '5'],
+
             <pre class="fragment"><code contenteditable style="margin-top: 20px;">sage: G = Graph({'1': ['2', '5'],
 
     '2': ['3', '5'],
 
     '2': ['3', '5'],
 
     '3': ['4'],
 
     '3': ['4'],
 
     '4': ['5', '6']})
 
     '4': ['5', '6']})
−
<span style="color: #ff4040;">sage:</span> G
+
sage: G
−
Graph on 6 vertices</code></pre>
+
Graph on 6 vertices</pre>
 
          
 
          
 
           <h1>Bináris keresőfák</h1>
 
           <h1>Bináris keresőfák</h1>
74. sor: 74. sor:
 
</td><td width="200" height="200" style="text-align:right;"><img height="250" src="./images/bst.png" alt="BST"></td></tr></table>
 
</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):
+
             <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: 84. sor:
 
         return search_bst(tree, left, key)
 
         return search_bst(tree, left, key)
 
     else:
 
     else:
−
         return search_bst(tree, right, key)</code></pre>
+
         return search_bst(tree, right, key)</pre>
 
          
 
          
 
           <h1>Egy klasszikus rekurzió példa</h1>
 
           <h1>Egy klasszikus rekurzió példa</h1>
96. sor: 96. sor:
 
         return 1
 
         return 1
 
     else:
 
     else:
−
         return fibo_r(n-1) + fibo_r(n-2)</code></pre>
+
         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>
108. sor: 108. sor:
 
         b=f
 
         b=f
 
         f=a+b
 
         f=a+b
−
     return f</code></pre>
+
     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>

A lap 2012. október 4., 22:15-kori változata

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:

<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;">sage: G = Graph({'1': ['2', '5'],
    '2': ['3', '5'],
    '3': ['4'],
    '4': ['5', '6']})
sage: G
Graph on 6 vertices</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>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)</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)</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</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>
A lap eredeti címe: „http://wiki.math.bme.hu/index.php?title=Informatika1-2012/Eloadas4&oldid=7847”
Személyes eszközök