Vysoké učení technické v Brně
Fakulta informačních technologií

Formální model procesu učení

Moderní teoretická informatika
Seminární práce

Autor: Tomáš Vojta
Školitel: Prof. Ing. Jan M. Honzík, CSc.

18. prosince 2002

Abstrakt
Tato práce se zabývá procesem učení s důrazem na skutečnost, že jde o proces - tedy děj, který lze popsat některým z mnoha formálních modelů. Zvolil jsem Petriho síť a na příkladu kursu Algoritmizace a datové struktury jsem proces učení popsal - nejprve hrubě pomocí černobílé sítě, následně přesněji sítí barvenou. Nalezl jsem rovněž obecně platné principy použitelné při modelování učení se jiné látce.

Klíčová slova
Petriho síť, učení, proces

Obsah
1.	Učení	3
1.1.	Stupeň zvládnutí látky	3
1.2.	Pojem	3
2.	ADS	4
2.1.	Graf struktury pojmů kursu ADS	4
2.2.	Hierarchie pojmů	6
3.	Petriho síť	7
3.1.	Jednoduchá černobílá síť	7
3.2.	Jednoduchá barvená síť	8
4.	Závěr	11
4.1.	Vyhlídky do budoucna	11
5.	Literatura	12

Prohlašuji, že jsem tuto práci vypracoval samostatně a v seznamu jsem uvedl veškerou použitou literaturu

V Brně, 18. prosince 2002	…………………
	L.S.
1.	Učení
Než vytvoříme slíbenou Petriho síť modelující studium kursu ADS, definujme nejdřív potřebné pojmy.
1.1.	Stupeň zvládnutí látky
Jedním ze základních problémů, před kterým stojíme, je otázka, co přesně myslíme učením. Stačí nám, když student pozná v předloženém zdrojovém textu řadící algoritmus QuickSort? Nebo budeme vyžadovat, aby dokázal vybrat optimální algoritmus pro řešení zadané úlohy?
Každý z těchto úkolů vyžaduje jinou úroveň zvládnutí předložené látky
Znalost
Znalostí myslíme prostou schopnost studenta si fakt vybavit z paměti. Typickým příkladem získávání znalostí je memorování textu bez jeho dalšího chápání – užitečný příklad je naučená báseň, při studiu ADS budeme vždy požadovat vyšší úroveň zvládnutí.
Pochopení
Pokud student látku chápe, je schopen vlastními slovy interpretovat její význam – „abstraktní datová struktura zásobník je struktura podobná zásobníku střelné zbraně – poslední vložená položka opouští zásobník jako první“.
Aplikace
Schopnost aplikovat získané fakty je cílem výuky ADS. Výsledek je možno ověřit zadáním úkolu (např.): „Napište program, který seřadí záznamy studentů podle ročníků a v rámci ročníků podle studijního průměru metodou QuickSort“.
Vyšší stupně
Vyšší stupně zvládnutí látky – Analýza, Syntéza a Hodnocení – nechme prozatím stranou. Pro účely této práce předpokládejme, že schopnost aplikovat získané dovednosti je právě tím cílem, kterého chceme dosáhnout.
1.2.	Pojem
Definovali jsme jak se učit, zbývá definovat co se učit. Základním termínem bude slovo pojem. Pojem je to, čemu se učíme. „Zásobník“ nebo přesněji „abstraktní datová struktura zásobník“ je pojem. „QuickSort“ je pojem. „Strom“ je rovněž pojem, a k jeho zvládnutí je nutno zvládnout (znát, pochopit, dokázat aplikovat, …) pojmy jako „kořen“, „vztah otec-syn“, „in-order průchod“ apod..
Termínem elementární pojem nazveme takový pojem, který z hlediska výkladu už nemůžeme dále rozdělit. (např. „operace inicializace fronty“ či „rekurzivní definice kořenového stromu“)
Vztahy mezi pojmy
Řekneme, že pojem je předchůdce jiného pojmu, pokud je jeho zvládnutí nezbytné pro zvládnutí pojmu následujícího. Přímý předchůdce je ze všech předchůdců ten nejbližší.
Výchozí pojem je takový, který nemá žádného předchůdce. Formálně jsou tyto termíny definovány v kapitole 2.2.
2.	ADS
Kurs ADS (Algoritmizace a datové struktury) je vyučován na FIT VUT v Brně. Jde o předmět druhého ročníku studia, seznamující studenty s pokročilejšími tématy programování, jako je dynamické programování, vyhledávání a řazení. 
Shrňme teď pojmy, které je nutné (ve větší či menší míře) zvládnout, k absolvování kursu ADS.
2.1.	Graf struktury pojmů kursu ADS
Strukturu pojmů kursu ADS znázorníme orientovaným grafem. Uzly grafu tvoří pojmy, hrany reprezentují vztah mezi přímým předchůdcem a jeho (přímým) následníkem. Hrany jsou orientovány od předchůdce k následníkovi..
Struktura kapitol

