kotprog.html

Kötelező programok

Fontos:

Mindenki egyeztessen velem előzetesen, hogy az általa kiválasztott programot csinálhatja-e! Az egyeztetés történhet az óra elején vagy végén személyesen.
A kötelező program célja annak igazolása, hogy az illető kellőképpen elsajátította a prolog programozás alapjait. A pontozásnál ennek megfelelően az kerül mérlegelésre, hogy a benyújtott program ezen kritériumnak mennyire felel meg.
A lenti listában nem szereplő, új ötletek is megvalósíthatók kötelező programként, amennyiben megfelelnek az előző pontban leírt kritériumoknak. Előzetes egyeztetés ebben az esetben is szükséges!
A témaötletek gondolatébresztő céllal lettek megadva, ezért a specifikációk szándékosan kidolgozatlanok. A pontos feladat megfogalmazása és a/egy megfelelő reprezentáció kitalálása szintén a feladat része.
Egy példát legfeljebb hárman választhatnak.
A projektmunka pontozásáról lásd a követelményeknél leírtakat.
A Hanoi tornyai, a nyolc királynő (n királynő) és a kannibál-misszionárius példák nem adhatók be kötelező programként.
Az eddigi választásokat tartalmazó lista.

Ajánlott témaötletek:

Átdarabolós játékok generálása és/vagy megoldása. (Néhány példa a játékra az ARCHIMEDES újság honlapjáról)
Ugyanez 3D-ben: a darabok, a doboz, a kezdeti elrendezés és a feladat.
Napóleon csillaga: a képen látható gráf csúcsaira kell 9 érmét elhelyezni 9 lépésben úgy hogy egy lépésben mindig kiválasztjuk a gráf valamelyik érme nélküli csúcsát, abból valamelyik fekete egyenes mentén elindulunk, és a harmadikként érintett csúcsra lerakunk egy érmét. Pl. első lépésben a-ból indulva g-re letehetünk egy érmét. (Egy teljes megoldás: a-g; i-a; c-i; f-c; e-f; h-e; b-h; j-b; d-j)
Feladat: Napóleon csillaga általánosítása, és annak megoldása(i). (Pl. gráfok valamely fix Euler vonala mentén haladhatunk, ...)
Adott K pozitív egész, és egy N-szer M-es táblázat kitöltve az 1, . . . , K számokkal. Feladat: fedjük le a táblázatot minél kevesebb téglalappal úgy, hogy egy-egy téglalap alatt csak egyféle érték legyen!
Adott X, K illetve S1, . . . , SK pozitív egészek esetén melyik az az X-nél nem kisebb legkisebb egész, amely előállítható S1, . . . , SK nemnegatív egész kombinációjaként? (Avagy másként: ha adott S1, . . . , SK címletű bankjegyek (mind pozitív egész) felhasználásával kell egy X (pozitív egész) értékű árut megvennünk, ám a boltban nem tudnak visszaadni, hogyan tudjuk ezt a legkisebb ráfizetéssel megtenni?)
Horn formula gráfjának előállítása [Hammer, Kogan: Essential and Redundant Rules in Horn Knowledge Bases]
Listában megadott számok közé aritmetikai műveletek és relációjelek behelyezésével igaz egyenlőségek/egyenlőtlenségek legenerálása.
Amőba: inputként adott állás és egy K konstans esetén tud-e X mindenképpen nyerni K lépésben, bármit csinál is O? [30 pontért: a játék 5*5-ös táblán folyik, a nyeréshez elég 4-et kirakni]
Matt K lépésben 2N*2N-es pályán: adott N, K (kicsi számok) és egy állás (kevés bábuval); tud-e fehér feketének mattot adni K lépésben, bármit is csinál fekete? (Elég, ha esetleg csak 3-4 bábutípust tud kezelni a program)
Ládapakolás: adott téglalap alakú ládába beleférnek-e az adott téglalalap alakú csomagok? (Csak egész értékek, nincs forgatás)
Tetris: látjuk az összes elemet előre (N db) és ismerjük a (fix) sorrendjüket is. Keressük meg az összes optimális stratégiát! (forgatás és mozgatás, eltűnő sorok, . . . ) [30 pontért: az összes megoldást, amivel nem megyünk 8 sor fölé]
Egy N hosszú, {1, 2, . . . , K} feletti sorozat összes olyan részsorozatának megkeresése, mely számtani sorozatot alkot, és amely maximális hosszúságú (azaz nincs másik olyan, ez előbbieknek eleget tevő sorozat, melynek ez részsorozata lenne). Pl: ha az input [1,3,2,3,2,2,1,4,5], akkor [1,2,3,4,5] kilistázandó, [1,3,5] viszont nem. [30 pontért: maximalitástól el lehet tekinteni]
Egy F1 és egy F2, inputként megadott, x1, x2, ..., xn változóhalmaz feletti logikai formula esetén kilistázni, hogy F1 mely részformulája F2 mely részformulájával ekvivalens (ekvivalensek = ugyanazt a függvényt határozzák meg ) [30 pontért: két formula különbözőségi halmazának megkeresése: mely értékadásokra adnak vissza különböző értéket]
Input: egy logikai formula. Feladat: megvizsgálni, hogy minimálisan hány változó értékét kell rögzíteni ahhoz, hogy a maradék formula érvényes (azaz tautológia) legyen, továbbá kiiratni az összes ilyen megoldást. [30 pontért: ]
Gráf összes maximális klikkjének kilistázása. Klikk: a gráf valamely teljes gráffal izomorf részgráfja. Maximális klikk: nem része a gráf más klikkjének. [30 pontért: maximalitástól el lehet tekinteni]
Maximális izomorf részgráfok: adott G illetve G' gráfok, keressük ezek azon H illetve H' (indukált) részgráfjait, melyek izomorfak egymással, és maximálisak az ilyenek közt a tartalmazásra nézve. [30 pontért: maximalitástól el lehet tekinteni]
Input: G gráf és K pozitív egész. Feladat: G összes, lényegileg különböző K-színezésének kiiratása, ahol két színezés lényegileg különböző, ha a csúcsoknak ugyanazon osztályozását határozzák meg. [30 pontért: a 'lényegileg különböző' feltételtől el lehet tekinteni]
Input: K darab D-dimenziós vektor. Output: az összes független részhalmaza, mely tartalmazásra nézve maximális. [30 pontért: ]
Bűvös négyzetek. Teljesen üres táblázat kitöltése, nem üres tábla kiegészítése. Kis négyzetkre lefuttatható legyen.
n×n-es négyzettáblák speciális fedései speciális dominókkal. Pl. szimmetrikus fedések n=4 esetén 2×1-es dominóval, . . .
Számokkal feltöltött táblák speciális bejárásai. Pl. bal alsó mezőből jussunk el a jobb felsőbe (bástyával, lóval, . . .) úgy, hogy az érintett mezőkön lévő számok összege minimális legyen.
Sudoku játék: az N×N-es tábla fel van osztva n darab, egyenként n mezőből álló diszjunkt régióra; a feladat megcímkézni a mezőket az 1, 2, ..., N számokkal úgy, hogy minden sorban, minden oszlopban és minden régióban minden egyes szám szerepeljen (egyszer).
Input: N, a tábla felbontása, valamint egy megkezdett címkézés.
Output: az összes olyan jó címkézés, ami a megkezdettet terjeszti ki.
[30 pontért: inputként csak N-et és a tábla felbontást kapjuk, és elég csak egy címkézést megtalálni]
Adott n és N=2n esetén egy X1, ..., XN sorozat N hosszú Skolem-sorozat, ha teljesül, hogy minden 1≤ i ≤ N esetén

