Az esszé kérdés Az esszé kérdés egy nagyobb kérdésről az előadásokon elhangzott ismeretek teljes leírását kéri. Az ``esszé'' megírásához néhány szempontot sorolok fel segítségül.

• A kérdés a benne leírt témáról az összes előadáson elhangzott anyag (ahol volt ott bizonyításokkal) tár\-gya\-lá\-sát jelenti.
• A leírás minőségét nagyban javítja, ha valaki tényleg veszi a fáradságot és mélyen végiggondolja a kérdéses anyagot. Ebben nagy segítség lehet, ha a fogalmak és állítások megértése után a hallgató megpróbálja saját maga belátni az egyszerűbb állításokat, lemmákat. Ha feltesz kérdéseket, amelyeket megpróbál önmaga megválaszolni. Az önálló gondolatok jelenjenek meg a dolgozatban is. A plusz munka nem veszik kárba. Ha a leírt anyag tükrözi a hallgató ebbe fektetett nagy energiáját az kihatással van a szóbeli részre is.
• A gráfelmélet alapelőadást meghaladó fogalmakat, tételeket pontosan fogalmazzuk meg.
• A fogalmazásra, stílusra fordítsunk nagy figyelmet. Világosan, érthetően, logikusan építsük fel mondanivalónkat.
• Az előadáson elsőre nehezen érthető anyagot próbáljuk úgy ``tálalni '', hogy másoknak már kevesebb problémájuk legyen a gondolat megértésével. A középiskolások számára érthető dolgok úgy legyenek megfogalmazva, hogy dolgozatunkból egy középis\-ko\-lás is értse meg azokat. Az egyszerű gondolatok az olvasó számára is egyszerűnek, a természetesek természetesnek tűnjenek.
• A beadott munka struktúrált legyen. Amit fontosnak tartunk azt emeljük ki. Amit a gondolatmenet fő irányához képest kitérőnek érzünk azt írjuk kisebb betűvel.
• Motivációra és a nehezebb fogalmak, ötletek fokozatos bevezetésére törekedjünk. Példák szerepeljenek, ha azok segítséget nyújtanak.
• Nem a dolgozt hossza számít, hanem minősége. Technikai részletekben ne vesszünk el. A fontos gondolatok, az áttekintés viszont mindig legyenek az előtérben. A cél nem az előadás írásbeli megismétlése, hanem arról való tanúságtétel, hogy megértettük az anyagot.
• Próbáljunk javítani az előadásban elhangzottak minőségén. Például az előadásokon elhangzott jelölések nem biztos hogy szerencsések voltak. Próbáljunk olyan jelölést használni ami számunkra a legkifejezőbb. Egyes bizonyítási részek sorrendje lényegtelen, de ha a hallgató úgy ítéli meg, hogy --- az előadáshoz képest --- felcserélésük könnyebbé, érthetőbbé teszi az olvasó (hallgató) feladatát, akkor tegyen úgy. Az előadás hibáit ne ismételjük meg. A pongyolán fogalmazott, könnyen félrérthető fogalmak, állítások kimondását úgy végezzük el, ahogy azt a leghelyesebbnek gondoljuk. Ha az előadásban hibát vagy hiányt fedezünk fel, akkor azt próbáljuk kijavítani. A fontos, de ``elhadart'' részeket bontsuk ki. Saját magunk által felvetett gondolatokat is érdemes leírni. Minden érdemi plusz az előadáshoz képest jelentős előnyt jelent.

* Egy esszé kérdés a következők közül kerül ki.

• Kiszámíthatóság, Turing-gép alapdefiníciója és változatai; Megállási probléma és kiszámíthatatlansága
• Post-féle ``dominó''-probléma megoldhatatlansága
• Kombinatorikus csoportelmélet: szabadon generált csoportok, Nielsen-elmélet
• Kombinatorikus csoportelmélet: végesen prezentált csoportok, HNN-bővítés
• A szóprobléma megoldhatatlansága: Novikov-tétel
• Időbonyolultsági osztályok; P és EXP szeparációja; Tárbonyolultsági osztályok
• Nemdeterminisztikus bonyolultsági osztályok; Bonyolutsági osztályok viszonyai
• Savitch-tétel; 0-tárú Turing-gépek és véges automaták
• Parkettázási probléma; Valós-számok kódolása; Wang-parkettakészlet, amivel létezik nem periodikus parkettázása a síknek, de periodikus viszont nem
• Bináris síkfa és automatikus automorfizmusai, Grigorchuk-csoport és tualjdonságai: végtelen és minden elem rendje véges
• Nemdeterminisztikus logaritmikus tár; teljes problémák;
• Véletlen algoritmusok; RL osztály és egyenlősége NL-lel; RL^* osztály és az irányítatlan gráfokra vonatkozó s-t-összefüggőség problémája
• P osztály és teljes problémák; NP osztály és teljes problémák