Výuka

informatika | algoritmizace | OO design | algoritmy + datové struktury | zpět na osobní stránku | původně z 4. února 2011, doplněny aktuální poznámky 20. prosince 2022

Výuka

V únoru 2011 jsem psal dvě učebnice:

Na gymnáziu jsem v letech 2006 až 2010 vyučoval

V roce 2010 jsem svoje působení na gymnáziu omezil na výuku programování, protože odmítám degradovat výuku informatiky na pouhé cvičení studentů pro státní maturitu z ICT podle katalogu požadavků CERMAT a školního vzdělávacího programu gymnázia Ústavní. Povolání učitele jsem měl rád, trenéra dělat nechci.

Roku 2010 jsem se stal odborným asistentem na FIT ČVUT, kde jsem v zimním semestru 2010 a 2011 vedl cvičení z předmětu objektové modelování a v letním semestru 2011 a 2012 cvičení z předmětů softwarový projekt 1 a technická dokumentace. Do roku 2021 jsem se pak podílel na výuce předmětu konceptuální modelování.

Během sbírání materiálu na učebnici informatiky jsem připravil přednášku o pojmovém modelu světa v knize Genesis, kterou jsem přednesl dne 26.4.2012 v rámci Informatických čtvrtků FIT. V rámci Informatických večerů FIT v roce 2011 jsem přednesl přednášku o filosofických základech softwarového inženýrství.

Učebnice informatiky pro gymnázia

(ukázka: k čemu má tato učebnice sloužit a k čemu nikoli)

Návody se najdou v příručkách, nápovědách a na fórech v internetu. Tato kniha není sbírka návodů, podle které by si student mohl nacvičit, jak správně spustit tu či onu funkci toho či onoho produktu. Na druhou stranu si myslím, že středoškolská informatika by se měla učit především prakticky, na projektech, samostatných pracech, při přípravě referátů, týmové práci nebo aspoň samostatnou prací na jednotlivých cvičeních. Některé osvědčené náměty na samostatnou práci zde uvádím. Součástí studia ovšem je i to, že student si musí umět sám najít a vybrat vhodný nástroj k řešení problému, musí se orientovat ve fórech na webu, v příručkách a v nápovědách.

Úmyslně zde neřeším otázku, zda každý student při samostané práci na úlohách ovládne všechny předepsané nástroje, ani zda si osvojí všechny požadované dovednosti. Jestli někoho zajímá můj názor (nad rámec této knihy), tak já si tedy myslím, že se jedná o podružné cíle, jejichž dosažení nesmíme obětovat hlavní účel, kterému má výuka informatiky (IVT, ICT) sloužit. Tento účel je celkem jasně vyjádřen v Rámcovém vzdělávacím programu (RVP) Ministerstva školství ČR. A jak se píše už v Kámasutře, prostředky je třeba volit.

Tolik k otázce, k čemu tato kniha neslouží. A k čemu slouží?

V této knize se snažím srozumitelně vysvětlit všechno, čemu má rozumět absolvent gymnázia podle požadavků RVP. Myslím, že se jedná o poměrně přehlednou, robustní a logicky konzistentní strukturu znalostí. Otázek, na které (v rámci svého tématu) z principu nedává odpověď, není příliš mnoho. Zato otevřených problémů, návazností na jiné obory a námětů k dalšímu poznávání nabízí spoustu.

Pokud jde o formu, ta je dána obsahem: kniha se omezuje na znalostní strukturu, proto musí mít formu výkladu. Snažím se ovšem, aby čtenář v každém okamžiku věděl, proč má to či ono pochopit, zásadně motivuji čtenáře problémem nebo aspoň účelem. Výklad se snažím vést pokud možno formou epiktétovského dialogu mezi „já“ a „vy“, která čtenáře vede k polemice, ke kritické úvaze a k vytvoření vlastního názoru. Samozřejmě, že výklad (ještě hůře frontální výklad) je jednou z nejhorších forem, jak vyučovat informatiku ve třídě. S metodou a formou výuky si ovšem už musí poradit učitel sám – má na to vysokou školu a státnici z didaktiky.

