Informatika | Tanulmányok, esszék » Iványi Antal - Informatikai algoritmusok I.

INFORMATIKAI ALGORITMUSOK I. Elektronikus tankönyv ELTE Informatikai Kar, Budapest, 2005 Iványi Antal alkotó szerkeszt® INFORMATIKAI ALGORITMUSOK I. ELTE Informatikai Kar, Budapest, 2005 A könyv az Oktatási Minisztérium támogatásával, a  Felsooktatási Pályázatok Irodája által lebonyolított  felsooktatási tankönyvtámogatási program keretében készült.  Iványi Antal Alkotó szerkeszto:  Szerzok: Kása Zoltán (1.), Járai Antal és Kovács Attila (2), Jörg Rothe (3 és 4), Gyires Tibor (5.), Iványi Antal és Claudia Leopold (6), Eberhard Zehendner (7), Szidarovszky Ferenc (8.), Vizvári Béla (9), Ulrich Tamm (10), Balogh Ádám és Iványi Antal (11.), Demetrovics János és Sali Attila (12), Miklós István (13.), Ingo Althöfer és Stefan Schwartz (14), Szirmay-Kalos László (15), Elek István és Sidló Csaba (16.), Galántai Aurél és Jeney András (17) Szakmai lektorok: Ivanyos Gábor (2.), Gonda János (3), Rónyai Lajos (4),  (6.

és 7), Mayer János (8), Csirik János (9), Fridli Sándor (10), Sima Dezso Varga László (11.), Kiss Attila (12), Katsányi István (13), Szántai Tamás (14.), Vida János (15), Meskó Attila (16), Szántai Tamás (17) Nyelvi lektor: Biró Gabriella Fordítók: Láng Zsuzsa (3.), Sidló Csaba (4), Roszik János és Sztrik János (5), Szakács Laura (7), Pintér Miklós (8.), Sike Sándor (10), Belényesi Viktor és Nikovits Tibor (14) A könyv címoldalán – a Szépmuvészeti  Múzeum engedélyével és az ELTE Informatikai Karának támogatásával – Vasarely Victor Dirac címu  festménye látható. A borítóhoz felhasznált lmet a GOMA RT. bocsátotta rendelkezésünkre A borítót Iványi Antal tervezte c Ingo Althöfer, Balogh Ádám, Belényesi Viktor, Biró Gabriella, Csirik János, Demetrovics János, Elek István, Fridli Sándor, Galántai Aurél, Gonda János, Gyires Tibor, Iványi Anna, Iványi Antal, Ivanyos Gábor, Járai Antal, Jeney András, Katsányi István,

Kása Zoltán, Kovács Attila, Láng Zsuzsa, Claudia Leopold, Locher Kornél, Mayer János, Meskó Attila, Miklós István, Nikovits Tibor, Pintér Miklós, Roszik János, Rónyai Lajos, Jörg Rothe, Sali Attila, Stefan Schwarz, Sidló Csaba, Sima  Sike Sándor, Szakács Laura, Szántai Tamás, Szidarovszky Ferenc, Szirmay-Kalos László, Dezso, Sztrik János, Ulrich Tamm, Varga László, Vida János, Vizvári Béla, Eberhard Zehendner, 2004 ISBN: 963 ??? ??? ? Kiadja az ELTE Informatikai Kara 1117 Budapest, Pázmány Péter sétány 1/C. Telefon: 381-2139, Fax: 381-2140 Honlap: http://www.infeltehu/ Elektronikus cím: itcs@inf.eltehu  kiadó: Kozma László Felelos El®szó Az informatikai algoritmusok magyar nyelvu  szakirodalma az utóbbi huszonöt évben ala szakkönyvet Lovász László és Gács Péter írta 1978-ban [13]. Ezt a könyvet kult ki. Az elso fordítások követték: 1982-ben Aho, Hopcroft és Ullman [1] könyve, 1987-ben Knuth háromkötetes monográája

[10, 11, 12], majd 1987-ben Cormen, Leiserson és Rivest muve   következtek – Rónyai Lajos, Ivanyos Gábor és Szabó Réka [2]. 1999-ben újra hazai szerzok [17] – majd 2002-ben megjelent Lynch Osztott algoritmusok címu  monográája [15]. Ezt 2003 tavaszán Iványi Antal Párhuzamos algoritmusok címu  könyve [8], majd 2003  oszén – Új algoritmusok címmel – Cormen, Leiserson, Rivest és Stein tankönyvének [3] fordítása követte.  A magyar informatikus hallgatók és gyakorlati szakemberek nagy érdeklodéssel fogadták az Új algoritmusokat – néhány hónap alatt a kiadott 2000 példány fele gazdára talált.  Ez ösztönözte ennek a könyvnek a hazai szerzoit, hogy – külföldi kollégáik segítségével – további informatikai területek algoritmusait is összefoglalják. A könyv tartalmát hat részre tagoljuk: Alapok, Hálózatok, Diszkrét optimalizálás, Folytonos optimalizálás, Adatbázisok és Alkalmazások.  kötetbe azok a fejezetek

került, amelyek szeptemberig elkészültek. Minden Az elso fejezet bemutat egy alkalmazási vagy elméleti szempontból lényeges területet és azokhoz kapcsolódó algoritmusokat. Az algoritmusok többségét szóban és olyan pszeudokóddal is  olvasók számára könnyen értmegadjuk, amely a programozási tapasztalattal rendelkezo  heto.  kötet 247 ábrát, 157 pszeudokódot és 133 példát tartalmaz, amelyek elosegítik  Az elso a tárgyalt algoritmusok muködésének  megértését. Az önálló tanulást az alfejezetek végén  gyakorlatok (összesen 269), az egyes témákban való elmélyülést pedig a fejezetek vélévo  (összesen 66) feladatok segítik. A fejezetek anyagával kapcsolatos friss és kiegégén lévo  ismeretekre való utalások találhatók a fejezetek végén lévo  Megjegyzések a fejezethez szíto címu  részben. Az Irodalomjegyzékben megadjuk egyrészt a felhasznált szakirodalom bibliográai adatait, másrészt – teljességre törekedve

– felsoroljuk a magyar nyelvu  forrásokat.  honlapra való ugráshoz. KüAz irodalomjegyzék számos eleme felhasználható a megfelelo lön részben szerepel a könyvben használt szakkifejezések angol-magyar és magyar-angol szótára, valamint a jelölések listája. A könyvet Névmutató és Tárgymutató zárja    és memóAz algoritmusok bemutatása az igényelt eroforrások – elsosorban futási ido  korlátoria – elemzését is magában foglalja. A szakirodalomban szokásos módon felso  eroforrásigényre,  kat adunk meg a legrosszabb esetre jellemzo és esetenként a megoldandó   alsó korlátot is levezetünk. probléma eroforrásigényére jellemzo 6 El®szó AT X kiadványszerkeszto  eszköz segítségével készítettük, amelyet A könyv kéziratát HL E az elmúlt hat év során Belényesi Viktorral és Locher Kornéllal fejlesztettünk ki, és korábban  már három könyv kéziratának eloállítására használtunk. Az ábrák többségét

Locher Kornél  rajzolta. Az irodalomjegyzéket Iványi Anna tette élové Garey és Johnson klasszikus muvét  [5] követve mindazon algoritmusok futási idejét  korlát. exponenciálisnak nevezzük, amelyekre nem adható polinomiális felso Az Új algoritmusok példáját követve tizedespontot használunk. Mindig különös gondot fordítunk könyveink külsejére. Az adott esetben olyan megoldást kerestünk, amely •  kötet 17 és a második kötet hasonló számú tükrözi a könyv tartalmi gazdagságát (az elso fejezetét) •  és az alkotók szoros kötodését mind Magyarországhoz, mind pedig Európához.  Úgy gondoljuk, hogy a pécsi születésu  Vásárhelyi Viktor – aki francia festoként Victor  a formák és színek gazdagsága, életútja Vasarely néven vált világhíruvé  – képeire jellemzo  pedig tükrözi kultúránk európai kötodését. A budapesti és pécsi múzeumokban összesen közel 500 Vasarely-alkotás van. Ezek a  muvész 

ajándékai – a szüloföld iránti hála és tisztelet szimbólumai. Vasarely gazdag élet a könyv alkotói és majdani olvasói segítségével választottunk A szavazók a Dirac, muvéb  ol Kubtuz, Rikka, Sixa és a Tupa-fond címu  képeket emelték ki. Közülük két olyan képet – a Dirac és a Kubtuz címu  festményeket – választottuk, amelyeken szakaszokból kör alakul ki  tulajdonságát, hogy a folytonos valós világot – szemléltetve az informatika azon alapveto diszkrét objektumokkal (bitekkel) írja le – és amelyekhez sikerült felhasználási engedélyt kapnunk. Közismert, hogy az elmúlt évszázadban nemcsak muvészeink,  hanem sok kiváló tudósunk is külföldön ért fel a csúcsra. Nagy részükre azonban folyamatosan számíthat a hazai  oktatás és tudományos élet. A hálózati szimulációs fejezet szerzoje Gyires Tibor (Illinois Egyetem), a játékelméleti fejezetet pedig Szidarovszky Ferenc (Arizonai Muszaki  Egyetem) írta. A

második kötetben a megbízhatóságról szóló fejezetet Gács Péter (Bostoni Egyetem)   szóló fejezet egyik szerzoje  írta, a belsopontos módszerekrol pedig Terlaky Tamás (McMas az adott terület vezeto  kutatója, amerikai egyetemek ter Egyetem). Ma mind a négy szerzo professzora – egykor magyar egyetemen tanultak, majd tanítottak.  A rekurziós fejezet szerzoje Kása Zoltán (Babeş-Bolyai Tudományegyetem), a sziszto szóló fejezetet Szakács Laura (Babeş-Bolyai Tudományegyetem) fordílikus rendszerekrol  magyarra. Részvételük a könyv megszületésében a határainkon túli magyar totta németrol nyelvu  oktatással való szoros kapcsolatunk része.  Könyvünk tartalmi gazdagsága jó külföldi – elsosorban német – kapcsolatainknak  Az elso  kötet kriptográai és bonyolultságelméleti fejezetét Jörg Rothe is köszönheto. (Düsseldor Egyetem), szisztolikus rendszerekkel foglalkozó fejezetét Eberhard Zehendner  (Friedrich Schiller

Egyetem) írta. Az adattömörítési fejezet szerzoje Ulrich Tamm (Chem nitzi Egyetem), a párhuzamos programozásról szóló fejezet egyik szerzoje Claudia Leopold  Ingo Althöfer (Kasseli Egyetem), az ember-gép kapcsolatokkal foglalkozó fejezet szerzoi és Stefan Schwartz (Friedrich Schiller Egyetem).   Az alkotók (szerzok, lektorok, fordítók és segítotársaik) többsége a hazai informatikai  felsooktatás meghatározó intézményeinek – Budapesti Corvinus Egyetem, Budapesti Mu  szaki és Gazdaságtudományi Egyetem, Budapesti Muszaki  Foiskola, Debreceni Egyetem, El®szó 7 Eötvös Loránd Tudományegyetem, Miskolci Egyetem, Pécsi Tudományegyetem, Szegedi Tudományegyetem – oktatója.   Az Oktatási Minisztérium támogatásának köszönhetoen ez a tankönyv nagyon kedvezo áron juthat el az Olvasókhoz. Ugyancsak az Oktatási Minisztérium támogatásának köszön hogy 2005 tavaszától a könyv elektronikus változata is mindenki számára

szabadon heto,  lesz. hozzáférheto Az alábbi kollégáknak köszönjük, hogy a tervezett könyv mindkét formáját támogatták: Fazekas Gábor egyetemi docens (Debreceni Egyetem Informatikai Karának dékánhelyettese), Imreh Balázs egyetemi docens (Szegedi Egyetem), Kása Zoltán egyetemi tanár (BBTE Matematikai és Informatikai Karának dékánhelyettese), Kozma László egyetemi docens (ELTE Informatikai Karának dékánja), Jörg Rothe egyetemi tanár (Heinrich Heine  foiskolai   Universität, Düsseldorf), Sima Dezso tanár (Budapesti Muszaki  Foiskola Neu mann János Informatikai Karának foigazgatója), Sidló Csaba PhD hallgató (ELTE Informatikai Doktori Iskola), Szeidl László egyetemi tanár (Pécsi Tudományegyetem Matematikai és Informatikai Intézet igazgatója), Szidarovszky Ferenc egyetemi tanár (Arizonai Muszaki  Egyetem), Szirmay-Kalos László egyetemi tanár (BME Villamosmérnöki és Informatikai Kara), Terlaky Tamás egyetemi tanár (McMaster

Egyetem, Hamilton)  Ugyancsak köszönjük azoknak a kollégáinknak a segítokészségét, akiknek a lektori véleményét csatolni tudtuk a pályázathoz: Fekete István egyetemi docens (Rekurziók címu  fejezet), Fridli Sándor egyetemi docens (Adattömörítés), Gonda János egyetemi docens (Kriptográa), Hunyadvári László egyetemi docens és Katsányi István PhD hallgató (Bioinfor matika), Kiss Attila egyetemi docens (Relációs adatbázisok tervezése), Toke Pál egyetemi docens (Hálózatok szimulációja), Vida János egyetemi docens (Graka). Az elektronikus változat elkészültéig a http://people.infeltehu/tony/konyvek/infalg  címu  honlapon találják meg olvasóink a könyv kiegészítését, amely többek között az élo irodalomjegyzéket, a névmutatót, a gyakorlatok és feladatok egy részének megoldását, mu  programokat, a talált hibák jegyzékét tartalmazza. Ezen a honlapon keresztül fogjuk ködo  Olvasóinkat tájékoztatni az

elektronikus változat hálózati címérol.  matematikus hallgató (ELTE), Köszönet illeti azokat – Bánsághi Anna programtervezo  matematikus hallgató (ELTE), Biró Gabriella (programterBenyó Tamás programtervezo  matematikus), Csörnyei Zoltán egyetemi docens, (ELTE), Gyires Tibor egyetemi tavezo  nár (Illinois Egyetem), Imrényi Katalin tanszéki eloadó (ELTE), Iványi Anna program koordináror (CEEWEB), Iványi Antal (villamosmérnök), Kása Zoltán egyetemi tanár  matematikus hallgató (ELTE), Locher Kornél (BBTE), Kurucz Miklós programtervezo  matematikus hallgató (ELTE), Rét Anna szerkeszto  (Muszaki programtervezo  Könyvki foiskolai  adó), Rónyai Lajos egyetemi tanár (BME), Sima Dezso tanár (BMF), Szabados  matematikus hallgató (ELTE), Szendrei Rudolf programtervezo  Kristóf programtervezo matematikus hallgató (ELTE), Szidarovszky Ferenc egyetemi tanár (Arizonai Muszaki   Egyetem), Szirmay-Kalos László egyetemi tanár (BME), Takács

Dániel programtervezo matematikus hallgató (ELTE) – akik észrevételeikkel segítettek a könyvünk alapjául szol kiadásának javításában. gáló mu,  az Informatikai algoritmusok I elso   nyomtatott kiadás, mind az elektronikus kiadás A késobbiekben szeretnénk mind az elso hibáit kijavítani. Ezért kérjük a könyv Olvasóit, hogy javaslataikat, észrevételeiket küldjék el a   pontosan megjelölve a hiba elofortony@inf.eltehu címre – levelükben lehetoleg 8 El®szó dulási helyét, és megadva a javasolt szöveget. Olvasóink javaslataikkal, kérdéseikkel megkereshetik a könyv alkotóit is (címük megtalálható a kolofonoldalon). Budapest, 2004. december 3 Iványi Antal  alkotó szerkeszto I. ALAPOK Bevezetés Ebben az alapozó részben négy témakört tárgyalunk.  Az informatikai algoritmusok elemzése során gyakran elofordul, hogy például felismerjük az n és n +1 méretu  feladatok megoldási ideje közötti kapcsolatot

– és ennek az úgyne- vezett rekurzív egyenletnek a felhasználásával szeretnénk közvetlenül felírni az n méretu   Az elso  fejezet a rekurzív egyenletek leggyakrabban elofor bemenethez tartozó futási idot. duló típusainak megoldási módszereit mutatja be. A mai számítógépek sebessége és tárolókapacitása, valamint az elméleti eredmények  számos olyan feladat kényelmes (mechanikus) megoldását lehetové teszik, melyeket korábban nem, vagy csak nagy nehézségek árán tudtunk kezelni. Ezek egy része – mint a formális differenciálás és integrálás – a második fejezetben tárgyalt komputeralgebrához tartozik.  a kommunikáció Az elektronikus kommunikáció hatalmas iramú terjedésével együtt no  biztonságának jelentosége. Ezért a mai informatika egyik kulcsfontosságú területe a kriptográa, mellyel a könyv harmadik fejezete foglalkozik.  Az algoritmusok elemzésének hagyományosan fontos része az eroforrásigény leg

korlátjának megadása. Az csak az utóbbi 15 évben vált rosszabb esetre vonatkozó felso  természetessé, hogy az eroforrásigényre vonatkozó – a probléma és a megengedett algoritmusok tulajdonságain alapuló – alsó korlátokat is megadnak. Például Donald Knuth The Art of Computer Programming címu  monográájának 1968 kötetében szerepelt az aszimptotikus felso  korlátok jellemzésére használt ban megjelent elso O-jelölés (nagy ordo) deníciója – ugyanakkor még nem szerepelt az alsó korlátok jellemzésére alkalmas Ω-jelölés, valamint a pontos nagyságrend megadására alkalmas Θ-jelölés. Az  kiadásában, a Distributed Algorithms Introduction to Algorithms 1990-ben megjelent elso  kiadásában, valamint Knuth könyvének 1997-ben megjelent har1996-ban megjelent elso madik kiadásában már az Ω-jelölés és a Θ-jelölés deníciója is szerepel. A negyedik fejezet szerint a bonyolultságelmélet fontos feladata, hogy a

problémákhoz és számítási modellekhez minél pontosabb alsó korlátokat adjon meg – ezzel is segítve a  problémák eroforrásigény szerinti osztályozását. A második kötetben fog megjelenni az algebrai algoritmusok elemzése. 1. Rekurzív egyenletek (Kása Zoltán) Közismert a Fibonacci-számok rekurzív deníciója: ha F n jelöli az n-edik Fibonacciszámot, akkor F0 F n+2 = = 0, F n+1 F1 =1, + Fn , ha n ≥0.  Szeretnénk explicit formában megadni F n értékét tetszoleges n-re. A feladat tulajdonképpen olyan egyenlet megoldását kéri, amelyben az ismeretlen rekurzív módon van megadva, ezért rekurzív egyenletnek hívjuk. Itt a megoldás felfogható úgy, mint természetes számokon értelmezett függvény, mivel F n minden n-re értelmezett Az ilyen rekurzív egyenletet szokás még differenciaegyenletnek is nevezni, de nevezhetnénk akár diszkrét differenciálegyenletnek is. 1.1 deníció A k-adrendu  rekurzív egyenlet (k f (xn , xn+1 ,

. , , xn+k ) ≥ 1) egy = 0, n ≥0 (1.1) alakú egyenlet, ahol xn -et kell explicit formában megadnunk.  Ahhoz, hogy egyértelmuen  meghatározhassuk xn -et, meg kell adnunk k kezdoértéket, ezek  általában x0 , x1 , . , xk−1 Ezek az értékadások kezdeti feltételeknek tekinthetok Mivel a Fibonacci-számokat deniáló egyenlet másodrendu  rekurzív egyenlet, ezért ott két kezdeti értéket adunk meg.  xn Az (1.1) egyenletet és annak adott kezdeti feltételeit kielégíto adott egyenlet partikuláris megoldásának nevezzük. Ha az xn = = g(n) sorozatot az h(n, C 1 , C 2 , . , C k ) soro- zatból – a C 1 , C 2 , . , C k állandók alkalmas megválasztásával – az (11) egyenlet minden  partikuláris megoldása eloállítható, akkor a sorozatot az egyenlet általános megoldásának nevezzük.  A rekurzív egyenletek megoldása általában nem egyszeru.  A következokben sajátos esetekben alkalmazható módszereket ismertetünk. Az

írásmódban függvény helyett inkább sorozatot használunk (ami tulajdonképpen természetes számokon értelmezett függvény). Így a jelölés egyszerubb  lesz, x(n) helyett mindenhol xn -t írunk.  áll. Az 11 alfejezetben a lineáris rekurzív egyenletek megA fejezet három részbol oldásával, a 1.2 alfejezetben a generátorfüggvények felhasználásával, az 13 alfejezetben pedig lineáris rekurzív egyenletek numerikus megoldásával foglalkozunk. 1.1 Lineáris rekurzív egyenletek 13 1.1 Lineáris rekurzív egyenletek Ha a rekurzív egyenlet f0 (n)xn + f1 (n)xn+1 + ··· + fk (n)xn+k = f (n), n ≥0 alakú, ahol f , f0 , f1 , . , fk természetes számokon értelmezett függvények, f0 , fk , 0, és  beszélünk. Ha xn -et kell explicit módon megadnunk, akkor lineáris rekurzív egyenletrol f azonosan nulla, akkor az egyenlet homogén, és különben inhomogén. Amennyiben az f0 , f1 , . , fk függvények mindegyike állandó, akkor állandó

együtthatós lineáris rekurzív  van szó. egyenletrol 1.11 Állandó együtthatós homogén lineáris rekurzív egyenletek Legyen a0 xn + a1 xn+1 + · · · + ak xn+k = 0, ahol a0 , a1 , . , ak valós állandók, a0 , ak , 0, k ≥ n ≥k, (1.2) 1. Amennyiben adva van k kezdeti érték (leggyakrabban x0 , x1 , . , xk−1 ), az egyenlet megoldása egyértelmuen  meghatározható. A megoldás érdekében rendeljük hozzá az egyenlethez a karakterisztikus egyenletét: a0 + a1 r + · · · + ak−1 rk−1 + ak rk = 0 , (1.3) amely valós együtthatós egyenlet. Ennek az egyenletnek k gyöke van a komplex számok   hogy ha r0 valós megoldása a karakterisztikus körében. Behelyettesítéssel ellenorizhet o, egyenletnek, akkor C 0 r n 0  megoldása az (1.2) egyenletnek, ahol C 0 tetszoleges állandó. Az (1.2) egyenlet általános megoldása xn (i) ahol xn (i = C1 xn(1) + C2 xn(2) + · · · + Ck xn(k) , = 1, 2, . , k) az (12) egyenlet lineárisan