Algoritmy

Abstraktní datová struktura

Vyhledávání

Řazení

Dokazování algoritmů

Obrázek 2.1 – Graf struktury kapitol kursu ADS
Strukturu pojmů můžeme modelovat na různé úrovni. Je jistě možné sestrojit graf obsahující všechny elementární pojmy, ovšem silně na úkor přehlednosti a bez významnějšího zlepšení modelovací schopnosti.
Proto budeme s kapitolami pracovat jako s dále nedělenými bloky. Počátek studia další kapitoly je možný až po dokončení kapitoly předchozí.
Grafy vybraných kapitol
Na rozdíl od grafu na obrázku 2.1 bude postup od předcházejících pojmů k pojmům následujícím zobrazen ve směru dolů, namísto směru doprava. Jde pouze o kosmetickou úpravu.
Strukturu celého kursu je možné najít v [2].
Kapitola Datová struktura

Abstraktní datová struktura

Abstraktní datová operace

Seznam

Zásobník

Fronta

Vyhledávací tabulka

Binární strom

PreOrder průchod stromem

InOrder průchod stromem

PostOrder průchod stromem

Kořenový strom

Oboustranně ukončená fronta

Obrázek 2.2 – Struktura kapitoly Datová struktura
Kapitola Vyhledávání

Sekvenční vyhledávání v neseřazené posloupnosti

Sekvenční vyhledávání v seřazené posloupnosti

Vyhledávání podřetězce v řetězci

Binární vyhledávání

Fibonacciho vyhledávání

Vyhledávání  v BVS

Vyhledávání ve vyhledávací tabulce

Binární vyhledávací strom (BVS)

