Algoritmy a datové struktury objektově

od Ivan Ryant

práce na učebnici algoritmizace pro gymnázia

Informace z profilu

Jsem softwarový inženýr, učitel informatiky na gymnáziu Ústavní v Praze 8 a odborný asistent na ČVUT FIT. V současné době se pokouším napsat dvě učebnice: jednu učebnici pokročilého programování pro středoškoláky (a možná i pro začínající vysokoškoláky) a druhou učebnici informatiky pro gymnázia.

  • Křestní jméno: Ivan
  • Příjmení: Ryant
  • E-mailová adresa: ryanti@acm.org

Algoritmy a datové struktury objektově

ADSO je učebnice algoritmů a datových struktur pro pokročilé programátory na úrovni střední školy. Už jsem ji dokončil. Je to však i nadále živý projekt. Rád bych zde zveřejňoval informace o projektu, aktualizace a dodatky. Jsou tu také ke stažení cvičení a prezentace.

Errata

  • Opravy chyb, které jsou ve výtiscích z června 2017, jsou uvedeny v dokumentu Errata.pdf a v prezentaci.
  • V dotisku z června 2018 tyto chyby již nejsou.

Soubory ke stažení

ADSO_pascal.zip

cvičení k učebnici ADSO v Pascalu

368,5KB | Pondělí, 19 prosinec 2016 | Detaily

ADSO_PruchodSachovnici_javadoc.zip

dokumentace k šachovým úlohám

222,5KB | Neděle, 07 květen 2017 | Detaily

ADSO_java.zip

cvičení k učebnici ADSO v Javě

1,4MB | Úterý, 16 květen 2017 | Detaily

ADSO_Library_javadoc_brief.zip

stručná dokumentace ke knihovně objektů ADSO

1,2MB | Úterý, 16 květen 2017 | Detaily

ADSO_Library_javadoc_detail.zip

snad až příliš podrobná dokumentace ke knihovně objektů ADSO

1,3MB | Úterý, 16 květen 2017 | Detaily

Errata.pdf

Opravte si prosím v učebnici...

86KB | Čtvrtek, 05 říjen 2017 | Detaily

ADSO_Prezentace.zip

prezentace k učebnici ADSO

1,5MB | Čtvrtek, 05 říjen 2017 | Detaily

ADSO_opraveneListy.pdf

sazba opravených listů, ve kterých byly chyby

234,4KB | Sobota, 07 říjen 2017 | Detaily

ADSO_opraveneStranky.pdf

sazba opravených stránek, ve kterých byly chyby

127,4KB | Sobota, 07 říjen 2017 | Detaily

programovani__prezentace_priklady.zip

Prezentace a příklady na témata: algoritmizace, design a projektování

1,4MB | Čtvrtek, 19 červenec 2018 | Detaily

Obsah

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

 

Komu je učebnice určena

(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.

Komu děkuji a za co

(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

Účel a ohlédnutí

(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

Ústřední knihovna VŠB-TUO

Deponováno v Institutu geoinformatiky, nelze půjčit. Viz https://katalog.vsb.cz/documents/188926?locale=cs

Ivan Ryant, 28 červenec 2017, 5:41 | Komentáře (0)

Vědecká knihovna na Kladně

Další knihovna, kde si lze půjčit učebnici:

  • Středočeská vědecká knihovna v Kladně
Ivan Ryant, 12 červenec 2017, 8:11 | Komentáře (0)

Další knihovna

Další knihovna, kde si lze půjčit učebnici:

  • Knihovna Akademie věd České republiky
Ivan Ryant, 20 červen 2017, 1:39 | Komentáře (0)

Půjčte si učebnici ve své veřejné knihovně

V současné době je učebnice v těchto knihovnách:

  • Národní knihovna ČR
  • Moravská zemská knihovna
  • Státní technická knihovna
  • Městská knihovna v Praze
  • Vědecká knihovna v Olomouci
  • Jihočeská vědecká knihovna v Českých Budějovicí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.

Ivan Ryant, 08 červen 2017, 10:28 | Komentáře (1)

Nová prezentace ADSO

Hotovo.

Ivan Ryant, 01 červen 2017, 1:49 | Komentáře (0)
Pohled byl zobrazen 3725x od 30 květen 2014 do 2 říjen 2022