független megoldásai A kezdeti felté-  mindig meghatározhatók a C 1 , C 2 , . , C k állandók egy k egyenletbol  álló egyentelekbol letrendszer megoldásával. A lineárisan független megoldásokat a karakterisztikus egyenlet gyökei szolgáltatják  szerint. Minden gyökhöz hozzárendelheto  egy fundamentálisnak nevezett a következok megoldás.  valós gyökök Különbözo  valós gyökei. EkLegyenek r1 , r2 , , r p a karakterisztikus egyenlet egymástól különbözo kor n n r1 , r2 , ., n rp megoldásai az (1.2) rekurzív egyenletnek, és n C 1 r1  is az, tetszoleges C1 , C2 , általános megoldása. ., + C2 r2n + · · · + C p rnp C p állandókra. Ha p = (1.4) k, akkor (1.4) a rekurzív egyenlet 14 1. Rekurzív egyenletek (Kása Zoltán) 1.1 példa Oldjuk meg az = xn+2 + xn , xn+1 x0 = 0, =1 x1 rekurzív egyenletet. A karakterisztikus egyenlet r −r−1=0 , 2 amelynek gyökei = r1 1 √ + 5 2 , r2 = 1 √ −

5 . 2 Ezek valósak és egymástól különböznek, tehát az egyenlet általános megoldása xn √ n √ n    1 − 5   1 + 5   + C2   . = C1  2 2  Ha gyelembe vesszük, hogy x0 A C 1 és C 2 meghatározhatók a kezdeti feltételekbol. = 0, x1 = 1, a  egyenletrendszerhez jutunk: következo C1 + C2 √ − 5 C1 √ + 1 5 + C2 2 1 2 = 0 , = 1 . √ √ = 1/ 5, C2 = −1/ 5 . Így az általános megoldás √ n √ n   1  1   1 + 5   1 − 5  = √   − √   , Az egyenletrendszer megoldása C 1 xn 2 5 2 5 amely éppen F n , az n-edik Fibonacci-szám. Többszörös valós gyökök Legyen r egy p-szeres gyöke a karakterisztikus egyenletnek. Ekkor r n , nr n , 2 n n r , ., n p−1 n r megoldásai az (1.2) rekurzív egyenletnek (az r többszörös gyökhöz tartozó fundamentális megoldások),

és C0 + C1 n + C2 n2 + · · · + C p−1 n p−1  is megoldás, tetszoleges C0 , C1 , .,
r n C p−1 állandókra. Ha a karakterisztikus egyenletnek nincs más gyöke, akkor (1.5) a rekurzív egyenlet általános megoldása 1.2 példa Oldjuk meg az xn+2 = 4xn+1 − 4xn , x0 = 1, rekurzív egyenletet. A karakterisztikus egyenlet r amelynek r 2 − 4r + 4 = 0 , = 2 kétszeres gyöke. Ekkor xn megoldása az egyenletnek. (1.5) = (C0 + C1 n)2n x1 =3 1.1 Lineáris rekurzív egyenletek 15  A kezdeti feltételekbol 2C 0 Innen C 0 C0 = 1 , + 2C1 = 3 . = 1, C1 = 1/2, azaz az általános megoldás = xn 1 + 1 2 ! n 2 n vagy = (n + 2)2n−1 . xn Egyszeres komplex gyökök Ha a trigonometrikus alakban felírt a(cos b + i sin b) komplex szám gyöke a karakterisztikus egyenletnek, akkor az a(cos b − i sin b) konjugált is az, mivel a karakterisztikus egyenlet valós együtthatós. Ekkor n a cos bn és n a sin bn megoldása az (1.2)

rekurzív egyenletnek és n C 1 a cos bn + C2 an sin bn (1.6)  is az, tetszoleges C 1 és C 2 állandókra. Ha a karakterisztikus egyenletnek nincsenek más gyökei, akkor (1.6) általános megoldás 1.3 példa Oldjuk meg az = 2xn+1 − 2xn , xn+2 = 0, x0 x1 =1 rekurzív egyenletet. A karakterisztikus egyenlet r amelynek gyökei 1 2 − 2r + 2 = 0 , + i és 1 − i, trigonometrikus alakban: √ 2(cos(π/4) i sin(π/4)). Ezért a rekurzív egyenletnek xn = C1 ( √ n 2) cos nπ + C2 ( 4 √ n 2) sin nπ 4  megoldása. A kezdeti feltételekbol √ C1 Innen azt kapjuk, hogy C 1 = 0, C2 2 cos π 4 + C2 C1 √ 2 sin π 4 = 0 , = 1 . = 1. Az általános megoldás tehát xn = √
n 2 sin nπ 4 . + i sin(π/4)) és √ 2(cos(π/4) − 16 1. Rekurzív egyenletek (Kása Zoltán) Többszörös komplex gyökök Ha a trigonometrikus alakban felírt a(cos b + i sin b) komplex szám p-szeres gyöke a karak- − i sin b) konjugált

