Úgy tűnik, hogy a JavaScript le van tiltva, vagy nem támogatja a böngésző. Sajnáljuk, de az oldal néhány funkciójának működéséhez, többek között a rendeléshez engedélyeznie kell a JavaScript futtatását böngészőjében. Köszönjük!

Algoritmusok

Algoritmusok - Lovász László, Gács Péter - Régikönyvek
Algoritmusok - Régikönyvek Algoritmusok - Régikönyvek Algoritmusok - Régikönyvek Algoritmusok - Régikönyvek
(0 vélemény)

ELŐSZÓ Az algoritmus legáltalánosabb értelemben nem más, mint tervszerűség. Ha egy elvégzendő cselekvéssorozatot lépésről lépésre előre átgondolunk, megtervezünk, úgy is mondhatjuk, hogy algoritmust adunk egy bizonyos cél elérésére. Egy épület terve, vagy egy ételrecept - ilyen legtágabb értelemben vett algoritmus. Algoritmust követ a futballbíró, amikor mérkőzést vezet - hiszen előre el van tervezve, méghozzá nem is ő maga, hanem a játék szabályai mondják meg, hogy milyen szituációban mit kell ítélnie. Sok mindennapi tevékenységünk szigorúan véve nem algoritmikus. Megállhatunk közben töprengeni, vagy akár csak magunk elé meredni, hátha "beugrik" egy jó ötlet. Ha azonban sokszor kell őket végrehajtani, előbb-utóbb "algoritmizál" az ember. Gondoljunk például a csomagolásra valamilyen utazáshoz, vagy egy tárgy keresésére a lakásban. Egy tevékenységet csak akkor mondunk teljesen algoritmizáltnak, ha már pontosan leírtuk, elterveztük, hogy milyen lépéseket fogunk végrehajtani (esetleg a korábbi lépések eredményétől függően); végrehajtás közben további módosításra vagy gondolkodásra nincs szükség. Nemcsak fizikai tevékenységet, hanem gondolatit is lehet tervezni, "algoritmizálni". A bolti pénztáros, ha visszaad, egy egyszerű algoritmust követ, melynek segítségével végül is eljuttatja a vásárlónak a visszajáró pénzt. Egy hivatal eljárási rendje, egy zene kottája, egy bridzs-licitrendszer - algoritmusok. Persze sok ezek közül nem elégíti ki a szigorúbb kikötéseket: ugyanabból a kottából ugyanazt a zenét sokféleképpen le lehet játszani, ugyanabból a lapból ugyanazzal a licitrendszerrel lehet kis szlemmet játszani és nagy szlemmet bukni. Mindezek a tevékenységek érdekességüket, sőt értelmüket vesztenék, ha teljesen algoritmizálva volnának. A legjobb példákat a mindennapi életben használatos algoritmusokra a matematika szolgáltatja. Hogyan adunk (vagy szorzunk) össze két számot? Megtanultunk rá egy mindig működő, pontosan leírt, gépiesen végrehajtható eljárást, egy algoritmust. Ugyanez a helyzet az osztással, a gyökvonással, a háromszög területének kiszámításával, a százalékszámítással stb. Az általános iskolai matematikaanyag, de még részben a középiskolai is, főként algoritmusokat tanít az ilyen gyakran felvetődő feladatok megoldására. Talán meglepő egy "Algoritmusok" c. könyv részéről, ha ezzel a gyakorlattal kapcsolatban kételyeknek ad hangot. Véleményünk azonban az, hogy az emberi szellemi tevékenység lényege nem algoritmusok végrehajtása, hanem algoritmusok alkotása. Természetes, hogy bizonyos alapvető algoritmusokat (összeadás, szorzás) mindenkinek ismernie kell. Azonban éppen az alapfeladatokat olyan sokszor, annyira változó körülmények között kell megoldanunk, hogy egy adott algoritmust - akár a legközönségesebbet, például a szorzásért - legjobbnak, "egyedül üdvözítőnek" deklarálni nem lehet. Éppen a szorzással kapcsolatban látni fogjuk, hogy nagyon sok jegyű számok szorzására van gyorsabb, jobb eljárás, mint amit az iskolában tanultunk! Ilyen sok jegyű számok szorzására ma talán még nincsen szükség, de ahogy a számítások mennyisége növekszik - a hibák halmozódása miatt -, a pontosságot, tehát a jegyek számát is növelni kell. Könyvünk célja sem az, hogy algoritmusok lexikonja legyen. Sok feladatra adunk algoritmust, némelyekre több különbözőt is, de ezek főként példaként szolgálnak. Fő célunk az, hogy az olvasó arról kapjon képet, hogyan is kell algoritmust keresni, tervezni egy-egy feladat megoldására.

Sorozatcím:
Matematika műszakiaknak
Borító tervezők:
Sebes János
Kiadó:
Műszaki Könyvkiadó
Kiadás éve:
1978
Kiadás helye:
Budapest
Nyomda:
Egyetemi Nyomda
ISBN:
9631020673
Kötés típusa:
ragasztott papír
Terjedelem:
179 oldal
Nyelv:
magyar
Méret:
Szélesség: 14.00cm, Magasság: 20.00cm
Súly:
0.20kg
Kategória:
Bevezetés 9

1. fejezet.
Kombinatorikai algoritmusok 15
1.1. Szortírozás 17
1.1.1. Beszúrós 17
1.1.2. Összefésülés 18
1.1.3. Sorbarendezés 19
1.1.4. Átrendezés cserékkel 22
1.1.5. Legnagyobb és következő elemek 26
1.1.6. Mediánskeresés 27
1.2. A pakolási probléma 29
1.2.1. Próbálgatás módszerek 31


1.2.2. Intervallumpakolás 33
1.2.3. Párosítások 35
1.3. Útkeresés 39
1.3.1. Összefüggőség 39
1.3.2. A legrövidebb út 41
1.3.3. A leghosszabb út 44
1.4. Szuboptimális algoritmusok 47
1.4.1. A hátizsákfeladat 47
1.4.2. A fedési feladat 49
1.4.3. A kromatikus szám 53
1.5. Gráfok diagnosztikája 54
1 .5.1 . Összefüggőség 55
1.5.2. Kieséses verseny és egy rokon feladat 57
1.5.3. A probléma általánosítása 60

2. fejezet.
Kereső feladatok 63
2.1. A problémák problémája 64
2.1.1. Ahol egy kismadár is segíthet 64
2.1.2. A kielégíthetőség problémája — univerzális feladat 66 2.2. Nehéz kombinatorikai feladatok 70
6 2.2. Nehéz kombinatorikai feladatok 70
2.2.1. Közvetlen átfogalmazás 70
2.2.2. A háromszín-probléma 71
2.2.3. A pakolási probléma 73
2.3. Áttekintés 74

3. fejezet.
Algebrai algoritmusok 79
3.1. Gyorsabban is lehet szorozni 80
3.1.1. Nagy számok szorzása • 80
3.1.2. Nagy mátrixok szorzása 82
3.1.3. Polinomok szorzása 85
3.1.4. A véges Fourier-transzformált 88
3.2. Osztás helyett szorzás 90
3.2.1. Számok osztása 90
3.2.2. Hatványsorok és polinomok osztása 92
3.2.3. Az euklidészi algoritmus 97
3.2.4. Mátrixinvertálás 104


3.3. Polinomok kiértékelése 106
3.3.1. Pan alsó becslései 107
3.3.2. Prekondicionálás 113
3.3.3. Tabellázás és fordítottja, az interpoláció 117
3.4. Párhuzamos számolás 123
3.5. Moduláris algoritmusok 130
3.5.1. A kínai maradéktétel 130
3.5.2. Lineáris egyenletrendszer pontos megoldása 137

4. fejezet.
A kiszámíthatóság elméletéről 145
4.1. Az algoritmikus megoldhatóság 145
4.1.1. Az algoritmus fogalma 146
4.1.2. Az univerzális gép. A megállási feladat 148
4.1.3. Egyszerű eldönthetetlen feladatok 150
4.2. A számolósok terjedelméről 153
4.2.1. A terjedelem mérése 156
4.2.2. Optimális algoritmusok 158
4.2.3. Alsó becslések 160

Feladatmegoldások 163

Lovász László

1948 -
Lovász László (Budapest, 1948. március 9.) Széchenyi-nagydíjas, Bolyai-nagydíjas, valamint Bolyai János alkotói díjas és Wolf-díjas magyar matematikus, egyetemi tanár, a Magyar Tudományos Akadémia (és az amerikai National Academy of Science) rendes tagja. A számítógép-tudomány világhírű kutatója. 2006 és 2011 között az Eötvös Loránd Tudományegyetem Matematikai Intézetének igazgatója. 2014 óta a Magyar Tudományos Akadémia elnöke.

Lovász László  további könyvei

Hűségpont:
 
Antikvár könyv
900 Ft

Az Ön ajánlója

Még nincs vélemény a könyvről, legyen Ön az első aki véleményt ír róla...