Algoritmuselmélet (VISZAB03 ás VISZAB01)

2021 tavasz

• Előadás: csütörtök 12.15-14:00-ig a Teamsben 
  
• Előadó: Csima Judit,  IB136/b, email, weboldal


• Gyakorlatok: 
  

  11	hétfő 12.15 - 13.45	Gujgiczer  Anna	gujgiczer.anna_KUKAC_gmail.com
  12	hétfő 12.15 - 13.45	Gálai Janka	galaijanka_KUKAC_gmail.com
  13	hétfő 12.15 - 13.45	Horváth Bálint	hbalintt96_KUKAC_gmail.com
  14	hétfő 12.15 - 13.45	Fridvalszky András	fandras_KUKAC_cs.bme.hu
  15	hétfő 12.15 - 13.45	Pintér József	jozsikamk_KUKAC_gmail.com
  16	hétfő 14.15 - 15.45	Gálai Janka	galaijanka_KUKAC_gmail.com
  17	hétfő 14.15 - 15.45	Gujgiczer  Anna	gujgiczer.anna_KUKAC_gmail.com
  19	hétfő 14.15 - 15.45	Csima Judit	csima_KUKAC_cs.bme.hu
  18 + 20	hétfő 14.15 - 15.45	Horváth Bálint	hbalintt96_KUKAC_gmail.com
  21	kedd 10.15-11.45	Papp László	lazsa_KUKAC_cs.bme.hu
  22	kedd 10.15-11.45	Rácz Dániel	danielracz10_KUKAC_gmail.com
  23	kedd 10.15-11.45	Matyasi Lilla	lilla.matyasi_KUKAC_gmail.com
  24	kedd 10.15-11.45	Nemkin Viktória	nemkin_KUKAC_cs.bme.hu
  25	kedd 10.15-11.45	Csima Judit	csima_KUKAC_cs.bme.hu
  I1	kedd 12.15-13.45	Papp László	lazsa_KUKAC_cs.bme.hu
  I2	hétfő 10.15 - 11.45	Palincza Richárd	richard.palincza_KUKAC_gmail.com
  I3	hétfő 12.15-13.45	Palincza Richárd	richard.palincza_KUKAC_gmail.com

        
  
• Matematikus hallgatók: A matematikus hallgatóknak a számukra kiírt VISZAB01 kódú tárgyat kell felvenniük. Ehhez ugyanez az előadás (és követelményrendszer) tartozik, de gyakorlat van hozzá külön, gyakorlatvezető Rónyai Lajos (lajos_KUKAC_math.bme.hu).

  ---

• A zh szabályai:
  
• A zh március 29-én reggel 8:00-kor kezdődik. Az első rész 8:00-tól 8:30-ig tart, a teszt eredményei 8:30-kor lesznek láthatóak. Ezután van 10 perc szünet, a második rész 8:40-kor nyílik meg azoknak, akik legalább 6 jó választ szereztek az első részben. A második rész megoldását 9:50-ig kell feltölteni pdf-ben.
• A kifejtős feladatok megoldását indokolni kell, a megoldás során csak az órán tanult állı́tásokat használhatják fel indoklás nélkül. Órai saját jegyzet, a tárgy weboldalán vagy a tárgy Moodle felületén levő bármilyen anyag szabadon használható a teszt és a második rész alatt is, de mással kommunikálni és a fentieken kı́vül egyéb anyagot használni nem szabad.
  
• Aláírás és jegyszerzés feltételei:
•  Egy félévközi zárthelyi lesz, ezen lehet az aláírást megszerezni.
  
  • A zh két részből fog állni: egy feleletválasztós első részből és egy feladatkidolgozós második részből. A két rész egymás után zajlik majd, mindkettő a Moodle-ben lesz, a korábban meghirdetett zh időpontban (a kezdés pontos időpontját majd időben jelezni fogom a Moodleban is és itt a weboldalon is).
  • Az első részben 30 perc alatt 10 feleletválasztós kérdést fognak kapni, a kérdések alapfogalmakat tesztelnek.  (Egy próbazh elérhető a Moodle-ben, ott meg tudják nézni, hogy milyen nehézségű kérdésekre kell számítani.) A feladatok random sorrendben jönnek, visszalépni köztük nem lehet és csak egyszer lehet a tesztet kitölteni. Aki a kapott 10 kérdésből nem ér el legalább 6 jó választ, annak a zh-ja sikertelen. Akinek legalább 6 jó válasza van, az szerez annyiszor 3 pontot ebben a részben, ahány jó válasza volt (azaz valamit 18 és 30 pont között).
  • Az első rész lezárulta után az itt szerzett pontok azonnal kiderülnek (a Moodle mutatja majd). Pár perc szünet után nyílik meg a zh második része azok számára, akiknek az első részben volt legalább 6 jó válaszuk.  A második részben négy kifejtős feladat lesz, mindegyik 10 pontot ér. Ezek a feladatok hasonlóak lesznek a gyakorlaton látott nehezebb példákhoz, itt a megoldásokat indokolni kell.  (Ehhez a részhez is van egy elérhető próba verzió a Moodle-ben.) Ennek a résznek a megoldását egy darab pdf file-ként kell feltölteniük a Moodle-be a beadási határidőig. A vizsga ezen második része 70 perc lesz, ebbe a feltöltésnek is bele kell férnie (javaslom, hogy a feltöltésre legalább 10 percet hagyjanak). Nem kell begépelni a megoldást, lehet kézzel írott megoldás szkennelve vagy befotózva és pdf-é konvertálva. Ezzel a második résszel maximum 40 pontot lehet szerezni. A második részben nincs minimumkövetelmény, de a két résznek együtt el kell érnie a 24 pontot.  Ez azt jelenti, hogy nem 70, hanem 60 pontból számoljuk az elérendő 40%-ot, mert a négy kifejtős feladat egyikére IMSc-s feladatként gondolunk. Nem lesz külön megjelölt IMSc-s feladat, mindegyik példát beadhatja mindenki, az IMSc pontok majd úgy keletkeznek, hogy az 51 pont feletti pontok (de legfeljebb 15 pont) számítanak IMSc pontoknak az infós hallgatók számára.
    

• A pótzh ugyanolyan felépítésű, mint  a zh, anyaga megegyezik a zh anyagával, pótzht lehet javító céllal is írni.  Javítási kísérlet esetén a pótzh pontszáma felülírja a zh pontszámát, azzal a kivétellel, hogy ha a pótzh nem éri el a 24 pontot, de a zh elérte, akkor a megszerzett aláírás nem vész el, viszont a zhn szerzett pontszám visszamegy 24 pontra.
• A pótlási időszakban még egyszer megkísérelhető az addig sikertelen zh megírása.  Ezt már javító céllal (már megszerzett aláírással) nem lehet megírni. Erre a pótpótzh  alkalomra a Neptunban kell jelentkezni. A pótpótzh anyaga és felépítése megegyezik a zh anyagával és felépítésével.
• A vizsgaidőszakban írásbeli vizsgát tartunk, a vizsgára az jöhet, akinek van aláírása.
  
• Ha  tantermi számonkérés lesz, akkor a vizsgán is 6+1 feladat van, mindegyik 10 pontot ér. Ha a vizsgán elért pontszám kevesebb, mint 24, akkor a vizsga elégtelen. Ha a vizsga legalább 24 pontos, akkor a vizsgajegyet átlagolva alakítjuk ki úgy, hogy abba a félév közben szerzett pontszám 40%, a vizsga pontszáma pedig 60% erejéig számít bele. Az így eredő pontszám alapján a jegyek: 24-től 32-ig elégséges, 33-tól 41-ig közepes, 42-től 50-ig jó, 51-től jeles.
• Ha online számonkérés lesz, akkor a vizsga  a zh-hoz hasonló felépítésű lesz, egy feleletválasztós első részből és egy feladatkidolgozós második részből fog állni, összesen 70 pontot lehet majd szerezni.  Ennek pontos részleteit később hirdetjük ki.
  
• A vizsgán az 51 pont feletti teljesítménnyel az informatikusok IMSC pontokat szerezhetnek, de legfeljebb 15 pontot. Az összesen megszerzett IMSC pontok száma (zh és vizsga) együtt legfeljebb 25 lehet.
• A vizsgán szerzett legalább elégséges jegyen szóbelivel egy jegyet lehet módosítani (javítani vagy rontani), de a szóbelin IMSC pont már nem szerezhető.
  
• Ismétlő vizsga esetén a félév közben szerzett pontok változatlanul érvényesek.
• Ha valaki sikeres vizsga után újra megírja a vizsgát javító céllal, akkor az új vizsga eredménye felülírja az eredeti eredményt, még akkor is, ha az új vizsga elégtelen.
  
• Korábbi félévben szerzett aláírás esetén vizsgakurzusos hallgatóknál az akkor szerzett félévközi pontszám az érvényes (visszaskálázva az eféléves pontokra), vizsgakurzusos tárgyfelvétel esetén zht írni és így a félévközi pontot javítani nem lehet. Ha korábban szerzett aláírással valaki a normál kurzust (nem a vizsgakurzust) veszi fel, akkor amennyiben bármelyik alkalommal (zh vagy pótzh) dolgozatot ír, akkor annak pontszáma számít félévközi pontszámnak, kivéve, ha a dolgozat nem éri el az aláíráshoz szükséges minimumpontszámot, mert  ekkor az elért pontszám a minimális félévközi pontszám lesz (aláírást nem lehet elveszíteni). Ha korábbi aláírással rendelkező hallgató nem kísérel meg sem zht, sem pótzht  írni, akkor a korábbi féléves pontszáma számít félévközi pontnak.

Zh időpontok:

zh: március 29., hétfő reggel 8:00-9:50

pótzh: április 21., szerda este 18-20

pótpótzh: május 17., hétfő, a pótlási héten

Tankönyv:

Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok (TYPOTEX). Link a Typotex oldalára (ahol a könyv online olvasható)

Kiegészítések a tankönyvhöz:

1. Mintaillesztés
2. Az O jelölésről és fóliák erről
3. Véges automaták
4. Környezetfüggetlen nyelvtanok
5. Veremautomaták
6. Turing-gépek
7. NP-teljes problémák
8. Lineáris és egészértékű programozás
9. Elágazás és korlátozás, dinamikus programozás
10. Közelítő algoritmusok
11. Keresés, rendezés
12. Keresőfák
13. Piros-fekete fák
14. 2-3-fák
15. Hash (vödrös és nyitott címzésű)

Versenyek

Őszre: ACM programozási verseny

És ha valaki inkább programozni szeret: 24 órás programozási verseny

Egy másik verseny a tavaszi félévre

A legrövidebb út és más "triviális" problémák-- Implementation challenges

Modeling and Optimization verseny

Student Contest on Software Engineering

Vagy pl. az évente megrendezett gráf rajzoló verseny

És még kettő: topcoder és code jam

Csima Judit, BME   VIK   SZIT