az i pontosan kétszer fordul elő a sorozatban, és
a két előfordulási hely távolsága pontosan i.

Nem ajánlott témaötletek:

Fakezelés, fák bonyolultabb átalakítása. Pl. két döntési fa ekvivalenciájának eldöntése (a feladat hatékony megoldásához szükséges algoritmus kérhető).
DNF vagy döntési fa formájában megadott Boole-függvény prímimplikánsainak felsorolása.
Elemző program egyszerű programozási nyelvre(begin, end, egyszerű értékadások). Interpreter/compiler.
Kombinatorikus játékok. Pl.

Nimm,
amőba,
. . .

Polinomaritmetika: összeadás, kivonás, szorzás, maradékos osztás, stb
Deriválás: elemi függvények illetve összetett függvények deriváltjai. Esetleg többváltozós függvények parciális deriválásai.
MÁV-Elvira program. Kis adatbázis készítése, különböző kérdések megválaszolása: két hely között milyen útvonalak vannak, melyik a legolcsóbb legfeljebb két átszállással, . . .
Ítéletkalkulus megvalósítása (=, \=, /\, \/, \+ használata) , egyszerű normálformák, változók mely értékére igaz egy adott formula, adott formula Horn-formula-e, . . .
Automaták, nyelvtanok, Turing-gépek.

Reguláris kifejezés által generált nyelvnek eleme-e egy adott szó,
nyelvtanok különböző normálalakokra hozása (Chomsky-, Greibach-, . . . ),
adott nyelvtan környezetfüggetlen-e LL(1)-e, LL(2)-e, . . .
. . .

Gráfalgoritmusok:

minimális feszítőfa súlyozott gráfban,
színezések,
. . .

Mátrixaritmetika (összeadás, kivonás, szorzás, invertálás, determináns, . . . ).
Labirintus játék.
Kifejezések egyszerűsítése.
Természetes nyelvi adatbázisokra statisztikák készítése. Pl. fák mélységeinek maximuma, szögpontok átlaga, hány főnévi szerkezet, melyek az n szóból állók, . . . (adatbázis illetve plusz segítség kérhető)
Maximális folyam kiszámítása (Ford-Fulkerson algoritmus).
Numerikus módszerek.

Ajánlott témaötletek:

Nem ajánlott témaötletek:

Eddigi választások