1. óra
(2008.09.16.)
Az idei első nagyobb gondolati egység: kombinatorikus algoritmusok. Variációk, kombinációk, permutációk, partíciók, fák, gráfok szerepelnek majd a feladatokban.
A Mester (
D. E. Knuth) nyomán a következő kérdéseket fogjuk vizsgálni az egyes kombinatorikai objektumoknál:
- Létezés: Van-e valamilyen feltételeknek megfelelő $X$ objektum?
- Konstrukció: Ha van, hogyan lehet ilyet gyorsan találni?
- Megszámlálás: Hány különböző ilyen $X$ létezik?
- Generálás: Hogyan lehet az összes megfelelő $X_1, X_2, X_3, \ldots$ objektumot bejárni?
- Optimalizáció: Melyik $X_i$-re lesz $f(X)$ maximális vagy minimális?
Ismétléses variációk
Első órán a legegyszerűbb esettel foglalkozunk: hogyan lehet előállítani az $n$ hosszúságú 0-1 sorozatokat. Egy iteratív és egy rekurzív megoldást adunk.
Számolás kettes számrendszerben
A 0-1 sorozatot egy kettes számrendszerbeli számnak fogjuk fel. A csupa nulla sorozatból indulunk, és mindig növeljük eggyel a "számot". A növelés úgy történik, hogy a legkisebb helyiértéken növelünk, majd végigkövetjük az esetleges átviteleket.
a[1..n] := 0
Ciklus 2^n-szer
bejárás( a[ ] )
i := 1
Ciklus
c := (a[i] + 1) div 2
a[i] := (a[i] + 1) mod 2
i := i + 1
amíg c > 0
Ciklus vége
Ciklus vége
Ha jobban megfigyeljük, mi történik kettes számrendszerben, az eggyel növeléskor, kaphatunk egy másik változatot: az eggyel növelés minden egyből nullát "csinál" az első nulláig, amit egyesre vált.
a[1..n] := 0
Ciklus
bejár( a [ ] )
amíg (Növel())
Ciklus vége
Függvény Növel
i := 1
Ciklus amíg a[i] = 1 és i <= n
a[i] := 0
i := i + 1
Ciklus vége
Ha i <= n
akkor
a[i] = 1
Növel := igaz
különben
Növel := hamis
Elágazás vége
Függvény vége
Rekurzív felsorolás
Az első üres helyre beírunk 0-t és 1-et is, és mindkét esetben feltöltjük a többi üre helyet egy rekurzív hívással.
Eljárás rek(i)
Ha i = 0 akkor bejár( a[ ] )
különben
a[i] := 0; rek(i-1)
a[i] := 1; rek(i-1)
Elágazás vége
Eljárás vége
A generálás a következő hívással kell indítani:
rek(n)
Feladat
