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:
Algoritmy + datové struktury = objekty (podrobnosti o projektu viz zde; vyšla 2017, nyní je již rozprodána)
Učebnice informatiky pro gymnázia (podrobnosti o projektu viz zde; zůstala nedokončená a s přechodem do důchodu a do vzdělávacího dissentu se ji chystám přepracovat spíš do populárně naučné podoby)
Na gymnáziu jsem v letech 2006 až 2010 vyučoval
povinnou informatiku
volitelné programování
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:
MIT Open CourseWare, úvodní stránka (navštíveno 1.2.2010)
MIT Open Courseware, Laboratory in Software Engineering přehled (navštíveno 1.2.2010)
MIT Open Courseware, Laboratory in Software Engineering 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:
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.