is az. terisztikus egyenletnek, akkor az a(cos b Ekkor az (1.2) rekurzív egyenletnek n n ., n n ., n a cos bn, na cos bn, és n a sin bn, na sin bn, p−1 p−1 n a cos bn n a sin bn megoldásai. Ekkor megoldás (C 0 + C1 n + · · · + C p−1 n p−1 )an cos bn + (D0 + D1 n + · · · + D p−1 n p−1 )an sin bn  is, ahol C 0 , C 1 , . , C p−1 , D0 , D1 , , D p−1 tetszoleges állandók, amelyek meghatározhatók  Ez általános megoldás, ha a karakterisztikus egyenletnek nincsenek a kezdeti feltételekbol. más gyökei. 1.4 példa Oldjuk meg az xn+4 + 2xn+2 + xn = 0, x0 = 0, x1 = 1, x2 = 2, x3 =3 rekurzív egyenletet. A karakterisztikus egyenlet r amely (r 2 4 + 2r2 + 1 = 0 , + 1)2 = 0 alakban is írható, és amelynek i és −i kétszeres gyöke. Ezek trigonometrikus alakja i = cos π 2 π + i sin , 2 − i = cos valamint π 2 − i sin π 2 Ezért az általános megoldás xn = (C0 + C1 n) cos nπ 2 + (D0 + D1 n) sin nπ 2

.  következik: A kezdeti feltételekbol (C 0 + C1 ) cos π 2 C0 + (D0 + D1 ) sin π 2 + 2C1 ) cos π + (D0 + 2D1 ) sin π 3π 3π + (D0 + 3D1 ) sin (C 0 + 3C 1 ) cos (C 0 2 2 = 0 , = 1 , = 2 , = 3 , azaz = 0 , + D1 = 1 , −2C1 = 2 , −D0 − 3D1 = 3 , D0 és innen C 0 C0 = 0, C1 = −1, D0 = 3 és D1 = −2. Az általános megoldás tehát xn = (3 − 2n) sin nπ 2 − n cos nπ 2 . . 1.1 Lineáris rekurzív egyenletek 17 A most vizsgált négy eset segítségével bármilyen állandó együtthatós homogén egyenletet megoldhatunk. 1.5 példa Oldjuk meg az xn+3 = 4xn+2 − 6xn+1 + 4xn , x0 = 0, x1 = 1, x2 =1 rekurzív egyenletet. A karakterisztikus egyenlet r 3 − 4r2 + 6r − 4 = 0 , + i és 1 − i. Ezért az általános megoldás √
n √
n nπ nπ n + C3 2 sin . 2 cos xn = C 1 2 + C 2 amelynek gyökei: 2, 1 4 4 Az állandók meghatározása után xn = −2 n−1 + √
n  2 2 cos nπ 4 nπ + 3

sin  . 4 Általános megoldás Az (1.2) k-adrendu  homogén lineáris rekurzív egyenlethez rendelt karakterisztikus egyenletnek összesen k gyöke van a komplex számok között, amelyek nem feltétlenül   különbözok. Legyenek ezek a gyökök a következok: r1 valós, p1 -szeres ( p1 r2 valós, p2 -szeres, ( p2 ≥ 1) ≥ 1) , , . ≥ 1) , = a1 (cos b1 + i sin b1 ) komplex, q1 -szeres (q1 ≥ 1) = a2 (cos b2 + i sin b2 ) komplex, q2 -szeres (q2 ≥ 1) rt valós, pt -szeres, ( pt s1 s2 , , . sm = am (cos bm + i sin bm ) komplex, qm -szeres (qm ≥ 1) Mivel összesen k gyök van, p1 . + p2 + · · · + pt + 2(q1 + q2 + · · · + qm ) = k. Ekkor az (1.2) rekurzív egyenlet általános megoldása xn t X  = C ( j) 0 + C1( j) n + · · · + C (pj)−1 n p −1 + ( j) D 0 + D(1j) n + · · · + D(qj)−1 nq −1 + E ( j) 0 + E1( j) n + · · · + Eq( j)−1 nq −1 j=1 ahol C ( j) 0 , C ( j) 1 , ., C ( j) p j −1 , j  j j j=1

m X  = 1, 2, . , t , j j n rj j j=1 m X   j  n a j cos b j n n a j sin b j n , (1.7) 18 1. Rekurzív egyenletek (Kása Zoltán) (l) D 0 , E (l) 0 , (l) D 1 , E (l) 1 , .,  meghatározhatók. feltételekbol (l) D pl −1 , E (l) pl −1 , l = 1, 2, . , m állandók, melyek a kezdeti  tételben foglalhatók össze. Az eddigiek a következo 1.2 tétel Legyen k ≥ 1 egész, a0 , a1 , . , ak valós számok, a0 , ak , 0. Az (1.2) lineáris rekurzív egyenlet általános megoldása eloállítható  az (1.3) karakterisztikus egyenlet ri gyöj n keibol  képezett n ri alakú tagok lineáris kombinációjaként, ahol a pi -szeres ri gyök esetében 0 ≤ j< p és a lineáris kombináció együtthatói a kezdeti feltételektol  függnek. A tétel bizonyítását az Olvasóra hagyjuk (lásd 1.1-5 gyakorlat)  A megoldás lépéseit a következoképpen foglalhatjuk össze. Feltesszük, hogy az egyenlet együtthatóit az A

tömb, a megoldás állandóit pedig a C tömb tartalmazza H́-́ 1 írjuk fel a rekurzív egyenlet karakterisztikus egyenletét 2 keressük meg a karakterisztikus egyenlet összes gyökét, multiplicitásukkal együtt 3 írjuk fel az (1.7) általános megoldást a gyökök alapján 4  ha léteznek, határozzuk meg az (1.7)-ben szereplo  állandókat a kezdeti feltételekbol, 1.12 Állandó együtthatós inhomogén lineáris rekurzív egyenletek Az állandó együtthatós inhomogén lineáris rekurzív egyenlet általános alakja a0 xn + a1 xn+1 + · · · + ak xn+k = ahol a0 , a1 , . , ak valós állandók, a0 , ak , 0, k ≥ 1, és f (n) , (1.8) f (n) nem azonosan nulla. Az egyenlethez tartozó (1.2) homogén lineáris egyenletet az 12 tétel szerint meg tudjuk oldani. Ha ismerjük az (18) egyenlet egy partikuláris megoldását, akkor az (18) egyenlet  tudjuk állítani. általános megoldását is elo 1.3 tétel

Legyen k ≥ 1 egész, a0 , a1 , . , ak valós számok, a0 , ak lineáris inhomogén rekurzív egyenlet egy partikuláris megoldása és tartozó (1.2) homogén lineáris egyenlet általános megoldása, akkor xn = (0) xn + xn(1) általános megoldása az (1.8) egyenletnek A tétel bizonyítását meghagyjuk az Olvasónak (lásd 1.1-6 gyakorlat) 1.6 példa Oldjuk meg az xn+2 + xn+1 − 2xn = 2n , x0 = 0,  rekurzív egyenletet. Eloször megoldjuk az xn+2 + xn+1 − 2xn = 0 x1 =1 , 0. (0) xn (1) Ha xn az (1.8) az (1.8) egyenlethez 1.1 Lineáris rekurzív egyenletek 19 (1) f (n) xn n a p n (C 0 + C1 n + · · · + C p n p )an n p (C 0 + C1 n + · · · + C p n p )an sin bn + (D0 + D1 n + · · · + D p n p )an cos bn n p (C 0 + C1 n + · · · + C p n p )an sin bn + (D0 + D1 n + · · · + D p n p )an cos bn a n sin bn a n cos bn 1.1 ábra A partikuláris megoldás alakja homogén egyenletet, amelynek általános megoldása (0) xn = C1

(−2)n + C2 , (1)  mivel a karakterisztikus egyenlet gyökei −2 és 1. Könnyen ellenorizhetjük, hogy xn = 2n−2 megoldása az eredeti, inhomogén egyenletnek. Az inhomogén egyenlet általános megoldása tehát xn = C1 (−2)n + C2 + 2n−2 .  Ennek alapján az általános megoldás A C 1 és C 2 állandókat meghatározhatjuk a kezdeti feltételekbol. xn =− 1 4 (−2) n ( azaz xn = + 2n−2 vagy 0, 2 xn ha n páros n−1 , 2 = n − (−2)n 4 , , ha n páratlan . A partikuláris megoldás meghatározható a konstansok variálásának módszerével. Léteznek azonban olyan esetek, amikor a partikuláris megoldást könnyebben is megkaphatjuk (1) Az 1.1 ábrán olyan f (n) függvényeket adunk meg, amelyek esetében az xn partikuláris  Az állandókat az egyenletbe való bemegoldás a táblázatban megadott alakban keresheto. helyettesítéssel kaphatjuk meg. = 2n , tehát az elso esetet alkalmazzuk, amikor a = 2, p = -nel próbálkozunk.

Behelyettesítés után azt kapjuk, hogy C 0 = 1/4, tehát a  o  példánk esetében f (n) Eloz n 0, ezért a C 0 2 partikuláris megoldás (1) xn = 2n−2 . Gyakorlatok 1.1-1 Oldjuk meg az alábbi inhomogén lineáris rekurzív egyenletet: Hn = 2Hn−1 + 1, ha n ≥ 1, és H0 =0. 20 1. Rekurzív egyenletek (Kása Zoltán) (Hn itt a Hanoi-tornyai nevu  feladat megoldásához szükséges – és egyben elégséges – lépések számát jelenti.) 1.1-2 Elemezzük a Hanoi-tornyaira vonatkozó feladatot abban az esetben, amikor úgy kell n korongot átrakni az A rúdról a C rúdra, hogy közben az A rúdról a C rúdra nem szabad korongot átrakni. Útmutatás. Mutassuk meg, hogy ha az optimális algoritmus lépéseinek száma Mn és n ≥ 1, akkor Mn = 3Mn−1 + 2.  rekurzív egyenletet: 1.1-3 Oldjuk meg a következo (n + 1)Rn = 2(2n − 1)Rn−1 , ≥ 1, ha n és R0 = 1. 1.1-4 Oldjuk meg alábbi inhomogén lineáris rekurzív egyenletet: = 2n − 2 +

2xn−1 , xn ha n ≥ 2, n Útmutatás. Keressük a partikuláris megoldást C 1 n2 1.1-5? 1.1-6? és x1 = 0. + C2 alakban. Bizonyítsuk be az 1.2 tételt Bizonyítsuk be az 1.3 tételt 1.2 Generátorfüggvények és rekurzív egyenletek A generátorfüggvényeket, többek között, felhasználhatjuk rekurzív egyenletek megoldására, bizonyos objektumok (pl. bináris fák) megszámolására, azonosságok bizonyítására, partíciós problémák megoldására. Az objektumok megszámolása rekurzív egyenletek felállításával és megoldásával történik Ezek a rekurzív egyenletek általában nem lineárisak, megoldásukban segíthetnek a generátorfüggvények. 1.21 Értelmezés és m¶veletek Egy (an )n≥0 = ha0 , a1 , a2 , . , an , i végtelen számsorozathoz hozzárendelhetünk egy hat-  ványsort a következoképpen: A(z) = a0 + a1 z + a2 z2 + · · · + an zn + · · · = X n an z , n≥0 amelyet az (an )n≥0 számsorozat

generátorfüggvényének nevezünk.  Például a Fibonacci-számok esetében a generátorfüggvény a következo: F(z) = X Fn z n = z + z2 + 2z3 + 3z4 + 5z5 + 8z6 + 13z7 + · · · . n≥0 2  Ha mindkét oldalt megszorozzuk z-vel, majd z -tel, a következoket kapjuk: F(z) zF(z) 2 z F(z) = = = F0 + F1 z + F2 z2 + F3 z3 + · · · + Fn zn + · · · , 2 3 n F 0 z + F 1 z + F 2 z + · · · + F n−1 z + · · · , F0 z 2 + F1 z3 + · · · + Fn−2 zn + · · · .  képletbol  a másodikat, majd a harmadikat, és gyelembe Ha kivonjuk tagonként az elso 1.2 Generátorfüggvények és rekurzív egyenletek 21  kapjuk: vesszük a Fibonacci-számokat deniáló képletet, a következot F(z)(1 − z − z2 ) = z , ahonnan F(z) z = 1 . − z − z2 (1.9) A fenti számítások helyességét matematikailag igazolni lehet, de nem térünk ki erre. A generátorfüggvények segítségével, formális muveletek  során kapott eredményeket a legtöbb esetben más

módszerekkel is lehet igazolni. Tekintsük az A(z) = X n an z és B(z) = X n≥0 n bn z n≥0 generátorfüggvényeket. Az A(z) és B(z) generátorfüggvényeket akkor és csakis akkor mondjuk egyenlonek,  ha an = bn bármely n természetes számra.  generátorfüggvényekkel végezheto  muveleteket Ezután a következo,  deniáljuk: összeadás és valós számmal való szorzás, eltolás, szorzás, deriválás, integrálás. Összeadás és valós számmal való szorzás αA(z) + β B(z) = X (αan + βbn )zn . n≥0 Eltolás A k z A(z) = X n+k an z n≥0 X n an−k z n≥k < 0, 0, . , 0, a0 , a1 , > | {z } generátorfüggvény a = számsorozatot jelképezi, míg az k 1 z k (A(z) − a0 − a1 z − a2 z2 − · · · − ak−1 zk−1 ) = X n−k an z < ak , ak+1 , ak+2 , . > 1.7 példa Legyen A(z) = 1 + z + z2 + · · · . Ekkor  1 A(z) − 1 = A(z) z X n ak + n z n≥0 n≥k generátorfüggvény az =

sorozatot. és A(z) = 1 1 −z . Szorzás Ha A(z) és B(z) generátorfüggvények, akkor A(z)B(z) + a1 z + · · · + an zn + · · · )(b0 + b1 z + · · · + bn zn + · · · ) = (a0 = = a0 b0 2 X + (a0 b1 + a1 b0 )z + (a0 b2 + a1 b1 + a2 b0 )z + · · · n sn z , n≥0 22 1. Rekurzív egyenletek (Kása Zoltán) ahol sn = n X ak bn−k . k=0 Sajátos eset. Ha bn = 1 bármely n természetes számra, akkor  n  X X  1  = A(z)  ak  zn . 1−z n≥0 k =0 (1.10) = 1 is igaz bármely n természetes számra, akkor Ha még ezenkívül an 1 − z) (1 X = 2 (n + 1)zn . (1.11) n≥0 Deriválás 0 A (z) X = a1 + 2a2 z + 3a3 z2 + · · · = (n + 1)an+1 zn . n≥0 1.8 példa Az A(z) X = z = n n≥0 1 1 −z generátorfüggvény mindkét oldalát deriválva azt kapjuk, hogy 0 A (z) X = nz n−1 = n≥1 1 (1 − z)2 . Integrálás Z z A(t)dt = a0 z + 0 1 2 2 + a1 z 1 3 a2 z 3 +

··· = X1 n≥1 n an−1 z n 1.9 példa Legyen 1 1 −z = 1 + z + z2 + z3 + · · · Mindkét oldalát integrálva azt kapjuk, hogy ln 1 1 =z+ −z 1 2 2 z + 1 3 3 z + ··· = X n≥1 1 n z n . Ha a két fenti generátorfüggvényt összeszorozzuk, akkor 1 1 ahol Hn =1+ 1 2 + 1 3 + ··· + 1 n (H0 −z = 0, ln 1 1 H1 −z = X Hn z n , n≥1 = 1) az ún. harmonikus számok . 1.2 Generátorfüggvények és rekurzív egyenletek 23 Argumentum cseréje Legyen A(z) P n P = < a0 , a1 , a2 , . > sorozatot jelképezi, akkor A(cz) =  is: < a0 , ca1 , c2 a2 , . cn an , > sorozatot Igazak még a következok n an z , amely az n≥0 n n≥0 c an z pedig az 1 2 1 2 A(z) A(z)  − A(−z) = a1 z + a3 z3 + · · · + a2n−1 z2n−1 + · · · . 1 = 1 + z + z2 + z3 + · · · = 1.10 példa Legyen A(z) 1  + A(−z) = a0 + a2 z2 + · · · + a2n z2n + · · · , 1 + z + z + ··· = 2 4 2 A(z) 1 .

Ekkor −z
+ A(−z) = 1 1 2 1 −z ! 1 + 1 = +z 1 1 − z2 1 − z2 , 2 amely megkapható úgyis, hogy z-t z -tel helyettesítjük A(z)-ben.  u Hasonlóképpen, megkaphatjuk a páratlan kitevoj  tagok összegét: z 1 + z3 + z5 + · · · = 2 A(z)
− A(−z) = 1 1 2 1 −z ! 1 − 1 +z = z . A generátorfüggvények segítségével érdekes képleteket kaphatunk. Legyen például A(z) = 1/(1 − z) = 1 + z + 2 z + z 3 + ···.
+ Ekkor zA z(1 z) = F(z), vagyis éppen a  Fibonacci-számok generátorfüggvénye. A fenti képletbol zA z(1 Az n+1 n+1 z
+ z) = z + z2 (1 + z) + z3 (1 + z)2 + z4 (1 + z)3 + · · · . + 1)-edik Fibonacci-szám, míg a együtthatója a bal oldalon éppen F n+1 , vagyis az (n jobb oldali együtthatója, a binomiális képlet alkalmazása után minden tagban X −k n k k ≥0 Innen F n+1 = X n −k k k ≥0 ! ! . b n+2 1 c = X n −k k k=0 ! . (1.12) 

Emlékeztetünk, hogy a binomiális képlet általánosítható tetszoleges valós r-re is, vagyis (1 r + z) = X n≥0 ! r n n z , amely a binomiális együtthatók generátorfüggvénye. Itt ! r n a kombináció általánosítása va- lós r-re, vagyis r ! n        =      r(r 1, 0, − 1)(r − 2) . (r − n + 1) , n(n − 1) . 1 ha n >0, ha n =0, <0. ha n 24 1. Rekurzív egyenletek (Kása Zoltán) A binomiális képlet fenti általánosításával (negatív r-re) egy, sok esetben hasznos képletet kapunk. Legyen 1 − z)m (1 X −m! = (1 − z)−m = (−z) k k≥0 k . Mivel egyszeru  számítással igazolható, hogy ! −m k m = (−1)k ! +k−1 , k  képletet kapjuk: a következo 1 (1 Ekkor z (1 m − z)m+1 = X k≥0 Innen pedig = − z)m+1 m +k k≥0 m m+k z = +k X m m ! z +k k . ! z m k≥0 k ! k k≥0 ! k X X m+k = X k≥0 k m ! k z . m

k z = z − z)m+1 (1 , (1.13) ahol m természetes szám. 1.22 Rekurzív egyenletek megoldása generátorfüggvényekkel Ha a megoldandó rekurzív egyenlet olyan, hogy a megoldás generátorfüggvénye sorba fejt úgy, hogy az együtthatók zárt alakban felírhatók, akkor ez a módszer eredményre vezet. heto  rekurzív egyenlet: Legyen adott a következo F(xn , xn−1 , . , xn−k ) A megoldáshoz tekintsük az X(z) = X =0. (1.14) n xn z n≥0 generátorfüggvényt. Ha (114) felírható G X(z)
= 0 egyenletként, amelyet meg tudunk oldani X(z)-re, majd X(z)-t sorba lehet fejteni úgy, hogy xn zárt alakban felírható, akkor az (1.14) egyenletet sikerrel oldottuk meg  A következokben általános módszert adunk az inhomogén lineáris egyenletek megoldására. Ezután három nemlineáris feladatra mutatunk példát Két esetben bináris fák valamilyen halmazának az elemeit számoljuk meg, a harmadikban pedig a bináris fák leveleit A három nemlineáris

rekurzív egyenlet az (1.15), (117) és (118), amelyeket a generátorfüggvények segítségével oldunk meg Állandó együtthatós inhomogén lineáris rekurzív egyenlet n Szorozzuk be z -nel az (1.8) egyenlet mindkét oldalát Ekkor n a0 xn z + a1 xn+1 zn + · · · + ak xn+k zn = f (n)z n . 1.2 Generátorfüggvények és rekurzív egyenletek 25 Összegezzük tagonként a fenti egyenlet mindkét oldalát: X a0 n + a1 xn z n≥0 X xn+1 z n X + · · · + ak xn+k z n≥0 n = X n≥0 f (n)z n . n≥0 Innen átalakításokkal kapjuk, hogy X a0 xn z n + X a1 z n≥0 n+1 xn+1 z = X(z) X xn z n és n+k xn+k z zk n≥0 Legyen X ak + ··· + = n≥0 F(z) = n f (n)z . n≥0 X f (n)z n≥0 X n . n≥0 Ekkor az egyenletünk így alakul: a0 X(z) + a1  z X(z) ak   − x0 + · · · + zk  − x0 − x1 z − · · · − xk−1 zk−1 = X(z) F(z) . Ezt az egyenletet meg lehet oldani X(z)-ben. Az X(z)

kifejezésében a jobb oldali racionális törtet fel lehet bontani elemi (parciális) törtekre, majd azokat sorba fejtve meghatározhatjuk az eredeti egyenlet xn általános megoldását, gyelembe véve a kezdeti feltételeket.  egyenletet: 1.11 példa Oldjuk meg a fenti módszerrel a következo xn+1 − 2xn = 2n+1 − 2, ≥0 ha n és x0 =0. Beszorzás és összegezés után 1 z X xn+1 z −2 n≥0 innen pedig X xn z n =2 X X(z) −2 n n 2 z n≥0 1 z Mivel x0 n+1 n≥0  − x0 − 2X(z) = z n , n≥0 2 − 2z 1 X − 2 1 −z . 1  miután a jobb oldalt elemi törtekre bontottuk: = 0, az egyenlet megoldása a következo, X(z) = 2z (1 − − 2z)2 Az 1 = − 2z 1 2 1 −z X − 2 1 − 2z . n n 2 z n≥0  kapjuk: generátorfüggvény tagonkénti deriválásával a következot 2 (1 Ezért X(z) = X n≥0 1 n n n2 z +2 − 2z) X z n≥0 n 2 = −2 X n n−1 n2 z . n≥1 X n n 2 z n≥0 = X (n − 2)2n

+ 2 n≥0 Az elemi törtekre való bontást a határozatlan együtthatók módszerével végeztük.  n z , 26 1. Rekurzív egyenletek (Kása Zoltán) n=2 n=3 1.2 ábra Két- és háromcsúcsú bináris fák ahonnan xn = (n − 2)2n + 2 . Bináris fák száma = 1, b2 = 2, b3 = 5 (lásd az 1.2  = 1. (Késobb látni fogjuk, hogy ez jó választás.) Ha rögzítjük egy n csúcsú bináris fa gyökerét, akkor még n − 1 csúcs marad a bal és jobb részfában összesen. Ha k csúcs van a bal oldali, n − 1 − k pedig a jobb oldali részfában, akkor összesen bk bn−1−k ilyen bináris fa létezik. Összegezve k = 0, 1, , n − 1 értékekre,  pontosan bn -t kapjuk. Tehát tetszoleges n ≥ 1 természetes számra a bn -ben megoldandó Jelöljük bn -nel az n csúcsú bináris fák számát. Ekkor b1 ábrát). Legyen b0  rekurzív egyenlet a következo: = b0 bn−1 + b1 bn−2 + · · · + bn−1 b0 . bn Ez még így is írható: bn = n−1 X bk

bn−1−k (1.15) . k =0 n A fenti rekurzív egyenlet mindkét oldalát z -nel szorozva, majd n szerint összegezve, a  kapjuk: következot X n bn z Legyen B(z) = X n≥1 n bn z −1 n≥1 (1.16) k =0 a bn számok generátorfüggvénye. Az (115) összefüggés bal ol- n≥0 dala éppen B(z)   n−1 X X    bk bn−1−k  zn . = (mivel b0 = 1). A jobb oldal nagyon hasonlít két generátorfüggvény  van szó, használjuk a következo  szorzatához. Hogy észrevegyük, melyik két függvényrol jelölést: A(z) = zB(z) = X n+1 bn z n≥0 = X n bn−1 z . n≥1 2  zB (z)-vel. Innen Ekkor az (1.16) jobb oldala éppen A(z)B(z), ami egyenlo B(z) − 1 = zB2 (z), B(0) =1. 1.2 Generátorfüggvények és rekurzív egyenletek 27 Oldjuk meg ezt az egyenletet B(z)-re. Ekkor = B(z) Mivel B(0) ± 1 √ 1 − 4z 2z .  Tehát = 1, csak a negatív jel megfelelo. B(z)   1  1/2 1 − (1 − 4z)

− 4z = 2z 2z     ! X X 1/2!     1/2 1 1   n n 2n n  1 −  =  (−4z)  (−1) 2 z  1 −  1 = =  1 − 2z √ 1 n n≥0 ! 1/2 2 z ! 2z n≥0 ! 1/2 2 z n 2n n 1/2 2 z n − ··· − + ··· (−1) 2z 0 2z 1 2z 2z n ! ! 1/2 1/2 3 1/2 n 2n−1 n−1 = 2− 2 z + ··· − (−1) 2 z + ··· 1 2 n ! ! X 1/2 X 1 2n n n 2n+1 n z . = (−1) 2 z = n+1 n n+1 n≥0 n≥0 1 = Innen bn = 1 2n − ! 0 0 + 2 ! . n+1 n  könnyen bizonyítható Megjegyzés. Az utolsó átalakításnál felhasználtuk a következo, összefüggést: ! 1/2 n +1 ! (−1) n = 22n+1 (n 2n + 1) n . Levelek száma n csúcsú bináris fák halmazában  fokú csúcsok) számát. Számítsuk ki az n csúcsú bináris fák halmazában a levelek (azaz elso Jelöljük ezt a számot fn -nel. Megjegyezzük, hogy a gyökeret akkor sem tekintjük levélnek, ha a fokszáma 1. Könnyu 

belátni, hogy f2 = 2, f3 = 6. Legyen f0 = 0 és f1 = 1 konvenció alapján. Ahogy a bináris fák megszámolásánál, tekintsük most is az olyan n csúcsú bináris fákat, amelyeknek bal oldala k csúcsot, a jobb oldala pedig n − k − 1 csúcsot tartalmaz. Bal oldalon bk ilyen részfa van, jobb oldalon pedig bn−1−k . Ha rögzítünk egy ilyen bal oldali részfát, akkor az összes jobb oldali részfát gyelembe véve, ott fn−1−k levél van. Könnyen belátható tehát, hogy adott k-ra bn−1−k fk + bk fn−1−k fn = levél van. Ekkor, összegzés után n−1 X ( fk bn−1−k + bk fn−1−k ) . k=0 Egyszeru  számítással azt kapjuk, hogy fn = 2( f0 bn−1 + f1 bn−2 + ··· + fn−1 b0 ), ≥2. n Ez a megoldandó rekurzív egyenlet, amelynek megoldása fn . Legyen F(z) = X fn z n≥0 n és B(z) = X n bn z n≥0 . (1.17) 28 1. Rekurzív egyenletek (Kása Zoltán) n Az (1.17) összefüggés mindkét oldalát z -nel

szorozva, majd n szerint összeadva X  n−1 X X  =2  n fn z n≥2 De, mivel f0 = 0 és f1 n≥2    zn . fk bn−1−k  k =0 = 1, F(z) − z = 2zF(z)B(z) . Innen F(z) de mivel B(z) = z = 1  1 1 2z , − 2zB(z) √ −  − 4z 1 , következik, hogy F(z) z = √ 1 = z(1 − 4z)−1/2 = z − 4z X −1/2! n n≥0 n (−4z) . A számítások elvégzése után F(z) X = 2n fn = −2 n−1 2n n+1 z n n≥0 innen pedig ! X = n≥1 ! vagy fn+1 −2 n−1 2n 2n = ! z n , ! = (n + 1)bn . n A kombináció általánosítása alapján f0 és f1 a konvenció alapján megadott értékekkel lesz nek egyenlok. n csúcsú, k levelu  bináris fák száma Egy kicsit nehezebb feladat: hány n csúcsú k levelu  bináris fa létezik? Jelöljük ezek számát (k) (k) bn -val. Könnyu  belátni, hogy bn lehet számítani a k Legyen b (0) 0 = = = 0, ha k (1) 1 esetet, vagyis bn =

> b(n + n−1 1)/2c. Egyszeru  okoskodással ki  tetszoleges n 2 ≥ 1 természetes számra.  o  feladatoknál, itt is a bal és jobb 1 konvenció alapján. Akárcsak az eloz oldali részfákat vizsgáljuk meg. Ha a bal oldali részfában i csúcs és j levél van, akkor a jobb oldaliban n ( j) − i − 1 csúcs és k − (k− j) j levél van. A bi b n−i−1 szorzat éppen ezeknek a fáknak a  rekurzív képletet kapjuk: száma. Összegezve k és j szerint, a következo (k) bn = 2b(k) + n−1 n−2 X k −1 X ( j) (k− j) bi b n−i−1 i=1 . (1.18) j=1  generátorfüggvényt: Ennek a rekurzív egyenletnek a megoldására használjuk a következo (k) B (z) = X (k) n bn z n≥0 , ahol k ≥1. 1.2 Generátorfüggvények és rekurzív egyenletek 29 n Az (1.18) egyenlet mindkét oldalát z -nel megszorozva, majd összeadva az n = 0, 1,  kapjuk: 2, . értékekre, a következot X (k) n bn z =2 n≥1 X (k) b n−1 

n−2 k−1  X X X  ( j) (k − j)   zn . + bi b n−i−1    n z n≥1 n≥1 i=1 j=1 Az összegezés sorrendjét felcserélve X (k) n bn z =2 n≥1 X (k) b n−1  n−2  k −1 X X X   ( j) (k− j)   bi bn−i−1 zn . + n z n≥1 j=1 n≥1  k−1  X  ( j) (k − j)   (z) + z  B (z)B (z)  Innen (k) B (z) i=1 (k) = 2zB j=1 vagy (k) B  k−1  X  ( j) (k − j)   . B (z)B (z) (z) = 1 − 2z z (1.19) j=1  lépésre haladva, felírhatjuk a következoket.  Lépésrol (2) B  z = (z) 1 (1) B − 2z  2 (3) B (z) = (z) = 2z − 2z)  3 (4) B 5z (z) (1) (z) B − 2z) 3 (1 (1) B 2 (1 2 (z) , 3 4 , .  alakban keresni: Az általános megoldást megpróbáljuk a következo  k−1 (k) B ahol, amint láttuk, c2 (z) ck z = (1

k−1 − 2z) (1) B (z) k , = 1, c3 = 2, c4 = 5. Az (119) képletbe behelyettesítve, a ck számokra egy rekurzív összefüggést kapunk: ck = k −1 X ci ck−i . i=1 Ezt szintén a generátorfüggvények segítségével oldjuk meg. Ha k innen c1 = 1. Legyen c0 = 1. Ha C(z) = P n≥0 n cn z = 2, akkor c2 – gyelembe véve a generátorfüggvények szorzási képletét – C(z) − 1 − z = (C(z) − 1)2 2 vagy C (z) amelyet C(z)-re nézve megoldunk, és a C(z) = 3 − √ 1 2 = c1 c1 , és a cn számok generátorfüggvénye, akkor − 4z − 3C(z) + z + 2 = 0 , 30 1. Rekurzív egyenletek (Kása Zoltán)  = 1 miatt csak a negatív elojel jó. Sorba fejtés után X −1 2n! 1 3 1 1/2 n − (1 − 4z) = − z 2 2 2 2n − 1 n n≥0 ! ! X X 1 2n n 1 2n n + z = 1+ z . 2(2n − 1) n 2(2n − 1) n n≥0 n≥1 képletet kapjuk, mivel C(0) 3 = C(z) 2 3 = 2 ! , Innen (1) Mivel bn 2n 1 = cn − 1) 2(2n n ≥1. n (1)  

hogy B = 2n−1 , ha n ≥ 1, könnyen ellenorizhet o, = z/(1 − 2z). Tehát ! 2k−1 2k z 1 (k) . B (z) = 2(2k − 1) k (1 − 2z)2k−1 Mivel azonban 1 = − z)m (1 X ! +m−1 n z n n≥0 n ,  eredményhez jutunk: a következo (k) B (z) 2k 1 = 2(2k − 1) 2k 1 = 2(2k k − 1) !X 0 ! n≥X k n≥2k−1 Innen pedig (k) bn = 2k 1 2k −1 vagy (k) bn = 1 2k n 2k ! k ! k ! −1 n − 2k + 1 n n−2k+1 n 2 z . ! −1 2k − 2 −1 n 2k+n−1 2 z n n n 2k ! +n−2 n−2k 2 ! n−2k 2 . 1.23 A Z-transzformáció módszere Ha generátorfüggvényekkel oldunk meg egy inhomogén lineáris rekurzív egyenletet, akkor, amint láttuk, mindig egy racionális törtfüggvény sorba fejtése adja meg a megoldást. A Z-transzformáció módszerével ezt a sorba fejtést könnyebben elvégezhetjük. Legyen a raci onális törtfüggvény P(z)/ Q(z), ahol P(z) kisebb fokszámú, mint Q(z). Ha ismerjük a nevezo gyökeit, a

törtfüggvényt elemi (vagy parciális) törtfüggvények összegére bonthatjuk a hatá  rozatlan együtthatók módszerével. Nézzük meg eloször azt az esetet, amikor a nevezonek  gyökei vannak, és legyenek ezek csak egyszeres (azaz egymástól különbözo) Ekkor felírhatjuk, hogy P(z) Q(z) = A1 z − α1 + ··· + Ai z − αi + ··· + Ak z − αk . α1 , α 2 , . , α k 1.2 Generátorfüggvények és rekurzív egyenletek 31 Könnyen belátható, hogy Ai =  Másfelol Ai z ahol lim (z zαi − αi − αi ) P(z) Q(z) , i Ai = −αi − 1 1 αi = 1, 2, . , k != z −Ai βi , 1 − βi z  kapjuk: βi = 1/αi . Ha most ezt az elemi törtet sorba fejtjük, akkor a következot −Ai βi = − A i βi 1 − βi z n Innen a z együtthatója
+ βi z + · · · + βni zn + · · · . 1 −Ai βni +1 , és jelöljük ezt Ci (n)-nel. Ekkor = −Ai βni +1 = −βi C i (n) lim (z zαi vagy C i (n) Ha most elvégezzük a z

= −βni +1 (z lim − αi ) P(z) Q(z) − αi )P(z) zαi Q(z) , . 1/z átalakítást, és gyelembe vesszük, hogy βi = 1/αi , akkor ! p(z) n−1 , C i (n) = lim (z − βi )z zβi ahol q(z) p(z) = q(z) P(1/z) Q(1/z) . n Ekkor az X(z) kifejtésében a z együtthatója éppen C 1 (n) Könnyen belátható, hogy ha α + C2 (n) + · · · + Ck (n) . β = gyöke a Q(z) polinomnak, akkor 1/α gyöke a q(z) polinomnak. Például, ha z P(z) Q(z) = 2z (1 − z)(1 − 2z) , p(z) akkor Amennyiben egy gyök többszörös, például βi q(z) = 2 (z − 1)(z − 2)  részeredp-szeres, akkor a neki megfelelo mény C i (n) Itt d = 1 (p lim − 1)! zβ i d . p−1 dz p−1 (z − βi ) p n−1 z p(z) q(z) ! . p f (z) az f (z) függvény p-edrendu  deriváltját jelenti. dz p  algoritmusban összegezhetok.  Az eddigiek a következo Feltesszük, hogy az egyenlet együtthatóit a A, a megoldás állandóit pedig a C tömb tartalmazza.

32 1. Rekurzív egyenletek (Kása Zoltán) L́-́(A, k, f ) 1 legyen az egyenlet a0 xn + a1 xn+1 + · · · + ak xn+k = f (n); n szorozzuk be az egyenlet mindkét oldalát z -nel és összegezzünk n szerint 2 = hozzuk az egyenletet X(z) P(z)/ Q(z) alakra, ahol X(z) = P n≥0 n xn z , P(z) és Q(z) pedig polinomok 3 végezzük el a z 1/z átalakítást, legyen az eredmény p(z)/q(z), ahol p(z) és q(z) polinomok 4 legyenek q(z) gyökei: β1 β2 p2 -szeres, p2 ≥ 1, ≥ 1, pk -szeres, pk ≥ 1; p1 -szeres, p1 . βk ekkor az eredeti egyenlet általános megoldása = C1 (n) + C2 (n) + · · · + Ck (n),  ahol  − d p n−1 C i (n) = 1/(( pi − 1)!) limzβ (z − βi ) z ( p(z)/q(z)) , − dz xn pi 5 1 pi i i i 1 = 1, 2, . , k return C A módszer neve onnan ered, hogy ha egy generátorfüggvényben z helyébe 1/z-t helyet- tesítünk, akkor megkapjuk a Z-transzformáltját, amelyre hasonló

muveletek  léteznek, mint a generátorfüggvényekre, és amelyre alkalmazva a reziduum-tételt, a fenti eredményhez jutunk. 1.12 példa Oldjuk meg az xn+1 − 2xn = 2n+1 − 2, ha n ≥ 0, =0 x0 rekurzív egyenletet. n z -nel beszorozva és összegezve X xn+1 z n −2 n≥0 azaz 1 z X(z) X xn z 2 n≥0 − 2X(z) = 2 1 − 2z X(z) = n+1 n z − n≥0 − 2 1 −z Innen Az X = n 2z X 2z n , n≥0 , ahol X(z) = X xn z n . n≥0 2 (1 − z)(1 − 2z)2 (z − 1)(z − 2)2 . 1/z helyettesítést elvégezve p(z) q(z) = 2z ,  gyökei: 1 egyszeres, 2 kétszeres gyök. Ezért ahol a nevezo n C1 C2 = lim z2 d dz 2z z = lim n −1 z1 2z (z − 2)2 ! = 2 lim z2 nz =2 n−1 − 1) − zn = 2n (n − 2) . − 1)2 (z (z és 1.2 Generátorfüggvények és rekurzív egyenletek 33 Az általános megoldás tehát = 2n (n − 2) + 2, xn n ≥0. 1.13 példa Oldjuk meg az xn+2 = 2xn+1 − 2xn , ha n ≥ 0, x0

= 1, =1 x1 rekurzív egyenletet. n z -nel beszorozva és összegezve 1 X z n+2 xn+2 z 2 2 =  1 z F(z) 2 xn+1 z z n≥0 innen X F(z) 1 − z2 z 2 z  gyökei 1 A nevezo = z2 X xn z n , n≥0 2 Ekkor F(1/z) −2 n≥0  −z = azaz n+1 F(z) − 2F(z) , ! 1 +2 =− . z −z . − 2z + 2 + i és 1 − i. Kiszámítjuk C1 (n)-t és C2 (n)-t: Mivel 1 +i= C 1 (n) = C 2 (n) = √  2 cos π 4 lim z1+i z −zn+1 = − (1 − i) i(1 + i)n 2 és −i(1 − i)n −zn+1 = . − (1 + i) 2 √  π π π , 1 − i = 2 cos − i sin , lim z1−i z + i sin 4 4 4 hatványozás után (1 + i)n = √
n  2 cos nπ 4 xn + i sin nπ 4  , (1 = C1 (n) + C2 (n) = − i)n =  √ n 2 √
n  sin 2 nπ 4 cos nπ 4 − i sin nπ 4  , . Gyakorlatok 1.2-1 Számítsuk ki, hány olyan n csúcsú bináris fa van, amelynek sem a bal, sem pedig a jobb oldali részfája nem üres.  külön1.2-2 Számítsuk ki, hány olyan n

csúcsú bináris fa van, amelyben minden levéltol  csúcsnak pontosan két gyereke van. bözo 1.2-3 Oldjuk meg generátorfüggvény segítségével az alábbi rekurzív egyenletet Hn = 2Hn−1 + 1, H0 =0. (Hn itt a Hanoi-tornyai nevu  feladat lépésszámát jelenti.) 34 1. Rekurzív egyenletek (Kása Zoltán) 1.2-4 Oldjuk meg Z-transzformáció segítségével az alábbi rekurzív egyenletet: F n+2 = F n+1 + Fn + 1, ha n ≥ 0, és F0 = 0, F1 = 1 .  egyenletrendszert: 1.2-5 Oldjuk meg a következo un vn ahol u0 = = + un−2 , + un−1 , vn−1 un = 1, u1 = 2, v0 = 1. 1.3 Numerikus megoldás Leírunk egy függvényeljárást, amellyel lineáris rekurzív egyenleteket oldhatunk meg nume formában adjuk meg: rikusan. Az egyenletet a szokásos módon, a következo a0 xn + a1 xn+1 + · · · + ak xn+k = f (n) .  Az a0 , a1 , . , ak együtthatókat az A, míg az x0 , x1 , , xk−1 kezdoértékeket az X vektor tartalmazza. Hogy kiszámítsuk xn

értékét, sorra kiszámítjuk az xk , xk+1 , , xn értékeket,  k elemében (azaz a 0, 1, . , k minden alkalommal az X vektor elso − 1 indexu elemekben)   o  k értékét. orizve meg a sorozat eloz R́(A, X, k, n, f ) 1 for j 2 3 4 5 6 7 8 9 ← k to n ← A[0] · X[0] for i ← 1 to k − 1 do v ← v + A[i] · X[i]
v ← f ( j − k) − v /A[k] if j , n then for i ← 0 to k − 2 do X[i] ← X[i + 1] X[k − 1] ← v do v 10 return v  xj ( j A 2–5. sorokban kiszámítjuk a következo  o  k érték = k, k + 1, . , n) értékét (az eloz felhasználásával), ezt az értéket az algoritmusban v jelöli. A 7–9 sorokban, amennyiben  k elemébe. A 10 még nem értük el az n-et, átmásoljuk az utolsó k értéket az X vektor elso sor visszaadja az xn értékét. Könnyen belátható, hogy az algoritmus futási ideje Gyakorlatok Θ(kn). 1.3-1 Hány összeadást, kivonást, szorzást, osztást és értékadást végez a

R́ algorit adatokkal kiszámítja x1000 értékét? mus, ha az 1.4 példában szereplo 1. fejezet feladatai 35 Feladatok 1-1. Homogén egyenlet megoldhatósága generátorfüggvénnyel  Bizonyítsuk be, hogy tetszoleges homogén lineáris rekurzív egyenlet generátorfüggvénnyel  olyan eset, hogy nem tudjuk alkalmazni a megvaló megoldáskor csak akkor fordulhat elo adott módszert, mivel az X(z) = 0 egyenlethez jutunk, ha az egyenlet megoldása xn = 0 minden n-re. 1-2. Komplex gyökök Z-transzformáláskor  Vizsgáljuk meg, mi történik, ha a Z-transzformáció módszere alkalmazásakor a nevezo gyökei komplex számok. A rekurzív egyenlet megoldásának mindig valósnak kell lennie Biztosítja-e ezt a módszer? Megjegyzések a fejezethez Elaydi [4], Flajolet és Sedgewick [18], Greene és Knuth [7], valamint Mickens [16] könyve részletesen tárgyalja a rekurzív egyenletek megoldását. Vannak a generátorfüggvényekkel foglalkozó,

magyar nyelvu  könyvek is – például Knuth [10], valamint Graham, Knuth és Patashnik [6]. Vilenkin muve  [19] egyszeru  módon tárgyal sok-sok feladatot – a könyv utolsó két fejezete rekurzív egyenletekkel és generátorfüggvényekkel foglalkozik. Lovász [14] kombinatorikai problémákat és feladatokat tartalmazó könyvében is vannak generátorfüggvényekre vonatkozó feladatok.  a levelek megszámolása a bináris A bináris fák megszámolása Knuth [10] könyvébol, fák halmazában, valamint az n csúcsú k levelu  bináris fák megszámolása Kása Zoltán [9]  valók. könyvébol Irodalomjegyzék [1] A. V Aho, J E Hopcroft, J D Ullman The Design and Analysis of Computer Algorithms Addison-Wesley, Könyvkiadó, 1982. 5 1974. Magyarul: Számítógép-algoritmusok tervezése és analízise Muszaki  [2] T. H Cormen, C E Leiserson, R L Rivest Introduction to Algorithms The MIT Press/McGraw-Hill, 1990 Kiadó, 2003, negyedik kiadás). 5 (Magyarul:

Algoritmusok. Muszaki  [3] T. H Cormen, C E Leiserson, R L Rivest, C Stein Introduction to Algorithms The MIT Press/McGrawHill, 2004 (Második kiadás ötödik, javított utánnyomása Magyarul: Új algoritmusok Scolar Kiadó, 2003) 5 [4] S. N Elaydi An Introduction to Difference Equations Springer-Verlag, 1999 (2 kiadás) 35 [5] M. R Garey, D S Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness W H. Freeman, 1979 6 [6] R. L Graham, D E Knuth, O Patashnik Concrete Mathematics Addison-Wesley, 1994 (2 kiadás MagyaKönyvkiadó, 1998) 35 rul: Konkrét matematika, Muszaki  [7] D. H Greene, D E Knuth Mathematics for the Analysis of Algorithms Birkhäuser, 3 kiadás, 1990 35 [8] A. Iványi Párhuzamos algoritmusok (Parallel Algorithms) ELTE Eötvös Kiadó, 2003 5 [9] Z. Kása Combinatorica cu aplicaţii (Combinatorics with Applications) Presa Universitara Clujeana, 2003 35 [10] D. E Knuth Fundamental Algorithms, The Art of Computer Programming 1 kötete

Addison-Wesley, 1968 (3., javított kiadás 1997 Magyarul: A számítógép-programozás muvészete  1. kötet Alapveto  algoritmusok, Könyvkiadó, 1993, 2. kiadás) 5, 35 Muszaki  [11] D. E Knuth Seminumerical Algorithms, The Art of Computer Programming 2 kötete Addison-Wesley, 1969 (3. javított kiadás 1998 Magyarul: A számítógép-programozás muvészete  2. kötet Szeminumerikus Könyvkiadó, 1993, 2. kiadás) 5 algoritmusok, Muszaki  [12] D. E Knuth Sorting and Searching, The Art of Computer Programming 3 kötete Addison-Wesley, 1973 (3, javított kiadás 1997. Magyarul: A számítógép-programozás muvészete  3. kötet Keresés és rendezés, Muszaki  Könyvkiadó, 1994, 2. kiadás) 5 [13] L. Lovász, P Gács Algoritmusok (Algorithms) Muszaki Könyvkiadó és Tankönyvkiadó, 1978 és 1987. 5  [14] L. Lovász Combinatorial Problems and Exercises Akadémiai Kiadó, 1979 (Magyarul: Kombinatorikai problémák és feladatok, Typotex, 1999). 35 [15] N. A Lynch

Distributed Algorithms Morgan Kaufman Publisher, 2001 (Ötödik kiadás Magyarul: Osztott algoritmusok. Kiskapu Kiadó, 2002) 5 [16] R. E Mickens Difference Equations Theory and Applications Van Nostrand Reinhold, 1990 35 [17] L. Rónyai, G Ivanyos, R Szabó Algoritmusok (Algorithms) Typotex, 1999 5 [18] R. Sedgewick, P Flajolet An Introduction to the Analysis of Algorithms Addison-Wesley, 1996 35 [19] N. J Vilenkin Kombinatorika (oroszul) Mir, 1969 (Angolul: Combinatorial Mathematics, Mir, 1972; maKönyvkiadó, 1987, 2 kiadás) 35 gyarul: Kombinatorika, Muszaki  Tárgymutató A, Á kezdeti feltétel, 12 általános megoldás, 12 konstansok variálásának módszere, 19 B L bináris fák megszámolása, 26 L́-́, 32 binomiális képlet általánosítása, 24 O, Ó F  Felsooktatási Pályázatok Irodája, 4 Fibonacci-számok, 20 fundamentális megoldás, 13 G generátorfüggvény, 20 bináris fák megszámolása, 26

muveletek,  21 Oktatási Minisztérium, 4 P partikuláris megoldás, 12 R R́, 34 rekurzív egyenlet, 12 állandó együtthatós lineáris, 13 homogén lineáris, 13, 18 inhomogén lineáris, 18, 30, 31 lineáris, 13, 18, 24, 30 H Hanoi-tornyai, 20gy harmonikus számok, 22 H́-́, 18 megoldása generátorfüggvénnyel, 24 rekurzív egyenletek, 11 reziduum-tétel, 32 K Z karakterisztikus egyenlet, 13 Z-transzformáció, 30 Névmutató A, Á Iványi Anna, 4 Aho, Alfred V., 36 Iványi Antal, 4, 36 Ivanyos Gábor, 36 B Balogh Ádám, 4 Belényesi Viktor, 4 J Járai Antal, 4 Biró Gabriella, 4 Jeney András, 4 Johnson, David S., 6 Jörg Rothe, 4 C Claudia Leopold, 4 Cormen, Thomas H., 36 K Kása Zoltán, 4, 35, 36 Katsányi István, 4 CS Csirik János, 4 Kiss Attila, 4 Knuth, Donald Erwin, 35, 36 Kovács Attila, 4 Kozma László, 4 D Demetrovics János, 4 L E, É Eberhard Zehendner, 4 Elaydi, Saber

N., 35, 36 Elek István, 4 F Fibonacci, Leonardo Pisano, 12, 14, 20, 21, 23 Flajolet, Philippe, 35, 36 Fridli Sándor, 4 G Galántai Aurél, 4 Garey, Michael R., 6, 36 Gonda János, 4 Graham, Ronald Lewis, 35, 36 Greene, Daniel H., 35, 36 GY Gyires Tibor, 4 I, Í Ingo Althöfer, 4 Láng Zsuzsa, 4 Leiserson, Charles E., 36 Locher Kornél, 4 Lovász László, 35, 36 Lynch, Nancy Ann, 36 M Mayer János, 4 Meskó Attila, 4 Mickens, Ronald Elbert, 35, 36 Miklós István, 4 N Nikovits Tibor, 4 P Patashnik, Oren, 35, 36 Pintér Miklós, 4 R Rivest, Ronald Lewis, 36 Rónyai Lajos, 4, 36 Roszik János, 4 Névmutató 39 S Szidarovszky Ferenc, 4 Sali Attila, 4 Szirmay-Kalos László, 4 Sedgewick, Robert, 35, 36 Sztrik János, 4 Sidló Csaba, 4 Sike Sándor, 4  4 Sima Dezso, U, Ú Stefan Schwartz, 4 Stein, Clifford, 36 SZ Szabó Réka, 36 Szakács Laura, 4 Szántai Tamás, 4 Ulrich Tamm, 4 V Varga László, 4 Vida János, 4 Vilenkin, Naum Jakovlevics, 35, 36 Vizvári

Béla, 4 Megoldások 1.1-1 megoldása A homogén Hn − 2Hn−1 = 0 egyenlet karakterisztikus egyenlete r −2=0 , (0) ezért általános megoldása az 1.2 tétel szerint Hn = C1 2n . Az inhomogén egyenlet szabad tagja 1, ezért a partikuláris megoldás C 2 alakú. Ezt az inhomogén egyenletbe helyettesítve = −1 adódik, tehát Hn(1) = −1. n Az általános megoldás ezért Hn = C 1 2 − 1 alakú. Mivel H0 = 0, C 1 = 1 következik, innen n pedig Hn = 2 − 1. C2 1.1-2 megoldása Egy korongot csak a B rúd segítségével tudunk a helyére rakni, ezért M1 ≥ 2. Mivel a korongot két lépésben a helyére tudjuk tenni, ezért M1 = 2  oleg  Ha n + 1 korongunk van, akkor a legnagyobbhoz csak úgy férünk hozzá, hogy eloz Mn lépésben a többi korongot átraktuk a C rúdra. Most egy lépés kell a legnagyobb korong A-ra való átrakásához nak a B rúdra rakásához, újabb Mn lépés a többi korongnak C-rol Ezután még legalább egy lépés kell a

legnagyobb korong, és Mn lépés a többi korong C-re való átrakásához. Így azt kapjuk, hogy Mn+1 = 3Mn + 2, ha n ≥ 1. − 3 = 0, tehát  karakterisztikus egyenlet alakja r A megfelelo (0) n−1 = talános megoldása Mn C1 3 . a homogén egyenlet ál- Mivel az inhomogén egyenlet szabad tagja 2, ezért az (1) = C2 . Behe= −1, tehát az inhomogén egyenlet általános megoldása = 2 kezdeti feltétel alapján a feladat megoldása Mn = 3n−1 − 1. inhomogén egyenlet egy partikuláris megoldása – az 1.1 ábra szerint – Mn lyettesítéssel azt kapjuk, hogy C 2 Mn = C1 3n−1 − 1. Az M1 1.1-3 megoldása Az egyenlet nem állandó együtthatós, tehát nem alkalmazhatjuk a módszerünket De ha felírjuk Cn = − 1) C n−1 +1 2(2n n alakban, majd behelyettesítjük C n−1 -et és így tovább, azt kapjuk, hogy − 1)(2n − 3) . 1 = (n + 1)n . 2 n Cn = n 2 (2n 2 (2n)! 2n (n + 1)!n! = homogén egyenlet partikuláris megoldását kapjuk, hogy

2 − C3 = (1 − C2 )2n , = C 2 n2 n + C3 2n n +1 (0) = 1.1-4 megoldása A homogén egyenlet általános megoldása xn (1) xn ! 1 n . n C 1 2 . Keressük az in- alakban. Behelyettesítve azt (1) amely minden n-re igaz, ha xn = n C 2 n2 + C3 gyök. Megoldások 41 = 1 és C3 = 2. Így az általános megoldás n megoldás xn = (n − 2)2 + 2. Tehát C 2 1.2-1 megoldása Legyen ez a szám an Ekkor a0 an xn = C1 2n + n2n + 2, de mivel x1 = 0, a = 1, a1 = 1, a2 = 0 és = b1 bn−2 + b2 bn−3 + · · · + bn−2 b1 ahol bk a k csúcsú bináris fák számát jelenti. Innen A(z) −1−z=z B(z) an − 2) = n(n + 1) 2n ahonnan −1
2 , ! −2 . n−1 2(n = bn − 2bn−1 , hiszen ha hiányzik egy fából a bal − 1 pontú bináris fát kapunk. Mivel mind De megkaphatjuk egyszerubben  is: an oldali részfa, akkor a gyökeret elhagyva egy n a bal, mind a jobb részfa hiányozhat, kétszer kell levonni ezek számát az összes bináris

fa számából.  generátorfüggvény. Ekkor 1.2-2 megoldása Legyen ez a szám cn és C(z) a megfelelo cn = c1 cn−2 + c2 cn−3 + · · · + cn−2 c1 . Innen C(z)  2 − 1 − z = z C(z) − 1 , ahonnan C(z) + 2z − 1 = √ 1 − 4z2 2z . Ezt sorba fejtve azt kapjuk, hogy C(z) =1+ X n n≥0 ! 2n 1 +1 2n+1 z n , ahonnan c2n = 0, c2n+1 1.2-3 megoldása Legyen H(z) = = n +1 P n≥0 ha n ! 2n 1 n , ha n ≥1 ≥0. n n Hn z . Beszorozzuk z -nel az egyenlet mindkét ol-  dalát, és összegezzük 1-tol. X n Hn z =2 n≥1 X n Hn−1 z n≥1 H(z) H(z) = 1 − 2z − 1 1 −z z n . ! 1 = 2zH(z) + 1 X n≥1 Innen Ahonnan + 1 = −z X −1 . n n 2 z n≥0 − X n z n≥0 . 42 Megoldások Innen pedig = 2n − 1 . Hn n 1.2-4 megoldása Beszorozzuk z -nel az egyenlet mindkét oldalát, majd összegezzük 1 z2 Ha P n≥0 n Fn z = X F n+2 z n+2 X 1 = F n+1 z z n≥0 n+1 + n≥0 X n

X + Fn z z n≥0 n . n≥0 F(z), akkor 1 z 2   −z = F(z) 1 z F(z) 1 + F(z) + . −z 1 Innen behelyettesítés és számítások után F(1/z) = z (z 2 2 − 1)(z2 − z − 1) ahol 1 α= + z = − 1)(z − α)(z − β) (z √ 5 2 Ekkor , β= 1 √ − 5 = lim z1 C 2 (n) = lim C 3 (n) = lim zα z (z − α)(z − β) z (z zβ (z − 1)(z − α) −1 = −1, αn+1 , (α − 1)(α − β) = βn+1 . (β − 1)(β − α) n+1 z 1 = = n+1 − 1)(z − β) . 2 n+1 C 1 (n) , A számítások elvégzése után Fn √ n   1 + 5    = C1 (n) + C2 (n) + C3 (n) = −1 +  5 +3 2 1.2-5 megoldása Legyen U (z) = P n≥0 n un z és V (z) √ 5 10 = √ n   1 − 5    + 2 P n≥0 5 −3 √ 5 10 n . n vn z . Mindkét egyenletet z -nel  szorozva, majd összegezve, a következoket kapjuk: (1 − z2 )U (z) − zV (z) = 1 + z , V (z) = (1

+ z)U (z). Innen U (z) V (z)  ol  un Az elsob vn =3·2 n−1 = , ha n n 2 = (1 + z)U (z) = = 1 1 − 2z , 1 =z =− + 1 − 2z 2 1 3 2 · 1 1 − 2z . adódik. A másodikból sorba fejtés után azt kapjuk, hogy v0 = 1 és ≥ 1.  muveleteket 1.3-1 megoldása Ha csak az algoritmusban ténylegesen jelen levo  vesszük Megoldások 43 gyelembe (tehát eltekintünk a ciklusváltozó és a függvényérték kiszámításától), akkor a  muveletek  száma a következo: + − ∗ / ← − k + 1)(k − 1) −k+1 (n − k + 1)k n−k+1 (2n − 2k + 1)k Esetünkben n = 1000, k = (n n 4, ezért 2991 összeadást, 997 kivonást, 3988 szorzást, 997 osztást és 7972 értékadást kapunk eredményül.  az 1.22 pontban alkalmazott eljárással eljutunk a 1-1. megoldása Az (12) egyenletbol,  következohöz: a0 X(z) + a1  z X(z)  − x0 + · · · + ak  z k X(z)  − x0 − x1 z − · · · − xk−1 zk−1 = 0 . Majd átrendezés után

azt kapjuk, hogy  X(z) a0 + a1 z + ··· + ak zk  = a1 z x0 + ··· + ak zk x0
+ x1 z + · · · + xk−1 zk−1 . Erre csak akkor nem alkalmazható a módszer, ha a jobb oldal azonosan nulla. A jobb oldalt k  kapjuk: z -nal szorozva, majd átalakítva, a következot z k −1 (a1 x0 + a2 x1 + · · · + ak xk−1 ) + zk−2 (a2 x0 + a3 x1 + · · · + ak xk−3 ) + · · · + z2 (ak−2 x0 + ak−1 x1 + ak x2 ) + z(ak−1 x0 + ak x1 ) + ak x0 .  nullával. Ezért a kifejezés csak akkor lehet azonosan nulla, ha Az ak sohasem lehet egyenlo x0  pedig = 0, x1 = 0, . , xk−1 = 0, ebbol azonnal következik, hogy ekkor xn = 0 minden n-re. 1-2. megoldása Az egyenlet megoldását ugyanúgy végezzük, mint a valós számok esetében Az a kérdés, hogy a megoldás valós lesz-e vagy komplex Mivel a komplex gyökök mindig párosával jelennek meg (egy komplex szám és a konjugáltja), a C i -k is párosával fognak megjelenni, mindegyik komplex számnak

meglesz a konjugált párja, ezért összegzéskor a tisztán képzetes részek kiesnek, tehát az eredmény mindig valós lesz. Tartalomjegyzék Tartalomjegyzék . 5  Eloszó . 5 I. ALAPOK . 10 Bevezetés . 11 1. Rekurzív egyenletek (Kása Zoltán) . 12 1.1 . 13 1.11 Állandó együtthatós homogén lineáris rekurzív egyenletek . 13 1.12 Állandó együtthatós inhomogén lineáris rekurzív egyenletek . 18 Generátorfüggvények és rekurzív egyenletek . 20 1.21 Értelmezés és muveletek  . 20 1.22 Rekurzív egyenletek megoldása generátorfüggvényekkel . 24 Állandó együtthatós inhomogén lineáris rekurzív egyenlet . 24 Bináris fák száma . 26 Levelek

száma n csúcsú bináris fák halmazában . 27 n csúcsú, k levelu  bináris fák száma . 28 . 30 . 34 Irodalomjegyzék . 36 Tárgymutató . 37 Névmutató . 38 Megoldások . 40 1.2 Lineáris rekurzív egyenletek 1.23 1.3 A Z-transzformáció módszere Numerikus megoldás