A beadandó feladatokkal kapcsolatos információk

A beadandó feladatokból mindenki annyit készít el, amennyit szeretne. A feladatokra kapható maximális pontszám a feladatok szövege mellett olvasható. A maximális pontszám akkor jár, ha a megoldás teljes és működőképes, illetve az is elvárás, hogy ha a megoldás nem teljesen nyilvánvaló, akkor egy rövid szöveges leírás legyen a fájlban a használt módszerről. A fájlokat mailben kell elküldeni, a kapott pontszám akkor válik véglegessé, ha a feladatot szóban "megvédi" a készítője (pár perces beszélgetésről van szó). Másolt megoldásra 0 pont jár.

A tárgyból megszerzett jegy teljes egészében a beadandó feladatok alapján kerül megállapításra. Beadandók határideje december 16. A követelmények a pontszám alapján a következők:
 
A 2-es követelménye: legalább 45 pontnyi beadandó elkészítése.
A 3-as követelménye: legalább 60 pontnyi beadandó elkészítése, kell lennie közte egy legalább 20 pontosra megoldott legalább 25 pontosnak.
A 4-es követelménye: legalább 75 pontnyi beadandó elkészítése, kell lennie közte két legalább 20 pontosra megoldott legalább 25 pontosnak.
Az 5-ös követelménye: legalább 90 pontnyi beadandó elkészítése, egy kivételével csupa legalább 25 pontosból.

Szívesen adok segítséget a feladatokhoz, ha van kérdés, emailben vagy személyesen pl. az órákon bátran tegyétek fel (de persze arra, hogy hogyan kell megoldani ezt meg ezt a példát, nem tudok/fogok válaszolni, ellenben azzal, ha pl. valaki olyan konkrét dolgot kérdez, hogy hogyan kell egy lista végére beszúrni egy elemet (bár ezt vettük órán), vagy ha elakadt valahol, és látom rajta, hogy dolgozott a feladattal, csak nem ismer valami trükköt, ami szükséges lenne stb.).

A feladatok listája (első verzió, október 18. - még bővül)

Lehet ajánlani saját feladatötletet is - ha érzésetek szerint eléri a kívánt nehézséget, írjátok meg bátran!


A maple/sage feladatok:

Animációk / rajzok

BUFFON (30 pont)

A Buffon-féle tűprobléma a következő: egy sík felületre, melyen egymástól egyenlő távolságra (d) párhuzamos vonalak találhatók, n darab l (< d) hossúságú tűt ejtünk. Nem nehéz belátni, hogy egy tűre annak valószínűsége, hogy az valamelyik vonalat érinti, bizonyos ésszerű feltételezések mellett 2l/dπ. Tehát várhatóan k = 2nl/dπ darab esik valamelyik vonalra. Ha a kísérletet sok-sok tűvel elvégezzük, π értékére kaphatunk becslést. Készítsünk ábrát, mely paraméterként adott n,d,l számokra véletlenszerűen leejtett n tűt ábrázol. A véletlen lehet pl. a következő: a tű közepének x és y koordinátája a -10d és 10d közötti intervallumból, a tű vízszintessel bezárt szöge a 0 és π közötti intervallumból van egyenletes eloszlás szerint választva. A vonalra eső tűket kék, a többit piros színnel rajzojuk ki. Számítsuk ki ebből (lásd wikipedia) π becsült értékét.

BOLYONGÁS (25 pont)
Rajzoljunk ki kétdimenziós véletlen bolyongást a képernyőre: hozzunk létre egy 1000 hosszú lépéssorozatot, melynek minden eleme 1/4-1/4 valószínűséggel az (1, 0), (-1, 0), (0, 1), (0, -1) vektorok valamelyike. Indítsunk el egy pontot az origóból, és mozgassuk 1000 lépésen át a generált lépéssorozatnak megfelelően. Rajzoljuk ki az útvonalát. Írjuk ki, hányszor járt az origóban, illetve hogy melyik pontban járt a legtöbbször (és hányszor). Állapítsuk meg, mikor járt a legtávolabb.

KONVERGENCIA (25 pont)
Kérjünk be a felhasználótól (readline vagy readstat segítségével) egy egyváltozós kifejezést x-ben. Írjuk ki a képernyőre, hogy van-e határértéke a végtelenben. Ha van határérték, készítsünk ábrát, melyben egy vízszintes vonal fut a határérték magasságában, illetve a függvény folytonos vonala, valamint az 1, 2, ..., 100 helyeken felvett diszkrét értékei látszanak, csupa különböző színnel.

Véletlennel való  kísérletezés

VÉLETLEN GYÖK (25 pont)
Legyen n rögzített pozitív egész. Készítsünk maple munkalapot, mely egy n-edfokú polinom együtthatóit egymástól függetlenül választja meg a {-1, 0, 1} halmazból. Rajzoljuk ki a komplex számsíkon a gyökeit.

VÉLETLEN GRÁF (25 pont)
Legyen p egy 0 és 1 közötti valós szám. Készítsünk el egy n csúcsú véletlen egyszerű irányítatlan gráfot, melyben bármelyik két csúcs között egymástól függetlenül p valószínűséggel fut él. Határozzuk meg a komponensek számát, a legnagyobb komponens méretét. Készítsük el a gráf adjacenciamátrixát, és keressük meg annak a legnagyobb abszolút értékű sajátértékét. Végezzük el a kísérletet 100-szor, és rajzoljuk ki hisztogramon a kapott értékek gyakoriságát (3 hisztogram).

KÖRVONAL (20 pont)
Válasszunk ki véletlenszerűen 3 pontot egy körvonalon. Határozzuk meg, hogy egy félköríven belül helyezkednek-e el. Ismételjük meg a kísérletet 100-szor. Végezzük el ugyanezt 3 helyett n ponttal.
+10 pontért: ugyanez gömbbel és félgömbbel.

Programozás

SZÁMREJTVÉNY (35 pont)
Hányféle lényegében különböző kifejezés képezhető az a,b,c,d szimbólumokból a négy alapművelet és zárójelek segítségével? (Pl. (a-b)-c és a-(b+c) megegyezik.)

FIBONACCI (20 pont) Legyen m egy 1-nél nagyobb egész. Könnyű matematikailag belátni, hogy ha a Fibonacci-számok sorozatát modulo m tekintjük, akkor a sorozat periodikus (előbb-utóbb újra szerepel benne 0 és 1, aztán ismétlődni kezdenek az értékek). Írjunk egy eljárást, melynek az egyetlen paramétere m, a kimeneti értéke pedig egy 2 hosszú lista: ennek első eleme a periódus hossza, második eleme pedig egy lista a periódus elemeiből. Például, ha az eljárás neve f, akkor az f(3) parancsra kapjuk azt válaszul, hogy [8, [0, 1, 1, 2, 0, 2, 2, 1]].

OSZTÓ (15 pont) Készítsük el a maple segítségével azt a 20 hosszú listát, melynek i-edik eleme egy kettő hosszúságú lista: [i, f(i)], ahol f(i) az a legkisebb természetes szám, melynek i darab pozitív osztója van. A keresett lista tehát valahogy így kezdődik: [[1, 1], [2, 2], [3, 4], [4,6],..]. (Mert pl. 6 a legkisebb pozitív egész, amelynek 4 osztója van.)

(+15 pontért:) Készítsük el ennek a listának a 100 hosszú változatát (elvárás: a számolás fusson le 5 percen belül egy átlagos mai PC-n (ha jól írjuk meg, úgyis másodpercek alatt lefut, ha nem, évek alatt sem)).

TÁBLA (30 pont) Valaki felír 8 nemnegatív egész számot egy táblára, majd a kezünkbe ad egy papírt, melyen szintén egy nemnegatív egész szám szerepel. Ezután a következő lépést tehetjük meg 7-szer: kiválasztunk a táblán aktuálisan szereplő számokból kettőt, letöröljük őket, és felírjuk a különbségük abszolút értékét a táblára. A cél az, hogy amikor csak egy szám szerepel a táblán, akkor az megegyezzen a papíron szereplővel. Kérdés, hogy ezt elérhetjük-e: írjunk ennek eldöntésére maple programot. A bemenet a táblára írt számok listájából és a célszámból áll, a kimenet pedig vagy az, hogy nincs megoldás (mondjuk legyen a visszatérési érték ilyenkor -1), vagy egy lehetséges lépéssorozat, amiket a letörölt számpárokkal adunk meg. Például, ha f az eljárás neve, akkor f([1, 2, 3, 4, 5, 6, 7, 8], 0) eredménye lehet mondjuk [[1, 2], [3, 4], [5, 6], [7, 8], [1, 1], [1, 1], [0, 0]], ha a cél pedig ugyanennél a táblánál 1 vagy 50, akkor nincs megoldás.

ARITMETIKAI (20 pont) Az aritmetikai deriváltat a következő szabályokkal definiáljuk a természetes számokra: p' = 1 minden p prímszámra, és ha a, b természetes számok, akkor (ab)' = a'b + ab'. Így például 15' = 3'·5 + 3·5' = 8, illetve kiszámolható pl. 60'=92. Írjunk eljrást, mely az ifactors függvény kimenete alapján kiszámítja egy bemeneti érték aritmetikai deriváltját.

EXPONENS (20 pont) Egy csoport exponensének azt a legkisebb pozitív egész n-t nevezzük (ha van ilyen), melyre igaz, hogy a csoport minden g elemére gⁿ=e, ahol e az egységelem. Írjunk eljárást, mely egy bemenetként kapott 1-nél nagyobb m egész modulusra kiszámítja a modulo m redukált maradékosztályok multiplikatív csoportjának exponensét. Listázzuk ki a 100-nál nem nagyobb m értékekre a kapott eredményeket, és hasolítsuk össze az Euler-féle φ függvénnyel.

VÉLETLEN (25 pont) Készítsünk véletelen 5x5-ös mátrixot, melynek az elemeit a [0,1] intervallumon egyenletes eloszlások szerint válasszuk ki függetlenül. Számítsuk ki a determinánsát és a legnagyobb abszolút értékű sajátérték abszolút értékét. Végezzünk 1000 ilyen kísérletet, és ábrázoljuk a determinánsra ill. sajátértékre kapott eredmények (tapasztalati) eloszlásfüggvényét.
(Egy F eloszlásfüggvény x helyen felvett értéke azt mondja meg, hogy mekkora valószínűséggel lesz a vizsgált mennyiség x-nél nem nagyobb. Tehát ha pl. egy konkrét x értéknél az 1000 kísérletből 349 esetben kisebb-egyenlő, 651 esetben nagyobb szám jött ki, akkor F(x) = 0,349.)

RELÁCIÓ (20 pont) Egy X halmazon értelmezett binér relációt formálisan X-beli rendezett párok halmazaként szoktunk definiálni. Írjunk eljárásokat, melyek egy ilyen formában adott relációról megmondják, hogy az reflexív, antiszimmetrikus ill. tranzitív-e (három külön eljárást). A bemenetük az X halmaz és a reláció. Tehát pl. isReflexive({1, 2, 3, 4}, {[1, 1], [2, 2], [3, 3], [4, 4]}) válasza legyen true,  isTransitive({1, 2, 3, 4}, {[1, 2], [2, 3], [1, 4], [2, 2]}) pedig false. (Itt nem elvárás a hatékonyság, tegyük fel, hogy legfeljebb 10 elemű X-re hívjuk meg.) (+10 pontért:) Írjunk programot, mely megszámolja, hogy egy 1, 2, 3, 4, illetve 5 elemű halmazon hány részbenrendezés adható meg (azaz olyan reláció, mely egyszerre reflexív, antiszimmetrikus és tranzitív).

NORMALITÁS (20 pont) Készítsünk eljárást, melynek egy bemenő paramétere van: egy n pozitív egész. A kimenet egy 10 hosszúságú lista legyen, melyben felsoroljuk, hogy a π tizedesvesszőt követő első n jegye közül hány darab 0, 1, 2, stb. számjegy van.

LEGNAGYOBB PRÍMOSZTÓ (20 pont) Készítsünk eljárást, mely három paramétert vár: a, b egészek, illetve n pozitív egész. A kimenet legyen egy lista, mely mindazokat az [a, b] intervallumbeli egészeket tartalmazza, melyek oszthatók a legnagyobb prímosztójuk n-edik hatványával.

3N+1 (20 pont) Készítsünk eljárásokat, melyek az ún. 3n+1 problámát viszgálják. Legyen f az a pozitív egész számokon értelmezett függvény, mely páros n-re n/2, páratlan n-re 3n+1 értéket vesz fel. Egy sejtés szerint ezt kellően sokszor ismételten alkalmazva, bármilyen kiindulási n-re lesz olyan, hogy 1-et kapunk (pl. 7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1). Írjunk egy olyan eljárást, mely meghatározza, hogy a paraméterként megadott n-re hány lépés múlva következik ez be (pl. 7-re 16 lépés kell). Egy másik eljárással pedig számoljuk meg, hogy mindeközben hány páros szám volt a sorozatban (a kiindulási értékkel együtt).

DINAMIKA (20 pont) Kérjünk be a felhasználótól egy k valós számot 1 és 4 között. Ezután tekintsük az f(x) = kx(1-x) függvényt. Válasszunk 1000 darab véletlen kiindulása értéket a [0, 1] intervallumból, mindegyikre hajtsuk végre ezerszer az f függvényt (tehát számoljuk ki az f(f(f(...f(f(x))...))) értéket), majd készítsünk egy 10 hosszúságú listát, amelyben felsoroljuk, hogy a kapott értékek közül hány esik az egységintervallum első, második stb. tizedik 1/10 hosszúságú részébe.

CSOKI (35 pont) Készítsünk programot, mely meghatározza, hogy egy adott állás a 6x6-os mérgezett csoki játékban nyerő-e.