Ústřední knihovna VŠB-TUO
Deponováno v Institutu geoinformatiky, nelze půjčit. Viz https://katalog.vsb.cz/documents/188926?locale=cs
od Ivan Ryant
práce na učebnici algoritmizace pro gymnáziaJsem softwarový inženýr a učitel informatiky v důchodu. Působil jsem na gymnáziu Ústavní v Praze 8 a byl jsem odborným asistentem na ČVUT FIT. Vydal jsem učebnici pokročilého programování pro středoškoláky a v budoucnu bych rád pokračoval v práci na učebnici informatiky pro gymnázia.
ADSO je učebnice algoritmů a datových struktur pro pokročilé programátory na úrovni střední školy. Dokončil a vydal jsem ji v roce 2017. Zde jsem zveřejnil informace o projektu, aktualizace a dodatky. Jsou tu také ke stažení cvičení a prezentace. Nyní již na projektu nepracuji a ani jej nehodlám v budoucnu rozvíjet. O komentáře a diskusi jsem ztratil zájem. V případě potřeby je možné poslat mi e-mail.
dokumentace k šachovým úlohám
stručná dokumentace ke knihovně objektů ADSO
snad až příliš podrobná dokumentace ke knihovně objektů ADSO
sazba opravených listů, ve kterých byly chyby
sazba opravených stránek, ve kterých byly chyby
Prezentace a příklady na témata: algoritmizace, design a projektování
Odborná recenze . . . 7
Poděkování . . . 8
Cíle a východiska . . . 9
1 Základní pojmy . . . 14
1.1 Algoritmus . . . 14
1.1.1 Formální zpřesnění pojmu algoritmus . . . 17
1.1.2 Nealgoritmické úlohy . . . 20
1.1.3 Shrnutí . . . 26
1.2 Výpočtová složitost . . . 27
1.2.1 Porovnávání výpočtové složitosti algoritmů . . . 29
1.2.2 Formalizace výpočtové složitosti . . . 32
1.2.3 Empirické zjišťování výpočtové složitosti . . . 34
1.2.4 Shrnutí . . . 35
2 Úloha abstraktních datových typů . . . 36
3 Posloupnosti a operace s nimi . . . 40
3.1 Posloupnost jako ADT . . . 40
3.2 Zásobník . . . 42
3.2.1 Příklad: polská kalkulačka . . . 48
3.2.2 Implementace obecného zásobníku . . . 53
3.2.3 Implementace zásobníku polem . . . 59
3.2.4 Implementace zásobníku spojovým seznamem . . . 61
3.2.5 Cvičení 1 . . . 64
3.3 Fronta . . . 65
3.3.1 Příklad: klouzavý průměr . . . 69
3.3.2 Implementace fronty polem . . . 74
3.3.3 Implementace fronty spojovým seznamem . . . 77
3.3.4 Implementace fronty dvojicí zásobníků . . . 79
3.3.5 Cvičení 2 . . . 81
3.3.6 Cvičení 3 . . . 82
3.4 Obecná posloupnost . . . 82
3.4.1 Specifikace datového typu posloupnost . . . 82
3.4.2 Příklad: směrová čísla . . . 86
3.4.3 Implementace posloupnosti dvojicí zásobníků . . . 88
3.5 Implementace posloupnosti seznamem . . . 89
3.5.1 Implementace lineárního a kruhového seznamu polem . . . 90
3.5.2 Prostý spojový seznam . . . 94
3.5.3 Spojový seznam se zaostalým běžným členem . . . 98
3.5.4 Spojový seznam s vlečeným členem . . . 102
3.5.5 Obousměrně propojený seznam . . . 103
3.5.6 Cvičení 4 . . . 106
3.5.7 Cvičení 5 . . . 107
3.5.8 Cvičení 6 . . . 108
3.6 Shrnutí . . . 108
4 Vyhledávací datové struktury . . . 109
5 Vyhledávací posloupnost . . . 112
5.1 Obyčejná vyhledávací posloupnost . . . 115
5.2 Vyhledávání s pomocí zarážky . . . 117
5.2.1 Cvičení 7 . . . 118
5.3 Reorganizovaná posloupnost . . . 119
5.3.1 Cvičení 8 . . . 122
5.4 Uspořádaná posloupnost, medián . . . 122
5.5 Seřazená posloupnost . . .130
5.6 Shrnutí . . . 136
6 Algoritmy řazení . . . 137
6.1 Řazení přímým výběrem . . . 137
6.2 Řazení vkládáním . . . 141
6.2.1 Cvičení 9 . . . 143
6.3 Bublinkové řazení . . . 143
6.3.1 Cvičení 10 . . . 147
6.4 Řazení sléváním . . . 148
6.4.1 Cvičení 11 . . . 152
6.5 Řazení rozdělováním . . . 153
6.5.1 Cvičení 12 . . . 159
6.5.2 Výpočet mediánu . . . 160
6.5.3 Cvičení 13 . . . 162
6.6 Counting sort . . . 163
6.6.1 Cvičení 14 . . . 167
6.7 Řazení haldou . . . 167
6.8 Shrnutí . . . 171
7 Stromy . . . 173
7.1 Graf a strom . . . 174
7.2 Halda . . . 178
7.2.1 Cvičení 15 . . . 183
7.3 Binární vyhledávací strom, zadání . . . 184
7.4 Bisekce . . . 188
7.4.1 Cvičení 16 . . . 190
7.5 Binární vyhledávací strom, návrh řešení . . . 191
7.5.1 Cvičení 17 . . . 197
7.6 Vyvážené binární stromy . . . 198
7.6.1 Cvičení 18 . . . 202
7.7 Shrnutí . . . 203
8 Rozptýlené tabulky . . . 205
8.0.1 Cvičení 19 . . . 212
8.0.2 Shrnutí . . . 213
9 Prohledávání do hloubky a do šířky . . . 214
9.1 Stavový prostor . . . 214
9.2 Prohledávání do hloubky . . . 218
9.2.1 Cvičení 20 . . . 221
9.2.2 Příklad: proskákat šachovnici koněm . . . 222
9.2.3 Cvičení 21 . . . 224
9.3 Prohledávání do šířky . . . 224
9.3.1 Cvičení 22 . . . 225
9.3.2 Příklad: hledání nejkratší cesty . . . 226
9.4 Využití heuristiky . . . 230
9.5 Shrnutí . . . 234
10 Práce s grafy . . . 235
10.1 Další pojmy z teorie grafů . . . 235
10.2 Reprezentace grafu . . . 235
10.3 Komponenty souvislosti . . . 244
10.3.1 Cvičení 23 . . . 246
10.4 Minimální kostra . . . 247
10.4.1 Cvičení 24 . . . 249
10.5 Topologické uspořádání . . . 250
10.5.1 Cvičení 25 . . . 251
10.6 Hledání nejkratší cesty . . . 253
10.6.1 Floydův algoritmus . . . 253
10.6.2 Cvičení 26 . . . 257
10.6.3 Dijkstrův algoritmus . . . 258
10.6.4 Cvičení 27 . . . 264
10.7 Shrnutí . . . 264
11 Techniky návrhu efektivních algoritmů . . . 265
12 Závěr . . . 270
(opsáno z úvodních kapitol)
Tato učebnice je určena zájemcům o programování na úrovni střední školy. Předpokládám, že čtenář již zvládl některý programovací jazyk a že absolvoval základní kurs objektového designu nepřesahující úvodní kurs softwarového inženýrství MIT (viz MIT softwarové inženýrství, http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-170Fall-2005/CourseHome/index.htm).
V této knize čtenář najde celou řadu příkladů lepšího nebo horšího objektového designu. Budu se snažit důkladně odůvodnit svoje designérská rozhodnutí, naznačovat alternativy a vážit argumenty pro ně a proti nim. Všechno, co se týká designu, sice vysvětlím, ale nebudu to vykládat systematicky. K tomu sloužil kurs objektového designu.
(opsáno z úvodních kapitol)
Děkuji doc. Pavlu Töpferovi za knihu Algoritmy a programovací techniky, ze které vycházím. Děkuji prof. Barbaře Liskovové a prof. Danielu Jacksonovi z Massachusetts Institute of Technology za zveřejnění jejich učebních textů Open Courseware, kde jsem hledal útěchu v okamžicích beznaděje nad Töpferovými pascalskými programy.
Děkuji kolegům Dr. Miroslavu Balíkovi a doc. Josefu Kolářovi z FIT ČVUT za dobré rady a připomínky. Děkuji Ing. Ivo Fišerovi, řediteli společnosti xPhoNet CZ s.r.o. za konzultace a nápady, jak zlepšit celý projekt. Dále děkuji Ing. Štěpánovi Jičínskému ze společnosti Robert Bosch odbytová s.r.o. za laskavou konzultaci. Dr. Robertu Perglovi z FIT ČVUT patří můj nevšední dík za recenzi a všestrannou podporu.
Děkuji kolegyni z gymnázia Ústavní v Praze Mgr. Michæle Drozdové za kontrolu pravopisu (zodpovědnost za chyby, které jsem v textu nechal, nesu já). Děkuji pracovníkům Metodického portálu RVP MŠMT za možnost předložit pracovní verzi projektu této učebnice a příslušného softwaru k veřejné diskusi.
Děkuji svým studentům z gymnázia Ústavní Pavlu Hájkovi a Lukáši Němcovi, s jejichž pomocí jsem se učil programovat v Delphi, Janu Černému za opravy a připomínky a zejména Veronice Steffanové, která kriticky a pečlivě vypracovala všechna cvičení a opravila při tom mnoho mých chyb.
V Praze v září 2009 – v dubnu 2017, Ivan Ryant
[1] Pavel Töpfer: Algoritmy a programovací techniky, Praha, PROMETHEUS 1995
[2] MIT Open CourseWare, http://ocw.mit.edu/index.html
[3] MIT úvod do algoritmů, http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm
(opsáno z úvodních kapitol)
Některé výpočetní postupy a některé struktury dat jsou v programování považovány za standardní, např.: bisekce, fronta, hledání nejkratší cesty v grafu. Programátoři je nevymýšlejí, nýbrž se je učí ve škole. V praxi je potom dokáží přizpůsobit na míru úloze, kterou právě řeší. Častěji však tyto postupy bývají k dispozici už naprogramované jako součást programovacího jazyka nebo knihovny, takže na programátorovi pak je, aby si jen správně vybral. Nicméně i k tomu potřebuje základní znalost standardních výpočetních postupů: Má k vyhledávání použít raději rozptýlenou tabulku, anebo vyhledávací strom? Vyplatí se strom vyvažovat? A třídit má raději haldou nebo přímým výběrem? Taková rozhodnutí jsou na denním pořádku a k řemeslu programátora patří, že se dokáže rozhodnout správně. A právě to je cílem tohoto kursu, ne víc.
Když Niklaus Wirth publikoval v roce 1975 učebnici Algorithms + Data Structures = Programs, způsobil převrat ve výuce programování, kde do té doby vládlo Knuthovo Umění programovat (The Art of Computer Programming) a série učebnic Sandry Forsythové. Nápad spojit postup výpočtu se zpracovávanou datovou strukturou byl v té době revoluční, ačkoli ne úplně ojedinělý. Jenže objektový jazyk Simula67 tenkrát působil jako něco exotického, co by se těžko dalo použít jinde než v oboru diskrétních simulací, a smalltalk s okny, menu a ikonami se právě rodil v Paloaltském výzkumném středisku firmy Xerox pod vedením Adély Goldbergové a Alana Kaye jako výzkumný pokus, který nedošel velkého uplatnění v praxi.
V té době už pár let existovala „computer science“ a zrovna vznikal nový obor nazývaný „software engineering“ – tenkrát ovšem ještě víc ironicky než vážně. Fred Brooks už zažil a popsal průšvihy s velkými programy, jejichž složitost přerostla programátorům přes hlavu, ale pověstný silver bullet nenašel. Velký program tehdy míval až desítky tisíc zdrojových řádků. Procesory běžely na megahertzových frekvencích a dokázaly vykonat snad až desítky tisíc operací v pohyblivé řádobé čárce za sekundu. Operační paměti mívaly desítky až stovky kilobajtů, výjimečně i megabajt. Dvousetmegabajtový výměnný disk byl médiem se zbytečně předimenzovanou kapacitou, kterou přece nikdo nemůže zaplnit. Výkonnost hardwaru nezadržitelně rostla, ale produktivita programátorů nikoli. Mluvilo se o softwarové krizi.
O softwarové krizi se dnes už tolik nemluví – ne proto, že by ji někdo vyřešil, ale spíš proto, že trvá už dlouho, a s nízkou kvalitou a produktivitou programátorské práce jsme se smířili. Jenom s těmi kapacitami a výkonnostmi hardwaru jsme o nějaké tři-čtyři řády dál, a to ne o řády dvojkové, nýbrž desítkové. Stejně se zvětšil i rozsah velkých softwarových systémů, deset tisíc řádků se dnes považuje za malý až středně velký program. Programuje se jinak než před čtyřiceti lety. Programátoři dnes myslí jinak: daleko víc přemýšlejí o architektuře systému, o opakované použitelnosti, využívají aplikačních rámců a komponent, dbají na co nejslabší spřaženost modulů, aby se programy daly dodatečně modifikovat. A přece: postupy programování standardních úloh typu vyhledávání ve stromech, řazení nebo hledání nejkratší cesty v grafu se vyučují pořád stejně jako před těmi čtyřiceti lety. To, co jsme se se studenty pracně naučili v kursu objektového designu, bychom teď – v kursu algoritmů a datových struktur – měli popřít. Měli bychom psát programy, které postrádají robustnost a o kterých tedy víme, že je budeme těžko ladit a že je nebudeme moci znovu použít a modifikovat, až budeme řešit podobnou úlohu. To opravdu nešlo.
Proto jsem musel sednout a programy z Töpferovy učebnice Algoritmy a datové struktury přepsat do podoby robustního objektového systému. Dosáhl jsem toho, že každý dílčí problém řeším stručně, jednoduše a v přiměřených pojmech (např. když mám vyhledat prvek posloupnosti, používám operace posloupnosti a nezabývám se tím, zda posloupnost implementuji polem, spojovým seznamem nebo třeba dvojicí zásobníků). Každá úloha má svůj konfigurační modul, takže různá řešení téhož problému mohu snadno přepínat na jednom místě. Provozní měření nám umožňují průběžně sledovat výpočtovou složitost algoritmů a experimentovat s ní. Přímo do zdrojových programů jsou zabudována cvičení, takže studenti je mohou velmi snadno řešit a testovat. Až potud to vypadá jako báječný didaktický systém.
Tento didaktický systém je však bohužel na hony vzdálen možnostem praktického využití při psaní softwaru: v reálně používaném softwaru se zpravidla nevolí mezi sedmi možnostmi třídění ani mezi třemi způsoby, jak implementovat binární vyhledávací strom. Kromě toho náš výukový systém obsahuje mnoho desítek tříd a interfejsů, takže je příliš složitý, než aby se studenti mohli vyznat v jeho struktuře – konec konců jde o to, aby pochopili pár standardních algoritmů, ne o mentální zvládnutí složitého systému.
Na druhou stranu, když studenta postavím před spletitý systém s podrobným návodem na řešení jednoduché úlohy, zakusí něco ze života. V praxi totiž programátor zpravidla stojí před systémem, který nenaprogramoval on, nýbrž kolega (mnohdy bývalý kolega), takže se v systému nevyzná. Přesto musí do systému zasáhnout, něco tam opravit, dodělat nebo změnit. Musí lokalizovat místo zásahu, zorientovat se tam, zasáhnout a ověřit, zda zásah byl úspěšný.
Takže si myslím, že ta nezvládnutelná složitost zase nemusí být až tak moc na závadu.
[1] Niklaus Wirth: Algorithms + Data Structures = Programs, Prentice-Hall, Englewood Cliffs 1975 (slovenský překlad Ing. Pavla Fischera: Algoritmy a štruktúry údajov, Alfa, Bratislava 1988)
[2] Donald Knuth: Art of Computer Programmnig, vol. 1, Addison-Wesley, 1968 (česky v překladu Davida Krásenského vydal Computer Press v září 2008)
[3] Donald Knuth: Art of Computer Programmnig, vol. 3, Addison-Wesley, 1973
[4] Alexandra Illmer Forsythe et al.: Computer Science: Primer, John Wiley & Sons Inc (December 1969)
[5] Alexandra I. Forsythe, Thomas Keenan, Elliott Organick, and Warren Sternberg: Computer science: A first course, Wiley (1969)
[6] Alexandra I. Forsythe, Thomas A. Keenan: Computer Science: Fortran Language Programming, John Wiley & Sons, Inc. (Jan 1, 1970)
[7] Pavel Töpfer: Algoritmy a programovací techniky, Praha, PROMETHEUS 1995
Poznámky k práci na učebnici algoritmizace pro gymnázia
Deponováno v Institutu geoinformatiky, nelze půjčit. Viz https://katalog.vsb.cz/documents/188926?locale=cs
Další knihovna, kde si lze půjčit učebnici:
Další knihovna, kde si lze půjčit učebnici:
V současné době je učebnice v těchto knihovnách:
...a možná i v dalších, o kterých nevím. Žádejte ji k zapůjčení, má být v katalozích a k dispozici čtenářům.