Umění programování, 1. díl - Základní algoritmy
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Umění programování, 1. díl - Základní algoritmyUmění programování, 1. díl - Základní algoritmy

 

Umění programování, 1. díl - Základní algoritmy

Google       Google       5. 9. 2009       25 536×

Recenze jedné z nejvlivnějších učebnic programování od světoznámého autora, držitele Turningovy ceny, IEEE Computer Pioneer Award či americké národní medaile za vědu, Donalda Ervina Knutha.

Reklama
Reklama

Série knih Umění programování má celkem 5 svazků a 10 kapitol. Tato recenze je psána o prvním svazku, zvaném Základní algoritmy a nesoucím 2 kapitoly celého mistrovského díla. Umění programování je opravdu velmi rozsáhlý zdroj pro teoretické i praktické řešení programátorských problémů od elementárních výpočtů až po složité kombinatorické problémy. Jak sám autor píše, kniha je stále ve vývoji a po přepracování všech svazků na třetí vydání se chystá znovu celou sérii aktualizovat pro zachycení všech ostatních prvků moderního programování. Struktura celého veledíla vypadá následovně:

Svazek 1. Základní algoritmy

  • Kapitola 1. Základní principy
  • Kapitola 2. Informační stuktury

Svazek 2. Seminumerické algoritmy

  • Kapitola 3. Náhodná čísla
  • Kapitola 4. Aritmetika

Svazek 3. Řazení a vyhledávání

  • Kapitola 5. Řazení
  • Kapitola 6. Vyhledávání

Svazek 4. Kombinatorické algoritmy

  • Kapitola 7. Kombinatorické vyhledávání
  • Kapitola 8. Rekurze

Svazek 5. Syntaktické algoritmy

  • Kapitola 9. Lexikální prohledávání
  • Kapitola 10. Lexikální analýza

Cvičení

Kniha je bohatě protkána velmi vydařenými cvičeními, která následují po každé podkapitole nebo chcete-li, po každém rozebíraném problému. Většinu cvičení by měl zvládnout člověk se středoškolskou znalostí matematiky, a to včetně diferenciálního a integrálního počtu či znalosti komplexních čísel. Cvičení spíše matematického rázu jsou v knize označována písmenem M, písmeny VM jsou označována cvičení, jež vyžadují znalost některých věcí z vysokoškolské matematiky. Série má svoji hiearchii i co se týče náročnosti cvičení na vypracování. Autor ji popisuje čísly 00 - 50, a to s následujícím popisem:

  • 00 - okamžitá odpověď
  • 10 - jednoduchá (do jedné minuty)
  • 20 - průměrná (čtvrt hodiny)
  • 30 - středně obtížná
  • 40 - semestrální projekt
  • 50 - výzkumný problém

Jak už jste jistě postřehli, narazíte i na cvičení nazvaná jako výzkumný problém. V praxi to znamená problém, na který dosud nebylo nalezeno plně uspokojivé řešení. Jako příklad jednoho takového výzkumného problému uvedu následující cvičení. [Poznámka: Algoritmus E uvedený ve cvičení níže je algoritmus pro zjištění největšího společného dělitele dvou čísel.]

[50] (R. W. Floyd) Vytvořte počítačový program, který na vstupu převezme program v nějakém programovacím jazyce a nepovinně také jistá tvrzení a dále se pokusí doplnit zbývající tvrzení potřebná k důkazu správnosti programu. (Tento program by se například měl pokusit dokázat platnost Algoritmu E, přičemž vyjde jen z tvrzení A1, A4 a A6. Další výklad viz příspěvky R. W. Floyd a J. C. King, IFIP Congress proceedings, 1971.)

Kapitola 1. - Základní principy

V první kapitole je na prvních několika desítkách stran shrnut a podrobně vysvětlen matematický základ, který budete ke čtení celé série potřebovat. Pokud to vezmu popořadě, jako první vás čeká osvětlení principů matematické indukce, která je, jak sám autor poznamenává, nesmírně důležitá pro rozbor algoritmů či matematických problémů. Dále následuje náhled do problematiky čísel, mocnin a logaritmů, poté operace se součty a součiny, použití celočíselných funkcí a úvod do teorie čísel. Na dalších stranách se setkáte s kombinatorickými problémy, a to přesně s permutacemi, faktoriály a binomickými koeficienty. Poté následují harmonická a Fibonacciho čísla, což je problematika číselného rozvoje, a v neposlední řadě generující funkce pro práci s posloupnostmi čísel. Jako dvě poslední podkapitoly matematické části shledáte analýzu algoritmů a asymptotickou reprezentaci zahrnující O-notace, Eulerův sumační vzorec a některé asymptotické výpočty. Celá tato matematická část je pojata do potřebné hloubky a s potřebnou dávkou vysvětlení, aby byly použité vztahy relativně snadno pochopitelné a, jak již jsem řekl na začátku recenze, člověk se znalostí středoškolské matematiky by se neměl setkat s žádným větším problémem. Za každou výše zmíněnou problematikou samozřejmě následuje sada cvičení, na níž si můžete zjistit, zda onu problematiku zcela chápete. Cvičení jsou samozřejmě opatřena řešeními, jež naleznete na konci knihy.

