Kombinatorikai algoritmusok
| dc.contributor.advisor | Papp, Zoltán | |
| dc.contributor.author | Albert, Andrea | |
| dc.contributor.department | DE--TEK--Informatikai Kar | en |
| dc.date.accessioned | 2006-08-02T09:49:51Z | |
| dc.date.available | 2006-08-02T09:49:51Z | |
| dc.date.created | 2005 | |
| dc.date.issued | 2006-08-02T09:49:51Z | |
| dc.description.abstract | Ez a dolgozat hasznos lehet a matematikát tanulóknak, egyetemi hallgatóknak egyaránt, de mindenekelőtt a matematikatanároknak, akik számítógépükön matematikai kísérleteket szeretnének végezni. Aki alaposan áttanulmányozza ezt a pár oldalt, az aktívan megismerkedhet – ha csak kis részével is – a matematika egyik alapvető ágával, a kombinatorikával.A dolgozat nyolc részből áll, mindegyik rész külön-külön is feldolgozható, és mindegyik rész végén találhatóak feladatok, melyek a megoldott problémák megértése után könnyen megoldhatóak, pár feladathoz a dolgozat végén útmutató is található. Az első részben a fontosabb rendezési algoritmusokat - a válogató rendezés, beszúró rendezés, shell rendezés, gyorsrendezés, ládarendezés - ismerhetjük meg. A második rész keresési algoritmusokról szól - egy n elemű halmaz k. elemét keresve több gondolat is célravezető lehet. A leggyorsabb az, ha egy olyan eljárást alkalmazunk, amelyik átrendez egy a[1..n] tömböt úgy, hogy például a középső elem előtt csak nála kisebb vagy egyenlő, utána csak nála nagyobb vagy egyenlő számok legyenek, és rekurzív módon ott folytatjuk az eljárást amelyik részben lehet a keresett elem. A harmadik részben a bináris kereséssel foglalkozunk. Azokat az értékeket, amelyek között keresünk, magunk állítjuk elő: ez a egészrész(t*i) (i = 1, 2, …, n) sorozat lesz, ahol t=1+√5/2. Ha a tömbben a keresett elem nem fordul elő, akkor n+1-et ad vissza. Több megoldást is adunk. A második esetben függvény nélkül oldjuk meg a feladatot, hogy a sikertelen keresést is közvetlenül jelezni tudjuk. Ez függvénnyel nem volna lehetséges, mivel a visszatérési érték a függvénnyel azonos típusú kell legyen. A harmadik programmal az 1, 2, 2, 3, 3, 3, …, n, n, …, n rendezett sorozatból a keresett számot annyiszor íratjuk ki, ahányszor az előfordul benne. A negyedik részben a bináris kitalálás témakörrel foglalkozunk, a számítógép minimális számú igen-nem válaszok segítségével találja ki, hogy melyik számra gondoltunk. Az ötödik részben az n_királynő problémával foglalkozunk. Például n = 8 esetén egy 8 x 8-as sakktáblán úgy helyezünk el 8 királynőt, hogy azok ne üssék egymást. Ez egy szép példa a visszalépéses eljárásmódra. Itt a probléma történetével is megismerkedhetünk. A hatodik részben betekintést nyerhetünk a permutációk világába, olyan érdekes programokon át, mint a ciklusokba szedés és a Jozefusz-permutáció. Egy kör alakú asztal körül n db ember ül. Körbejárva minden m-ediket kizárjuk, és a későbbi számlálásba nem számítjuk bele. A kizárt emberek sorszámából alkotott sorozatot (n,m)-Jozefusz-permutációnak hívjuk A hetedik részben kétszemélyes játékokkal foglalkozunk. A Nim és Négyzetes_Nim kőhalommal játszott játékokat ismerhetjük meg, és Withoff játékát, mely egy régi kínai játék, egy szép matematikai elmélettel. A nyolcadik részben a részösszeg problémával foglalkozunk. Ezt a híres problémát egy speciális esettel oldjuk meg: Ábel és Káin n darab aranyrögöt örökölnek. √1, √2, ..., √n uncia súllyal. Alkossunk két halmot ezekből, melyek a lehető legkevésbé különböznek egymástól. Egy jó, de nem szükségszerűen a legjobb megoldást adja az FFD heurisztika, az optimális megoldást a részöszeg program segítségével kapjuk. A fejezethez tartozó feladatok között megtaláljuk a rendezés egy érdekes alkalmazását, az arany permutációt. Az n számpárok (i, modf(i*t)), i = 1, ..., n rendezését fogjuk elvégezni, a második koordináta szerint, ahol t= √5-1/2. Az első koordinátákat adja vissza a program. Az eredmény az ún. arany permutáció 1..n-ig. A megfelelő programokkal megvizsgáljuk az arany permutáció meglepő tulajdonságait. | en |
| dc.description.degree | Ba | en |
| dc.format.extent | 47 | en |
| dc.format.extent | 121166 bytes | |
| dc.format.extent | 278808 bytes | |
| dc.format.mimetype | application/zip | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/2437/326 | |
| dc.language.iso | hu | en |
| dc.rights | no_restriction | en |
| dc.subject | rendezés | en |
| dc.subject | keresés | en |
| dc.subject | n-királynő | en |
| dc.subject | permutációk | en |
| dc.subject | játékok | en |
| dc.subject | részösszeg | en |
| dc.subject | FFD | en |
| dc.title | Kombinatorikai algoritmusok | en |
Fájlok
Eredeti köteg (ORIGINAL bundle)
1 - 2 (Összesen 2)
Nincs kép
- Név:
- szakdolgozat_741.pdf
- Méret:
- 272.27 KB
- Formátum:
- Adobe Portable Document Format
- Leírás:
- Szakdolgozat
Engedélyek köteg
1 - 1 (Összesen 1)
Nincs kép
- Név:
- license.txt
- Méret:
- 2.72 KB
- Formátum:
- Item-specific license agreed upon to submission
- Leírás: