Informatika1-2012/Eloadas4

A MathWikiből
A lap korábbi változatát látod, amilyen Tnemeth (vitalap | szerkesztései) 2012. október 5., 16:41-kor történt szerkesztése után volt.

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
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'],
'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

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