O čtenáři nepředpokládám víc, než že úspěšně dosáhl základního vzdělání. Všechny ostatní potřebné znalosti opět vysvětluji zde. Je pravděpodobné, že si čtenář mnohé z nich již osvojil v jiných předmětech, ale nemůžu na to spoléhat. Podle mých zkušeností je obtížné zkoordinovat výuku matematiky, fyziky, chemie, literatury a slohu, angličtiny, dějepisu, společenských věd a snad i jiných předmětů tak, aby na ně informatika mohla navazovat. Proto vysvětluji i témata, která s informatikou sice souvisí, ale obvykle se zařazují do jiných oborů. Snažím se tyto pomocné výklady typograficky odlišit od ostatního textu. Jednak proto, aby čtenář mohl snadno přeskakovat pasáže, které už zná odjinud, jednak aby si učitelé ostatních předmětů mohli snadno zjistit, co a kdy by měli vyučovat, aby informatika mohla navázat (případně co oni vyučovat nemusí, když se to studenti dozvědí v informatice dřív). Tímto způsobem bych rád poskytl trochu konkrétního materiálu k diskusím o přesazích, integraci a k porcování hodinových dotací. Pokud by snad opět někoho zajímal můj názor, jsem k výsledkům takových diskusí skeptický. Spíš si myslím, že zvlášť v dnešní, postindustriální, informační době je členění všeobecného vzdělání na vyučovací předměty překonané*), tak se nedivme, jak to dopadá, když členíme za každou cenu.

Ze zkušenosti odhaduju, že 90-98 procent studentů vyžaduje od gymnázia jediné: maturitní vysvědčení. A vzhledem k tomu, že se chtějí – na rozdíl od žáků průmyslovek – dostat na vysoké školy, snaží se dosáhnout co nejlepších známek s co nejmenším úsilím. Proto se naučí odříkávat „správné“ odpovědi na předem známé otázky. Nechtějí ničemu rozumět. Jenom asi 2-10% gymnazistů chce víc: vzdělání. Někteří z nich dokonce vzdělání všeobecné. A právě na tyhle lidi jsem myslel především.

Jde totiž právě o to, že právě studenti, kteří usilují o všeobecné vzdělání, nenajdou učebnici, která by jim vysvětlila základy informatiky tak, aby je mohli pochopit a aby o nich mohli samostatně přemýšlet. Rozcupovat, dohledat si protiargumenty, poslat autora do – řekněme: patřičných mezí – a postupně dospět k vlastnímu názoru. Nechápu, jak to, že taková učebnice neexistuje – vždyť právě informatika je jádrem všeobecného vzdělání.

Jistě, studenti mají přece internet, tam najdou všechno, co tady píšu. Opravdu: všechno, co jsem zde napsal, jsem našel ve Wikipedii. Jediný zádrhel je v tom, že encyklopedická data si člověk musí vyhledat, vybrat a správně uspořádat, aby dávala smysl. A právě tady je zakopaný pes: smysl toho, co hledáte, vám encyklopedie nevysvětlí, z encyklopedie těžko pochopíte souvislosti a smysl. Moje práce tedy spočívala v tom, že jsem vyhledal, uspořádal a vysvětlil. Ani v tom nejsem první – vezměme namátkou McLuhana, Wienera, Purkyně, Komenského, Epiktéta, Aristotela nebo Platóna. Každý z těchhle pánů už řekl o informatice všechno podstatné. Ale zkuste dneska získat Wienerovu Kybernetiku a společnost a přečíst ji – kdo ze středoškoláků tohle dokáže? Zkoušeli jsme to se studenty, tak vím, jak je to pro ně obtížné. Nerozumějí. Je jiná doba, jiné souvislosti, jiné problémy. Stará slova a staré věty ztratily během padesáti let své staré významy. Lidé už myslí jinak.