V dalším pokračování 1. kapitoly vás autor seznámí s počítačem MIX, pro nějž budou vytvořeny vzorové algoritmy. Pro kódovou prezentaci řešených problémů bylo použito strojového jazyka (ASSEMBLER) pro tento počítač. Jak autor zmiňuje, mohl použít některý z vyšších programovacích jazyků, ale pro rozsáhlou použitelnost zvolil jazyk strojový. Možná se zaleknete, že počítač MIX je stroj z 60. - 70. let minulého století, ale nejde zde o naučení se programovacího jazyka, ale o pochopení principů programování, jež jsou používanými základy dodnes. Tím samozřejmě myslím, že kniha je pojata podle nejnovějších programátorských trendů. Mimoto D. E. Knuth připravuje, po přepracování všech knih na 3. vydání, vydání čtvrté, které již bude psáno pro počítač MMIX 2009. Ale abych se vrátil k obsahu kapitoly. Jsou zde popsány vlastnosti počítače MIX a možnosti strojového jazyka pro něj použitého. Seznámíte se zde se základními příkazy pro práci s daty a pamětí, dále s prvními jednoduchými příklady algoritmů napsaných v ASSEMBLERU. Na posledních listech první kapitoly se seznámíte s některými základními technikami programování - například s podporgramy, koprogramy, interpretačními programy a vstupy a výstupy.

Kapitola 2. - Informační struktury

Kapitola Informační struktury je tvořena z pěti podkapitol, z nichž jsou dvě dále bohatě rozvinuté do několika dílčích problémů. V této části se velmi dobře a podrobně seznámíte se strukturovanými proměnnými (jako je například pole) a s informačními strukturami jako takovými, s nimiž se naučíte pracovat v mnoha různých směrech. Abych vás obeznámil, s čím vším se v kapitole setkáte, tak to shrnu do kratičké rekapitulace témat. Hned po úvodu do problematiky vás autor zavede do tajů lineárních seznamů, což jsou jednodušší informační struktury, které se dále dělí na zásobníky, fronty a oboustranné fronty, dále na kruhové seznamy, obousměrné propojené seznamy a pole a ortogonální seznamy. Důležitými pojmy pro práci s těmito prvky jsou sekvenční a spojová alokace, jež jsou zde také precizně popsány. Druhou obsáhlejší podkapitolou jsou stromy, což znamená již složitější větvené struktury. Je zřejmé, že práce se stromy bude mnohem náročnější než práce s lineárními seznamy. Ovšem díky autorovým zkušenostem se vaše znalosti obohatí o spoustu nových tipů a fíglů, jak tyto struktury efektivně ovládat. Nastíním vám také výčet toho, co se v kapitole dozvíte. Zaprvé je to procházení binárním stromem a reprezentace stromu binárním stromem, posléze i jiné reprezentace stromu. V rozsáhlejším měřítku autor probírá základní matematické vlastnosti stromů a nakonec seznamy a uvolňování paměti. Ke konci knihy se dozvíte i něco o vícenásobně propojených strukturách a dynamické alokaci paměti.

Stejně jako předešlý obsah knihy je tato část velice dopodrobna popsaná, tudíž není problém ji pochopit. Autor se hodně věnuje teoretické části struktur a práce s nimi. Krom příkladových algoritmů je zde opět široká škála cvičení, na nichž si ověříte, do jaké hloubky jste problém pochopili. Kapitola shrnuje vesměs ta nejdůležitější fakta o informačních strukturách, jejich statické a dynamické vlastnosti či algoritmy pro vytváření, změny, přístup a odstraňování strukturálních informací. Pro práce se strukturami, především stromy je potřebná dobrá znalost diagramů, množin a matic, ale o tom si samozřejmě přečtete vše potřebné v předešlé kapitole.

Knihu vám vřele doporučuji, protože se jedná o opravdový skvost programátorské literatury a domnívám se, že by neměla chybět v knihovně žádného člověka, který se chce o programování (navrhování algoritmů) do hloubky zajímat.

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

4 názory  —  4 nové  
Hlasování bylo ukončeno    
0 hlasů
Google
(fotka) Tomáš BobekAutor je designérem stránek (2D grafika), ovládá jazyky HTML, CSS, PHP, JavaScript a zajímá se o programování v Javě.Krom programujte.com se podílí na projektech maths.cz (jako redaktor a grafik), ceskewebstudio.cz (jako designér) a webber.cz (jako JavaScript scriptař). Ostatní volný čas rád tráví s přáteli nebo sportuje (tenis, nohejbal, hokejbal, závodně fotbal).
Web     Twitter     Facebook    

Nové články

Obrázek ke článku Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Reklama
Reklama
Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

Obrázek ke článku Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres HCPP16 pořádá od 30. září do 2. října nezisková organizace Paralelní Polis již potřetí, a to ve stejnojmenném bitcoinovém prostoru v pražských Holešovicích. Letos přiveze na třídenní konferenci přes 40 většinou zahraničních speakerů – lídrů z oblastí technologií, decentralizované ekonomiky, politických umění a aktivismu. Náměty jejich přednášek budou také hacking, kryptoměny, věda, svoboda nebo kryptoanarchie.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý