A gráffogalom fejlődése

A gráffogalom fejlődése Erdősné Németh Ágnes ELTE Informatikai Kar, Doktori Iskola, Budapest Batthyány Lajos Gimnázium, Nagykanizsa

[email protected] a prezentáció kézirata elérhető: http://people.inf.elte.hu/szlavi/InfoDidact16/Manuscripts/ENA.pdf INFODIDACT, 2016, Zamárdi

Erdősné Németh Ágnes

Matematika és informatika kerettanterv  Alsó tagozat:  Matematika: rajzok  Versenyek: Kenguru Matematika Tesztverseny, Zrínyi Ilona Matematikaverseny

 Felső tagozat:  Matematika: modellezés, szemléltetés, rendszerezés – kimondás nélkül  Informatika: folyamatábrák értelmezése, kapcsolat más tárgyakkal  Versenyek: felkészítés, Varga Tamás Verseny – modellezés

 Középiskola:  Matematika: gráfos definíciók, emelt szinten néhány egyszerű tétel, használat modellezésre  Versenyek: matematikából és informatikából – kerettantervet erősen meghaladó szint

INFODIDACT, 2016, Zamárdi


E-hód  5-6. osztály - nehéz: megadott, irányítás nélküli gráfon megszámolás  7-8. osztály - közepes és nehéz: irányított gráfokon megszámolás, útkeresés, összegzés felső tagozaton a gráf ábrája a feladatleírás része, próbálgatás  középiskola - közepes és nehéz: gráffal kapcsolatos fogalmak szemléletesen bevezetve - izomorf, összefüggő, súlyozott, irányított gráf  a gráf ábráját esetenként a diáknak kell elkészíteni



CSUnplugged.org  Tourist Town:

meghatározó halmaz nem egyetlen jó megoldás

 Treasure Hunt:

véges állapotú automaták szimulációs feladatok

 The Poor Cartographer: modellezés  The Muddy City:

minimális feszítőfák Kruskal algoritmus

 Ice roads:

Steiner-féle fakeresés speciális minimális feszítőfa kereső eljárás



Alapismeretek – felső tagozat  Csúcs, él, irányítás, súlyozás  Csúcsmátrix, éllista, csúcslista – tömb használata tárolási és hatékonysági megfontolások

MESTER Haladó szint, Gráfok, elemi feladatok (Állatkert, Falvak, Ember, Rémhír…) 1. korcsoport, 2. korcsoport megyei forduló



Floyd-Warshall algoritmus  rekurzió és dinamikus programozás után  súlyozatlan gráfban: minden csúcspárról - létezik-e közöttük út  súlyozott gráfban: minden csúcspárról - köztük levő minimális út hossza  kódolása nagyon egyszerű: 3 egymásba ágyazott ciklus  variációk más-más megfogalmazással: maximin, minimax, legbiztonságosabb út, minimin, maximax MESTER Haladó szint, Gráfok, legrövidebb utak (Szállítás, Vám, Túra, Kastély) 2. korcsoport



Gráfok bejárása, feszítőfák

0

2

6

1

7

8

9

3

5

4

 Szélességi bejárás és szélességi feszítőfa – sor  Mélységi bejárás és mélységi feszítőfa – verem, rekurzió  Gráf modell használata nem gráfos feladatokban:robot, labirintus  Haladó adatszerkezetek  ciklikusan, egyre nehezedő szinten újra-és újra MESTER Haladó szint, Gráfok, szélességi bejárás ; mélységi bejárás; bejárások 2. korcsoport, OKTV



Dijkstra algoritmusa  mohó eljárások, hatékony rendezési eljárások  Dijkstra algoritmusa: két pont között a legrövidebb út meghatározására irányított, súlyozott gráfban  Halmaz, kupac, prioritási sor adatszerkezet után újra elővehető  Topologikus rendezéses feladatok MESTER Haladó szint, Gráfok, legrövidebb utak 2. korcsoport országos, OKTV



Haladó feszítőfák  hatékony sorba rendezések, prioritási sor, halmaz, union-find adatszerkezet  Prim algoritmus: mindig a következő minimális költségű élet húzza hozzá a már összefüggő komponenshez.  Kruskal algoritmus: az éleket hosszúság szerint növekvő sorrendben veszi sorra. Összefüggő komponensek keresése

MESTER Haladó szint, Gráfok, feszítőfák OKTV országos INFODIDACT, 2016, Zamárdi


További tervek  nemzetközi versenyekre készüléskor  a válogatóversenyeken  az informatikai olimpiákon használt algoritmusok  Feltérképezése és tanítási sorrendbe rendezése



Irodalom

 Programozási versenyfeladatok tára (1985-1994), (1995-1999), (2000-2004), NJSzT, Budapest

 NJSZT Nemes Tihamér Országos Informatikai Tanulmányi Verseny – Programozás kategória, archívuma http://nemes.inf.elte.hu/

 51/2012. (XII. 21.) számú EMMI rendelet 1., 2. és 3. melléklete Módosítva a 34/2014. (IV. 29.) EMMI rendelet 2., 3., 4. mellékletének megfelelően Matematika és Informatika kerettantervek http://kerettanterv.ofi.hu

 CSUnplugged_OS_2015_v3.1, http://csunplugged.org

 Bebras–International Contest on Informatics and Computer Fluency (2007-2015) http://bebras.org; http://www.beaver-comp.org.uk; http://informatik-biber.de; http://e-hod.elte.hu

 Zsakó, L.: Variations for spanning trees, Annales Mathematicae et Informaticae 33 (2006) pp. 151-165.

 Szlávi, P., Zsakó, L.: Informatika oktatása TÁMOP-4.1.2 A1 és A2 könyvei, ELTE IK, 2012 http://www.tankonyvtar.hu/hu/tartalom/tamop412A/2011-0052_34_informatika_oktatasa/adatok.html

 Mester feladatértékelő feladatai: https://mester.inf.elte.hu

 Horváth, Gy., Horváth, Gy., Zsakó, L.: Variations on a classic task XXIXth DIDMATTECH (2016) pp. 72-78. INFODIDACT, 2016, Zamárdi


A gráffogalom fejlődése Erdősné Németh Ágnes ELTE Informatikai Kar, Doktori Iskola, Budapest Batthyány Lajos Gimnázium, Nagykanizsa

[email protected] INFODIDACT, 2016, Zamárdi


A gráffogalom fejlődése

Recommend Documents