Tematika
1.9. Kombinatorika, 7. évfolyam: 10 óra
Tananyag: A hozott kombinatorikai ismeretek
rendszerezése: összeszámlálás, skatulyaelv, szöveges feladatok.
Fogalmak: Permutáció,
n!, a skatulyaelv (
a
geometriai skatulyaelv még nem, leszámolás fagráfokkal.
Tételek, összefüggések: Sokszög átlóinak száma,
n
egyenes hány részre osztja a síkot (konkrét
n-ekre),
(
n
2
), permutációk száma. Véges halmaz részhalmazainak
száma. A Pascal-háromszög legegyszerűbb tulajdonságai
(sorösszeg). A Fibonacci-sorozat legegyszerűbb tulajdonságai.
Eljárások, algoritmusok: Leszámolási feladatok megoldása
pl. fagráf segítségével; tudatos leszámlálási módszerek
kialakítása.
Pontosítás: Bonyolultabb skatulya-elves feladatok;
leszámlálási feladatok; egyszerű feladatok, ahol pl. a sakktábla
színezése segít; az állapotfüggvényt előkészítő egyszerű
feladatok: invarianciával (pl. négyes maradék megmaradásával)
bizonyítható feladatok; vegyes feladatok (pl. sakktáblán).
2.9. Kombinatorika, 8. évfolyam: 15 óra
Tananyag: A kombinatorikus gondolkodás fejlesztése.
Fogalmak: A teljes indukció előkészítése. Ismétléses
permutáció, kombináció.
(
n
k
) kapcsolata a
Pascal-háromszöggel. Geometriai skatulya.
Tételek, összefüggések: A Pascal-háromszög tulajdonságai
(folytatás); véges halmaz részhalmazainak, páros-, páratlan
elemszámú részhalmazainak száma (újabb bizonyítások). A logikai
szita 2, 3 halmazra. Egyszerű minimum és maximum kereső feladatok.
(
n
k
) kiszámítása. Kombináció. A Fibonacci-sorozat
tulajdonságainak kombinatorikus bizonyítása (
Ez mit
jelent?) Könyvtár-feladat: páronként nem diszjunkt
intervallumoknak van közös pontja.
Eljárások, algoritmusok: Egyszerű kombinatorikai játékok.
(
n
k
) felhasználása feladatokban. Egyszerű feladatok
teljes indukcióra. További feladatok a skatulya-elvre, geometriai
skatulyára. Bonyolultabb leszámlálási, színezési feladatok. Olyan
(pl. kombinatorikus geometriai) feladatok, amelyeknek megoldásánál
hivatkozni kell arra, hogy végtelen sok lehetőség közül egy véges
halmaz csak véges sok lehetőséget zár ki; vagy azt kell
kihasználni, hogy valami egyesével változik (mindkettőre példa:
mindig húzható olyan egyenes, amelynek két oldalán
n-n darab van
adott
2n pont közül).
φ(n) kiszámolása szita-formulával
konkrét,
n=p·q,
n=p·q·r, ,
n=
p2
,
n=
p2
·q alakú számokra. Az állapotfüggvényt előkészítő további
feladatok.
1.10. Gráfelmélet, 7. évfolyam: 10 óra
Tananyag: A gráfelmélet egyszerű alapfogalmai és a gráfok
felhasználása feladatmegoldásokban.
Fogalmak: Gráf, csúcs, él, pont fokszáma, fa konkrét
feladatokban. Komplementer gráf, összefüggőség.
Tételek, összefüggések: A fokszámok összege páros.
Eljárások, algoritmusok: Permutációk ábrázolása gráffal
(
Kell ez itt?); osztók fája (
Ez mi?), részhalmazok
ábrázolása bináris fákkal; leszámlálási feladatok megoldása
fákkal.
Pontosítás: Ismeretségre, rokonságra vonatkozó (tehát
gráffal szemléltethető) egyszerű feladatok. Egyszerű
Ramsey-típusú feladatok konkrét, kis számokra (pl. egy hattagú
társaság bármely három tagja közül van kettő, aki ismeri egymást,
akkor van a társaságban hármas ismeretség.
Inkább 8-9-ben
javasoljuk a Ramsey témakört).
Alkalmazások: Más tantárgyak fogalmi rendszerezéséhez is
használhatók a fagráfok. Konkrét alkalmazás: kémiában a
szénhidrogénekben a hidrogének számának paritása.
2.10. Gráfelmélet, 8. évfolyam: 10 óra
Tananyag: Euler-kör és út. Az alapfogalmak bővítése, új
fogalmak előkészítése.
Fogalmak: Euler-vonal (kör és út). Út, kör, összefüggő
gráf, fa és faváz fogalma konkrét feladatokon keresztül.
Irányított gráf [és tournament (körmérkőzés)] fogalma konkrét
feladatokon keresztül. Komplementer gráf. Páros gráf és páros
körüljárású gráf.
Tételek, összefüggések: Ramsey-típusú tételek egyszerű
esetekben (folytatás: pl. ha egy kilenctagú társaság bármely három
tagja közül van kettő, aki ismeri egymást, akkor van négyes
ismeretség.
Inkább 9. osztályban!). Példák, ahol a mohó
algoritmus működik. Euler-kör és út létezésének szükséges és
elégséges feltétele. Ha minden pont foka legalább
k, akkor van
k pontú út és kör
Inkább 9. osztályban!. Páros
körüljárású gráf színezhető két színnel. [Tournamentben van
pszeudógyőztes (példa tekintsük a legnagyobbat típusú
bizonyításra)
Inkább 9. osztályban!]. (
Ha a csúcsok
száma
v, akkor legalább
v-1 él kell ahhoz, hogy összefüggő
legyen a gráf.)
Eljárások, algoritmusok: Adott gráfokban megfelelő
tulajdonságú utat, kört, sétát (pl. Euler-utat, kört) keresni,
[favázat keresni
Inkább 9. osztályban!]; adott gráfról
eldönteni, hogy összefüggő-e.
Részletezés: A nyolcadikos tananyag nem általános
gráfelméleti tételekről, hanem konkrét gráfokra vonatkozó
ismeretekről szól.
1.11. Algoritmusok, 7. évfolyam: 5 óra
Tananyag: Ismerkedés az algoritmusokkal, elsősorban
konkrét matematikai játékokon és keresési feladatokon keresztül.
Fogalmak: A ,,biztosan nyerünk", ,,nyerő helyzet",
,,vesztő helyzet" fogalmának kialakítása konkrét játékokon
keresztül. Mit jelentés a ,,kérdés" a barkochbában. Játékok
szimmetriája konkrét egyszerű példákon. Egyszerű invarencia-elves
feladatok.
Tételek, összefüggések:
n-elemű halmazból gondolt elem
kiválasztása minimális kérdéssel.
Eljárások, algoritmusok: Egyszerű szimmetrián alapuló
játékok elemzése; mérések számának minimalizálásával kapcsolatos
feladatok. A lehetséges ,,kérdések" tisztázása.
Pontosítás: Pl. 1-től 40 grammig minden egész grammot
mérni akarunk egy kétkarú mérlegen. Milyen súlyokat válasszunk,
hogy a lehető legkevesebb számú súlyra legyen szükség?
2.11. Algoritmusok, 8. évfolyam: 5 óra
Tananyag: További játék-algoritmusok, kiválasztási és
rendezési algoritmusok.
Fogalmak: Kétszemélyes determinisztikus játékok
stratégiája, ,,nyerő" és ,,vesztő" helyek konkrét játékoknál. A
mohó algoritmus fogalma konkrét példákon (mikor jogos, mikor nem)
(
Korai!). Állapotfüggvény előkészítése konkrét példákon.
Tételek, összefüggések:
n-elemű rendezett halmaz
legnagyobb, legkisebb elemének kiválasztása
n-1
összehasonlítással.
n-elemű halmaz rendezése összefésüléssel,
beszúrással (
Inkább kilencidekbe!). Konkrét egyszerű
példák, amikor a mohó algoritmus nem működik.
Eljárások, algoritmusok: Hanoi tornyai:
palacsintaforgatás (rendezni úgy, hogy mindig egy adott szeletet
forgathatok); 3, 4 [, 5] elem rendezése minimális
összehasonlítással. Kétszemélyes játékok (nyerő vesztő
helyzeteinek) elemzése.
Részletezés: Számítástechnikából ismert algoritmusok
matematikai ,,vizsgálata".