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 …”)
 
 
(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>
             <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>
22. sor: 22. sor:
 
               Például:</p>
 
               Például:</p>
 
  <table>
 
  <table>
  <tr><td width="200" height="200" ><img height="250" src="./images/graf1.png" alt="GRÁF1">
+
  <tr><td>
  </td><td style="vertical-align: top;">
+
[https://docs.google.com/open?id=0Bwk5mjaCfPlVRUtpYWVWaDk4OGs Gráf1]
             <div style="text-align:left;" class="fragment"><code>V = 1, 2, 3, 4, 5, 6<br/>
+
<!-- <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)</code>
+
  </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>
             <code><table><tr><td style="text-align:right; vertical-align: top;">G = {'1'</td><td style="vertical-align: top;">: ['2', '5'],</td>
+
             <table><tr><td style="text-align:right;">G = {'1'</td><td>: ['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 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></code>
+
                 <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"><code contenteditable style="margin-top: 20px;"><span style="color: #ff4040;">sage:</span> G = Graph({'1': ['2', '5'],
+
             <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']})
<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>
 
           <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><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;">- 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;" 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>
+
             <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;"><img height="250" src="./images/bst.png" alt="BST"></td></tr></table>
+
</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; 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;">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;">Á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>
+
               <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; text-indent: -1em;">- A gyökértől (legfelső elem) indulunk</li>
+
               <li style="list-style-type:none;">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;">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;">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>
+
               <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 width="200" height="200" style="text-align:right;"><img height="250" src="./images/bst.png" alt="BST"></td></tr></table>
+
</td><td>
 +
[https://docs.google.com/open?id=0Bwk5mjaCfPlVZ01uQ0ZXNmJQYUk BST]
 +
<!-- <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: 94. 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>
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 class="fragment">Feladat: írjunk Sage függvényt, ami visszaadja az n-edik Fibonacci-számot!</p>
+
           <p>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>
+
             <p style="text-align:left;">Megoldás: Rekurzióval a legegyszerűbb a kód</p>
           <pre class="fragment"><code contenteditable style="margin-top: 20px;">def fibo_r(n):
+
           <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)</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>
           <pre class="fragment"><code contenteditable style="margin-top: 20px;">def fibo_for(n):
+
           <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</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>
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; text-indent: -1em;">- Bináris keresőfa:<br/>
+
               <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; text-indent: -1em;">- Fibonacci számok:<br/>
+
               <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; text-indent: -1em;">- Algoritmusok futásidejéről:<br/>
+
               <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:

Gráf1

           V = 1, 2, 3, 4, 5, 6
E = (1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6)

Python-ban a legegyszerűbben egy szótárban tárolhatjuk a gráfokat.

G = {'1': ['2', '5'],

Gráf2

'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:

  • - bármely csúcs alatti bal részfa csak a csúcsnál kisebb kulcsú elemeket tartalmaz
  • - bármely csúcs alatti jobb részfa csak a csúcsnál nagyobb kulcsú elemeket tartalmaz
  • - a bal és jobboldali részfa is bináris keresőfa

BST

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!

  • A gyökértől (legfelső elem) indulunk
  • ha megtaláltuk a keresett kulcsot, visszatérünk (első alapeset)
  • ha levélhez értünk, visszatérünk (második alapeset)
  • ha a keresett kulcs kisebb, mint az aktuális csúcs értéke, akkor balra megyünk lefelé, ha nagyobb, akkor jobbra

BST

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 ciklussalRekurzióval
100.020s0.020s
200.020s0.034s
300.021s0.952s
400.021s1m 56.8s
40000.023skb. 1068 év
40000016.375skb. végtelen

További olvasnivalók
(nem kell tudni, de hasznos és érdekes):

Személyes eszközök