*) Pozn.: viz Mc Luhan, str. 152: „Ve školství je konvenční rozdělování látky na předměty již dnes stejně zastaralé, jako bylo po skončení renesance středověké trivium a quadrivium. Každý školní předmět, jdeme-li v něm do hloubky, se okamžitě začne vztahovat k jiným. Aritmetika na úrovni třetí nebo deváté třídy přestává být pouhým cvičením v řešení problémů, vyučuje-li se jí z hlediska teorie čísel, symbolické logiky a kulturních dějin. Pokud bude pokračovat dnešní fragmentarizace a nevztaženost školních osnov, vyrostou nám občané, kteří nebudou s to pochopit kybernetizovaný svět, v němž budou žít.“ – McLuhan, Herbert Marshall: Jak rozumět médiím. Odeon, nakladatelství krásné literatury a umění, Praha 1991, ISBN 80-207-0296-2

Informatika

Studenti se zdokonalí v ovládání operačního systému počítače na pokročilé úrovni. Naučí se systematicky používat základní kancelářské a komunikační programy. Při vyhledávání informací v prostředí internetu budou studenti schopni ověřovat a vyhodnocovat informace z různých informačních zdrojů. Studenti se naučí na uživatelské úrovni pracovat s bitmapovými a vektorovými editory. Při tvorbě dokumentů se budou řídit základními typografickými a estetickými pravidly. Naučí se vytvářet prezentace a základy publikování na WWW.

Studenti si prohloubí schopnost tvůrčím způsobem využívat informačních a komunikačních technologií, informačních zdrojů a aplikačního programového vybavení při respektování mravních zásad a právních norem. Zdokonalí se v systematickém uspořádávání svých vědomostí, rozvinou schopnost abstraktního systémového myšlení, vhodného vyjadřování myšlenek, smysluplné a účinné argumentace a tvůrčího přistupu k řešení problémů. Proniknou k podstatě a porozumí průběhu informačních procesů.

Výchovné a vzdělávací strategie

  • Samostatný sběr informací a orientace ve zdrojích informací rozvíjí kompetenci k učení a kompetenci komunikativní.

  • Samostatná práce na projektech rozvíjí kompetencí komunikativní a kompetenci k podnikavosti a na nižším gymnáziu také kompetenci pracovní.

  • Týmová spolupráce rozvíjí kompetenci sociální a personální.

  • Užívání výpočetní techniky a digitálních technologií rozvíjí kompetenci komunikativní, kompetenci pracovní, kompetenci k učení, kompetenci sociální a personální.

Povinný kurs informatiky je zařazen především do prvního ročníku vyššího gymnázia (kvinta). Zabýváme se těmito tématy:

Ergonomie a hygiena

  • řád laboratoře, plán práce

  • ergonomie a hygiena práce s výpočetní technikou

  • výpočetní technika pro osoby s handicapem

Bezpečnostní pravidla při používání počítače a internetu

  • aktualizace operačního systému

  • funkce firewallu

  • počítačové viry a červy, antivirový program

  • nebezpečné typy souborů v OS MS Windows

Informatika, informace, systémy

  • smysl a význam informatiky

  • co je informace

  • myšlenkové mapy

  • vztah informatiky ke všeobecnému vzdělání

  • disciplíny informatiky, kybernetika, přenos informací a řízení v systémech

Týmová práce, analýza a design systému

  • projekt a jeho řízení, plánování a dokumentace projektu

  • sbírání požadavků a jejich analýza

  • návrh řešení

  • implementace, testování a dokumentace

Studenti se rozdělí do týmů a navrhnou komunikační systém pro naši lokální síť, který by fungoval podobně jako Skype nebo ICQ. Týmy musí vypracovat zadání a navrhnout řešení (především nakreslí diagramy UML) a implemetovat databázovou část systému (především seznam kontaktů). Navazování a ukončování spojení a přenosy dat mezi počítači řeší studenti programování v septimě.

Používání relačních databází

  • základní pojmy a principy z oblasti relačních databází – struktura databáze

  • vkládání a editace dat, import a export dat

  • formuláře a sestavy, využití relací

  • vyhledávací dotazy, filtrování

  • databáze typu klient-server, SQL jazyk a transakční zpracování

  • oblasti použití relačních databází

Počítačové sítě a sítě GSM

  • sítě peer to peer a sítě klient–server

  • pojmy LAN a WAN

  • základní technické díly sítí

  • historie, principy a architektura internetu

  • princip fungování buňkové sítě mobilních telefonů

  • mapování složky, základní práva k síťovým diskům

Hra: simulace paketové sítě (snažíme se pronést rozstříhanou zprávu chodbami školy, kde číhají "chyby" a berou "signálům" pakety)

Aplikační programy, programovací jazyky, formáty datových souborů

  • druhy aplikačního software

    • webové prohlížeče a komunikační programy

    • kancelářské balíky

    • podnikové aplikace

    • vývojová prostředí a překladače programovacích jazyků

    • grafické a CAD programy

    • počítačové hry

    • výukové programy

    • pomocné programy (utility)

    • speciální programy pro různé profese

  • vazba typu dokumentu na program, programovací jazyky

Polyadické číselné soustavy

  • dvojková, osmičková a šestnáctková soustava

  • převody celých čísel mezi soustavami

Algoritmizace a základy programování

  • algoritmizace úlohy, vlastnosti algoritmu

  • jednoduché typy dat a jednoduché příkazy

  • složený příkaz, podmíněný příkaz, příkaz cyklu

  • přehled současných způsobů tvorby programů (objektové a vizuální programování)

Toto téma bych nejraději úplně vynechal a zájemce bych odkázal na volitelný předmět. V současné době se snažím uvedené učivo nahradit hrou založenou na Karlovi, při které studenti odvodí algoritmus myš v bludišti. Naučí se při tom základní příkazové struktury (cyklus ovšem nahradíme plnohodnotnou rekurzí), data vynecháme.

Webové stránky

  • struktura webu, pojmenovávání souborů na webu

  • prvky stránky v samostatných souborech (text HTML, obrázky, stylopisy aj.)

  • struktura dokumentu HTML: prvky, značky, atributy, entity

  • hypertextové odkazy, obrázky a jejich vlastnosti, tabulky

  • základy XHTML

  • stylopisy: styl, třída, vlastnost

Historie informatiky a výpočetní techniky

  • systémové pojetí světa

  • původ teorie systémů a teorie informace v matematice, logice a filosofii

  • vývoj informačních technologií, počátky automatizace

  • vznik teorie jazyků, automatů, systémů a informace, kybernetika

  • elektronické počítače a jejich technologické principy

  • druhy počítačů (superpočítač, mainframe, osobní počítač, PDA, smartphone)

  • význam informatiky a informačních technologií pro všeobecné vzdělání v současnosti

Samostatná práce: studenti vytvoří webovou stránku s rešerší na téma zvolené z historie informatiky a výpočetní techniky.

Multimédia

  • základní pojmy a principy z oblasti multimédií, multimediální formáty souborů

  • získávání a přehrávání multimediálních souborů

  • převody formátů multimediálních souborů

Samostatná práce: studenti se rozdělí do dvou- až tříčlenných týmů a natočí a sestříhají video na téma, které si zvolí z historie informatiky a výpočetní techniky. Tato úloha mívá u některých studentů úspěch, některá videa bývají vtipná a velmi pěkná.

Programování

Tříletý kurs programování zahrnuje tři obvyklá témata

Studenti se naučí navrhovat řešení zadaných úloh a tato řešení programovat v objektově orientovaném programovacím jazyce. Zvládnou jak programovací jazyk, tak i vývojové prostředí. Osvojí si základní postupy algoritmizace, objektového designu, seznámí se se standardními datovými strukturami a některými jednoduchými návrhovými vzory a porozumí základním standardním algoritmům. Rozvinou schopnost sytémového přístupu k problémům a dovednost samostatně navrhnout potřebné algoritmy řešení. Naučí se logicky strukturovat zdrojové texty programu, správně je graficky členit a dbát na srozumitelnost. Budou vytvářet grafická rozhraní aplikací přívětivá k uživatelům. Naučí se náležitě dokumentovat svoje projekty. Průběžně budou pracovat s příručkami a nápovědami v českém a anglickém jazyce, budou hledat nové informace na internetu, zejména v internetových encyklopediích, na fórech a v elektronických kurzech. Při kolektivním studiu a při týmové spolupráci si osvojí potřebné sociální dovednosti. Získají základní znalosti a elementární dovednosti potřebné pro práci ve vývojovém týmu na softwarových projektech.

Studenti si v tomto předmětu osvojí znalosti, dovednosti a postoje, které jim usnadní zejména další studium programování, matematické informatiky nebo softwarového inženýrství na vysokých školách.

Výchovné a vzdělávací strategie

  • analýza úloh, návrh řešení, algoritmizace rozvíjí kompetenci k řešení problémů

  • v pokročilejší fázi studia vyučující nahrazuje výklad samostatným studiem pomocí předem připravených anket a následnými konzultacemi; touto formou výuky a samostatnou prací s příručkami a nápovědou se rozvíjí kompetence k učení a kompetence komunikativní

  • samostatná práce na projektech rozvíjí kompetenci komunikativní a kompetenci k podnikavosti

  • týmová spolupráce rozvíjí kompetenci sociální a personální

Algoritmizace a programování

Přestože se učíme jazyk Pascal a programujeme v prostředí Delphi, vycházím z učebnice Pera B. Hansena Programming for Everyone in Java. Tuto úvodní část kurzu jsme spolu se studenty vyhodnotili průzkumem.

Literatura:

  • Per Brinch Hansen: Programming for Everyone in Java, Springer-Verlag, New York 1999

Dílčí témata kursu jsou:

Způsob práce a základní pojmy

  • Provozní řád laboratoře, hygiena, ergonomie

  • Plán práce

  • Mikroprocesor, paměť, instrukce, adresování

  • Reprezentace dat, číselné soustavy

  • Algoritmus, program

Jednoduché programy

  • První program

  • Vstup a výstup

  • Klíčová slova a jména

  • Proměnné a typy

  • Ordinální typy a intervaly

  • Víc o vstupech a výstupech

Projekt: robot, který běží za světlem

Příkaz jednoduchého výběru

  • Příkaz if

  • Porovnávání řetězců

  • Typ Boolean

  • Strukturované příkazy

  • Prázdný příkaz

  • Booleovský vstup a výstup

  • Kontrola induktivních podmínek, výjimky

Příkaz několikanásobného výběru

  • Příkaz case

  • Testování

  • Náhodný výběr, typ real

  • Styl

Příkazy cyklu

  • Cyklus for

  • Vnořené cykly

  • Postupné programování

  • Cyklus while

  • Ještě jednou postupné programování

  • Bloky a rozsahy platnosti

  • Cyklus repeat-until

Samostatná práce: výpočet funkce řadou

Textové soubory

  • Sekvenční soubory

  • Čtení ze souboru

  • Psaní do souboru

  • Kopírování souboru

  • Výběr dat

  • Konverze dat

  • Programování řízené syntaxí

Množiny a operace s nimi

  • Typ množina

  • Průnik, sjednocení, rozdíl a inkluze

  • Relace býti prvkem

Pole

  • Účel pole

  • Analýza textu

  • Typ real

  • Obdélníkové matice

  • Čtvercové matice

Rutiny

  • Kompozice programu

  • Jednoduché funkce

  • Jednoduché procedury

  • Způsoby, jak rozebírat text

  • Parametry typu pole

  • Pravidla rozsahu pro rutiny

  • Funkce vracející pole

  • Abstrakce

  • Výhody rutin

Rekurze

  • Rekurzivní metody

  • Vzájemná (nepřímá) rekurze

Pokročilé rysy Pascalu

  • Typ záznam a příkaz with

  • Variantní záznam

  • Typ soubor

  • Vstupní a výstupní proudy

Třídy

  • Pojem třídy

  • Grafické uživatelské rozhraní

  • Události, program řízený událostmi

  • Obslužné rutiny událostí

Projekt: snímání číslic z rotační číselnice telefonu

Pozn.: později se nám osvědčil Greenfoot od Michaela Köllinga.

Principy objektového designu a základy softwarového inženýrství

Tento kurs je slabým odvarem z kursu MIT a je doplněn několika tématy o objektovém modelování z mého staršího semináře o softwarovém inženýrství. Během kursu studenti navrhují architekturu části komunikačního systému podle zadání z povinné informatiky a programují tu část systému, která navazuje a rozvazuje spojení a přenáší data mezi počítači. Na komunikaci a na práci se zvukem mají připravené moduly, které použijí v systému.

Literatura:

Dílčí témata kursu jsou:

Proč záleží na dobrém designu

  • Projektování a týmová práce

  • Kvalita softwaru a význam designu

Objektově orientované programování

  • Proměnné, reference, objekty

  • Rovnost objektů

  • Třídy, členy, konstruktory

  • Dědičnost, kompatibilita tříd

Objektové modelování

  • Účel systému, způsoby užití, diagram způsobů užití

  • Scénáře chování, komunikační diagramy

  • Diagram tříd a objektový model systému

  • Třída, instance

  • Vazba, násobnost vazby

Specifikace metod

  • Specifikace metod, kontrakty

Ukázka: odvození programu metody ze specifikace

Testování

  • Úplný a neúplný test, strukturní test, důkaz správnosti

  • Pokrytí programu testem

  • Regresní testy

Dynamické datové struktury

  • Pohled pod pokličku: typ ukazatel, dynamické proměnné a ovládání volné paměti

  • Základní dynamické datové struktury: lineární spojové seznamy

  • Zásobník a fronta

Specifikace objektů

  • Abstraktní datový typ

Ukázka: specifikace zásobníku a fronty

Zeslabení spřaženosti

  • Dekompozice, vztahy závislosti, techniky zeslabování spřaženosti, rozhraní

  • Modulární programování

Výjimky

  • Defenzivní programování: testování invariantních podmínek za běhu, ošetření výjimek

Polymorfismus, podtřídy a podtypy

  • Procedurální typy, proměnné a parametry

  • Virtuální metody

  • Podtřídy a podtypy

  • Rozhraní a jeho implementace

Návrhové vzory

  • Vzory pro vytváření, chování a struktury

Strategie návrhu

  • Rozšiřitelnost, spolehlivost, účinnost

Algoritmy a datové struktury

Do úvodu připravovaného učebního textu k tomuto kursu jsem napsal:

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 kurzu, nic 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é 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. Pověstný silver bullet ovšem 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ž stovky 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 na nízkou kvalitu a produktivitu programátorské práce jsme si zvykli. 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 kurzu objektového designu, bychom teď – v kurzu 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.

Literatura:

  • Pavel Töpfer: Algoritmy a programovací techniky, PROMETHEUS, Praha 1995

  • Jakub Černý: Základní grafové algoritmy, Praha 2008, http://kam.mff.cuni.cz/~kuba/ka (navštíveno 1.2.2010)

  • Niklaus Wirth: Algorithms + Data Structures = Programs, Prentice-Hall, Englewood Cliffs 1975

  • MIT Open CourseWare, úvodní stránka (navštíveno 1.2.2010)

  • MIT Open CourseWare, Introduction to Algorithms přehled (navštíveno 1.2.2010)

  • MIT Open CourseWare, Introduction to Algorithms přednášky (navštíveno 1.2.2010)

  • UML (Unified Modeling Language), http://www.uml.org/ (navštíveno 1.2.2010)

  • Wikipedia, http://en.wikipedia.org/ (navštíveno 1.2.2010)

Dílčí témata kursu jsou:

Seznamy a jejich implementace

  • Seznam jako abstraktní datový typ

  • Zásobník a jeho implementace

  • Fronta a její implementace

  • Obecný seznam a jeho implementace

Řazení

  • Algoritmy řazení, jejich výpočtová složitost

  • Hledání K-tého nejmenšího prvku; medián

Stromy

  • Binární vyhledávací strom

  • Vyvážené binární stromy, přidávání a odebírání prvku

  • AVL-stromy

  • Halda

Rozptýlené tabulky

  • Rozptýlené tabulky

    • s vnějším zřetězením

    • s vnitřním zřetězením

  • Operace přidat, vyhledat, změnit, odstranit prvek

Prohledávání do hloubky a do šířky

  • Procházení stromem a grafem

  • Procházení stavovým prostorem

  • Ořezávání a heuristiky

Práce s grafy

  • Komponenty souvislosti grafu

  • Minimální kostra grafu

  • Topologické uspořádání

  • Hledání nejkratší cesty

Pokročilé techniky návrhu efektivních algoritmů

  • Odstranění opakovaných výpočtů

  • Přímé generování hledaných údajů

  • Předzpracování vstupních dat

  • Rozděl a panuj

To je konec stránky.