Obrázek 2.3 – Struktura kapitoly Vyhledávání
Relace na množině pojmů
Základní relací nad množinou pojmů je relace částečného uspořádání (budeme zapisovat tradičně a < b). Připomeňme, že relace částečného uspořádání je ireflexivní a tranzitivní relace na nosné množině, v našem případě množině pojmů (elementárních i složených).
Význam relace částečného uspořádání je zřejmý – platí-li a < b, pak zvládnutí pojmu a je nutné pro zvládnutí pojmu b. V této práci bude relaci a < b odpovídat hrana grafu orientovaná z a do b. V našem konkrétním příkladě vidíme, že zvládnutí pojmu řazení je možné až po zvládnutí pojmu vyhledávání.
Definujme relaci přímého předchůdce – a je přímý předchůdce b když a jen když: a < b a současně neexistuje žádné c takové, že (a < c) ^ (c < b). (Pro a, b, c z množiny pojmů).
Obdobně b je přímý následník a právě když platí a < b a současně neexistuje žádné c takové, že (a < c ^ c < b).
Jestliže a < b, říkáme, že a je předchůdce b a b následník a.
2.2.	Hierarchie pojmů
Ukázali jsme, že pojmy můžeme skládat (pojem datová struktura se skládá z mnoha dalších pojmů, jako je např. seznam) nebo naopak inverzním postupem dělit. Na nejvyšší úrovni můžeme ADS považovat za jeden pojem, na nejnižší budou elementární pojmy jako binární vyhledávací strom, hledání v poli se zarážkou, apod..
Nazvěme E množinu všech elementárních pojmů kursu ADS. Je zřejmé, že E je konečná.
Nadřazený pojem
Smyslem definice tohoto termínu je usnadnit vytváření učebních bloků – kapitol. Z praxe víme, že kapitola není nahodilý souhrn pojmů, ale takový jejich soubor, který spolu vnitřně souvisí. Tuto souvislost formalizujme následující definicí.
Za nadřazený pojem elementárnímu pojmu a prohlásíme pojem B právě když:
a je elementární pojem, B  E, |B| > 1, přičemž a  B a současně pro libovolná x,y  B neexistuje z  E, z  B takové, že (x < z) ^ (z < y).
Neformální vysvětlení definice je takové – pojem (např. kapitola vyhledávání) shrnuje takové elementární pojmy, které jsou buď neporovnatelné (Binární vyhledávací strom a sekvenční vyhledávání v neseřazené posloupnosti) nebo porovnatelné jak v rámci pojmu, tak v rámci všech pojmů kursu (tj. je-li předchůdce pojmu v množině B, pak je v B i přímý předchůdce tohoto pojmu)
Pojem
Bystrý čtenář si jistě všimnul, že tento termín jsme dosud nedefinovali. Definujme jej nyní, a to takto:
Pojem je taková podmnožina B množiny E, pro kterou platí:
B je nadřazený pojem alespoň jednomu elementárnímu pojmu z E.
Čtenář si jistě také všiml, že pojem je vždy složen z více elementárních pojmů. Rovněž jsme nedefinovali hierarchii neelementárních pojmů – není pro to důvod. Hierarchii neelementárních pojmů můžeme zkoumat pomocí množinových vlastností (je vlastní podmnožinou?). Pro neelementární pojmy obsahující jeden pojem elementární rovněž v praxi není důvod – v kombinaci s hierarchií pojmů bychom mohli dostat pojem, který obsahuje pojem, který obsahuje …, který obsahuje elementární pojem.
Výchozí je takový pojem, který nemá na E předchůdce, tj. a je výchozí pojem právě když neexistuje bE takové, že b < a.
3.	Petriho síť
V této kapitole budeme konstruovat Petriho sítě modelující proces učení. I když vycházíme z kursu ADS, základní jednotkou bude učení se pojmu – naše úvahy je tedy možno zobecnit na libovolný kurs, ve kterém se učíme pojmům.
Zaměřme se na dva případy – zaprvé na jeden osamocený pojem, zadruhé na dvojici pojmů, mezi kterými existuje přímá návaznost. Ukažme, že tímto způsobem dokážeme modelovat libovolně složitou strukturu pojmů.
3.1.	Jednoduchá černobílá síť
Následující schéma znázorňuje síť modelující elementární pojem
 
Vstupní test – neúspěch

Učení

Výstupní test – neúspěch

Neprošel vstupním testem

Prošel vstupním testem

Vstup / Neprošel výst. testem

Prošel výst. testem/ Výstup

Byl učen

Vstupní test – úspěch

Výstupní test – úspěch

Obrázek 3.1 – Petriho síť modelující učení jednoduchému pojmu
Místa jsou popsána kurzívou, přechody obyčejným řezem písma.
Fáze procesu učení elementárnímu pojmu
Do procesu učení elementárnímu pojmu zahrnuli nejen ověření nabytých znalostí, ale i vstupní ověření. Důvod je zřejmý – abychom mohli studenta pojmu naučit, musíme jej nejen úspěšně učit (a tento úspěch ověřit výstupním testem), ale musíme rovněž předem ověřit předpoklady studenta ke zvládnutí tohoto pojmu. Vstupní test zajišťuje, že je student na dostatečné úrovni, aby pojem zvládl.
Z existence částečného uspořádání na množině elementárních pojmů a z definice pojmu plyne, že jsme schopni u každého pojmu určit výchozí předpoklady a podle nich sestavit vstupní test (prerekvizitami pojmu b jsou všechny elementární pojmy a takové, že platí a je přímým předchůdcem některého elementárního pojmu z b).
Učení a výstupní test pak plně záleží na pojmu samotném.
Kompozice pojmů
Tuto jednoduchou síť jsme záměrně navrhli tak, aby bylo možné ji nahradit sítí podstatně jednodušší – totiž jediným místem. Pokud by síť na obrázku 3.1 popisovala vyhledávání v neseřazené posloupnosti, jiný vyhledávání podřetězců v řetězci a ještě jiný pak binární vyhledávací strom, pak jejich kompozicí bude síť na obrázku 3.2.

vyhledávání v neseřazené posloupnosti

vyhledávání podřetězců v řetězci

Binární vyhledávací strom

Shrnutí / Opakování / Motivace

Návrat k procvičení

