Gyakorlat időpontja és helyszíne: Szerda 08:30-10:00, LD-1-106
Az előadásokat Grolmusz Vince tartja hétfőn 12:10-13:40 között, a Marx teremben (É 0.87). (Neptun kurzuskód: szmtud1u0_m17ex)Számonkérés:
Két zárthelyi lesz év közben március 20-án és május 8-án-én.A zárthelyiken 7 darab 10 pontos feladat lesz kitűzve. Az év végi jegy a két zárthelyi összesített eredménye alapján az alábbiak szerint fog alakulni:
100 pont ≤ 5
080 pont ≤ 4
060 pont ≤ 3
040 pont ≤ 2 [mind a két zárthelyin külön-külön legalább 20 pontot el kell elérni a gyakorlat teljesítéséhez]
Legfeljebb 1 zh-ról lehet igazolatlanul hiányozni. Félév végén lesz egy javító zh, amin egy zh-t lehet javítani vagy pótolni. Ha valakinek a zh-k és a javító zh alapján nem sikerül jegyet szereznie, akkor a teljes félév anyagából írhat gyakuv-t, de arra már csak legfeljebb 2-est lehet kapni.
A zárthelyik mellett lesznek házifeladatok is hétről hétre, amelyek helyes megoldása 2 pluszpontot ér. Ezen felül lesznek csillagos és kétcsillagos feladatok is melyek 3 illetve 5 pluszpontot érnek, és amiket addig lehet beadni ameddig előadáson vagy gyakorlaton le nem zárjuk a kérdést. Összesen legfeljebb 30 pluszpontot lehet beszámítani az év végi jegybe, viszont a pluszpontok nem adnak felmentést a zárthelyinkénti minimum 20 pontos követelmény alól.
A házi- és csillagos feladatokon lehet közösen ötletelni, de mindenki saját maga kell leírja a végső kidolgozott megoldást. Akik közösen dolgoztak egy feladaton írják rá, hogy kikkel ötleteltek.
A házi- és csillagos feladatokat a gyakorlatok előtt tudjátok beadni, figyeljetek hogy a jól olvashatóak legyenek a megoldások!
A házi- és csillagos feladatokat a beadhatjátok a gyakorlat előtt élőben vagy a Moodle-ön keresztül egy pdf fájl feltöltésével a soronkövetkező gyakorlat kezdetéig. A megoldást csinálhatjátok latex-ben, de be is szkennelhetitek a kézzel írott megoldásotokat, vagy akár le is fotózhatjátok -- viszont utóbbi esetben figyeljetek arra, hogy jól olvasható éles és kontrasztos legyen a kép. Vannak különböző okostelefonos kamera szkenner alkalmazások amik a képeket automatikusan olvashatóbbá teszik és átkonvertálják pdf-be, lehetőség szerint ilyet használjatok. Egy ilyen például az Adobe Scan alkalmazás:
Feladatsorok:
- Február 14.
- Február 21.
- Február 28.
- Március 6.
- Március 13.
- Március 20. -- Első zárthelyi
- Március 27. -- Tavaszi szünet
- Április 3.
- Április 10.
- Április 17.
- Április 24. -- Előző órai feladatsort folytatjuk
- Május 1. -- Munka ünnepe
- Május 8. -- Második zárthelyi
- Május 15.
Háttéranyagok:
A 2021-es előadás jegyzete (nem hivatalos, lektorálatlan verzió). Alapvető bonyolultsági osztályok: .html Véges automata szimulátor: .html Turing-gép szimulátor: .html RAM-gép szimulátor: .html Hubai Tamás appja:
Előadáshoz kapcsolódó legfrisebb jegyzet: Lovász László: Algoritmusok bonyolultsága
Egyéb ajánlott olvasmányok: Christos H. Papadimitriou: Számítási bonyolultság, Sanjeev Arora és Boaz Barak: Computational Complexity: A Modern Approach.
Egyéb kapcsolódó ismeretterjeszto könyvek: Raymond Smullyan könyvek, pl.: To Mock a Mockingbird, Roger Penrose: A császár új elméje, Douglas L. Hofstadter: Gödel, Escher, Bach