Obrázek 3.2 – Kompozice elementárních pojmů
Uveďme na tomto místě, jaké bude počáteční značení sítě, kterou vytvoříme jako kompozici všech elementárních pojmů. Značky budou ve vstupních místech těch výchozích pojmů.
Je zřejmé, že u výchozího pojmu není možné ověřovat vstupní požadavky – pojem je výchozí, nemá žádné předchůdce. Tedy i možnost neprojít vstupním testem nemá smysl – síť modelující výchozí pojem bude vypadat takto:

Učení

Výstupní test – neúspěch

Vstup / Neprošel výst. testem

Prošel výst. testem/ Výstup

Byl učen

Výstupní test – úspěch

Obrázek 3.3 – Síť modelující výchozí pojem s počátečním značením

Vraťme se ale zpět ke kompozici sítí. Obrázek 3.2 můžeme opět nahradit jediným místem a tak bychom mohli pokračovat až po následující síť:

ADS

Obrázek 3.4 – Síť modelující pojem ADS
Na této úrovni už bychom mohli modelovat výuku více kursů – od jednoho semestru až po celý studijní program.
Problémy černobílé sítě
To je ovšem pouze teoretická možnost, které stojí v cestě praktická překážka. Tou překážkou je jednak jednoduchost modelu, jednak individuální rozdíly mezi studenty. Jednoduchost modelu naráží na tento problém:
Student právě absolvoval fázi učení a jeho znalosti je nyní nutno ověřit testem. Test může být důkladný nebo mírný. Důkladný test opakovaný na závěr každého elementárního pojmu bude po čase studenty odrazovat, naopak mírným testem mohou projít i studenti, kteří látku dostatečně nezvládli a proto budou mít s následujícími problémy.
Pokud by se nám podařilo testy vyladit tak, aby v průměru byly akorát, narazíme na individuální rozdíly mezi studenty – testy budou pro jednoho zbytečně důkladné, jiný dosáhne výsledku, který neodpovídá jeho znalostem.
To nás vede k zavedení složitějšího modelu, kterým bude
3.2.	Barvená síť
Barvená síť nám oproti síti černobílé umožní navíc:
a)	Zjednodušit či úplně vynechat vstupní testování
b)	Zjednodušit výstupní testování

Na následujícím obrázku je barvená Petriho síť modelující elementární pojem:

Ověř_vstupní_požadavky
Proveď učení

Ověř_nabyté_znalosti

Byl učen

Neprošel vstupním testem

Prošel výstupním testem

Vstup

Not(Ověř_vstupní_požadavky)

Not(Ověř_nabyté_znalosti)

Vstupní test – neúspěch

Výstupní test – neúspěch

Výstupní test – úspěch

Vstupní test – úspěch, učení

Obrázek 3.5 – Barvená Petriho síť, první přiblížení
Model elementární pojmu jsme při použití barvené sítě zjednodušili o jedno místo a jeden přechod. Musíme však ještě doplnit hranové výrazy a poněkud formálněji zapsat stráž a akce přechodů. (Barvená síť je použita dle definice HL Petriho sítě v [4], str. 19-24)
Počáteční značení
Podobně jako u sítě černobílé bude počáteční značení pouze ve výchozích pojmech. Rovněž síť modelující výchozí pojem se bude od ostatních odlišovat:

(e,0)

y = nauč(x,p)

(p=Ověř_nabyté_znalosti(y)) > 50

Byl učen

Prošel výstupním testem

Vstup

(x, p)

y

y

(y, p)

(y, p)

(p=Ověř_nabyté_znalosti(y)) <= 50

y

Učení

Výstupní test – neúspěch

Výstupní test – úspěch

Obrázek 3.6 – Model výchozího pojmu
Průběh učení (funkce nauč()) záleží na studentu a dosavadním zvládnutí látky. Učený student pak buď splní kritéria výstupního testu (u výchozího pojmu nemáme jinou možnost než test) nebo pokračuje „zpět na start.
Následující síť znázorňuje libovolný nevýchozí pojem:

VstupniTest(x)
y = nauč(x,p)

(p=Ověř_nabyté_znalosti(y)) > 50

Byl učen

Prošel výstupním testem

Vstup

x

x,y

x,y

(y, p)

x,(y, p)

(p=Ověř_nabyté_znalosti(y)) <= 50

Not(VstupníTest(x))
y = nauč(x,p)

x

Neprošel vstupním testem

x,y

Vstupní test – neúspěch

Výstupní test – neúspěch

Vstupní test – úspěch, učení

Výstupní test – úspěch

Obrázek 3.7 – Petriho síť modelující libovolný pojem
Výchozí značení nevýchozího pojmu je prázdné – nepředpokládáme žádné znalosti na této úrovni.
Chování modelu pojmu
Výstupem výchozího pojmu byla dvojice (y,p), kde y je identifikátor daného pojmu a p je hodnota určující stupeň zvládnutí látky (celé číslo z rozsahu <0;100>). Každý další pojem k této dvojici přidává další dvojici – opět identifikátor pojmu a stupeň zvládnutí. Každý z pojmů má tedy možnost zjistit úspěšnost studenta v předchozích krocích studia a podle toho buď postupovat pomalu a důkladně nebo naopak zrychlit potenciálně zřejmé věci. Tento princip je možno použít jak u výuky, tak u testů – v případě výborných dosavadních výsledků vstupní test zkrátit na minimum či zrušit, v případě výsledků horších věnovat ověření dosavadní úrovně vyšší pozornost.
Funkce VstupniTest(x) ve stráži přechodů Vstupní test – úspěch , učení a Vstupní test – neúspěch tedy studenta nemusí vůbec testovat – pouze zkontroluje dosavadní výsledky.
Naopak funkce nauč() může v průběhu učení klást otázky ke zjištění, zda je látka dostatečně chápána.
Konečně tvar stráže přechodů Výstupní test – úspěch a Výstupní test – neúspěch není zcela přesný– lépe by bylo použít booleovskou funkci, která jako vedlejší efekt nastaví parametr p. Pevně zvolená úspěšnost 50% nám totiž v praxi stačit nebude. Pro přehlednost jsem však zvolil méně přesný tvar.
Stupeň zvládnutí
V úvodu jsme řekli, že pro účely ADS budeme usilovat o naučení schopnosti aplikovat probranou látku. Tuto úroveň předpokládáme u všech pojmů.
Pokud bychom chtěli rozlišit různé úrovně zvládnutí u jednotlivých pojmů, museli bychom pracovat s různými verzemi funkce nauč().
Mohli bychom rovněž chtít sledovat nabytou úroveň znalostí (nezávisle na požadavcích k úspěšnému složení výstupního testu). V tom případě bychom museli rozšířit výstup funkce výstupního testu a hranové výrazy u přechodů Výstupní test na trojice (x,p,u), kde u bude značit nabytou (a testem prokázanou) úroveň.
4.	Závěr
Ukázali jsme, jak lze zavést formální aparát (algebru a Petriho sítě) do procesu učení, tím, že jsme nejprve definovali jsme potřebné termíny, využili vlastností relace částečného uspořádání a ukázali, že pomocí kompozice elementárních sítí jsme schopni modelovat kurs založený na nosné množině pojmů.
V procesu modelování procesu učení jsme použili nejprve černobílou a následně barvenou Petriho síť, která nám umožnila provádět pouze nezbytné ověřování zvládnutí látky s přihlédnutím k individuálním výsledkům studenta.
Ukázali jsme, že jsme schopni modelovat učení libovolnému předmětu, který je založen na učení se pojmům. Modifikace pro učení zahrnující manuální dovednosti se jeví velice jednoduché – jedná se o změnu definice naučení se (funkce nauč()) a ověřování nabytých dovedností (vstupní a výstupní test).
4.1.	Náměty pro pokračování
Nadějně vidím hledání cest další individualizace učení – hledání optimálního následujícího kroku či přizpůsobování tempa učení studentovi. Rovněž je možné statisticky zkoumat výsledky všech studentů a na základě těchto údajů odhalit obtížná či naopak snadná místa a věnovat jim patřičnou pozornost.

5.	Literatura
[1]	Hunterová, M.: Účinné vyučování v kostce, Portál s.r.o, Praha, 1999, ISBN 80-7178-220-3
[2]	Vojta, T.: ADS – struktura předmětu, UIFS FIT VUT, Brno, 2002, nepublikováno
[3]	Češka, M.: Teoretická informatika 2, UIVT FEI VUT, Brno, 1999, fotokopie přednášek
[4]	Janoušek, V.: Modelování objektů Petriho sítěmi, FEI VUT, Brno, 1998, disertační práce