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 pótpótzh szabályai:
  

• A pótpótzhra a Neptunban jelentkezni kell.
  
• A pótpótzh május 17-én  12:00-kor kezdődik. Az első rész 12:00-tól 12:30-ig tart, a teszt eredményei 12:30-kor lesznek láthatóak. Ezután van 10 perc szünet, a második rész 12: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 13: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.
• A pótpótzh anyaga megegyezik a zh anyagával, azaz a 6. heti előadással zárul.
  
• A pótpótzht  javító céllal nem lehet megírni, csak az jöhet, akinek a pótzh után még nincsen aláírása. 

• Aláírás és jegyszerzés általános 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.
  

• A vizsga szabályai

• A vizsga open book azzal a szabállyal, hogy a weboldalon található bármi jegyzetet, megoldást, segédanyagot, Teams-es, Moodle-ba feltöltött  anyagot szabad használniuk, de egymással nem kommunikálhatnak és segítséget sem kérhetnek másoktól.
  
• A vizsga előtt mindenkinek, akinek van aláírása van már (zh/60)*40 zhkból szerzett pontja, ahol zh jelöli a zhn vagy pzhn vagy ppzhn szerzett pontot. A vizsgán további 62 pontot lehet szerezni.
  
• A vizsga első része egy 10 kérdéses teszt, a teljes félév anyagából, 30 perc alatt kell megoldani.  Csak egyszer lehet próbálkozni, a kérdések között nem lehet visszafelé lépni. Rossz válaszért nem vonunk le pontot. A teszten legalább 6 helyes választ el kell érni, különben  a vizsga nem sikerült. Akinek van legalább 6 jó válasza, az ezzel kap 12 + 2*(jó_válaszok_száma) pontot (azaz valamit 24 és  32 között).
• A teszt után be lehet fejezni a vizsgát, ekkor a vizsga pontszáma a teszten szerzett pontszám, a teljes félévi pontszám pedig a zhkból szerzett pontszám  + a teszt pontszáma.  Ha ez a teljes pontszám 55-nél kevesebb, akkor 2-es, ha legalább 55, akkor 3-as jegyet ajánlunk meg (négyest és ötöst itt még nem lehet szerezni).
  
• A teszt befejezése után (a teszt eredményének és így a megajánlott jegynek az ismeretében) kell eldönteni mindenkinek, hogy elfogadja-e ezt a megajánlott jegyet vagy megy tovább a vizsga második részére. Erre a döntésre nagyjából 20 perc lesz, ezt a döntését a Moodle-ben kell majd jelezni úgy, hogy feliratkoznak az i.vizsga 2. részére jelentkezés csoportba.  A 2. rész csak azok számára nyílik meg, akik feliratkoztak. Feliratkozni csak azok tudnak, akik legalább 6 kérdésre jól válaszoltak a tesztben. A 2. rész megnyílásáig a döntésüket még meg tudják változtatni. Aki nem jelentkezik a 2. részre az ezzel elfogadja a teszt után megajánlott jegyet.
• Aki úgy dönt, hogy nem fogadja el a teszt után megajánlott legalább elégséges jegyet, az a 2. részben kap három kifejtős feladatot, mindegyik 10 pontot ér. Ezek a példák a gyakorlatokon megoldott komplexebb feladatokhoz lesznek hasonlóak.  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 60 perc lesz, ebbe a feltöltésnek is bele kell férnie. Nem kell begépelni a megoldást, lehet kézzel írott megoldás beolvasva vagy befotózva és pdf-fé konvertálva.
• Aki feliratkozott a második részre, de itt nem ad be megoldást vagy ad be megoldást, de nem ér el legalább 6 pontot a maximális 30-ból, az a teszt utáni megajánlott jegyéből egyet elveszít, azaz ha az a jegy kettes volt, akkor megbukik a vizsgán, ha hármas, akkor pedig kettes lesz a vizsgajegye.
• Aki elér legalább 6 pontot a kifejtős részen, annak a vizsgára kapott pontszáma a teszten szerzett pontja + kifejtős részen szerzett pontok. A teljes féléves pontot a zhkból szerzett pontok + a vizsgán szerzett pontok módszerrel számoljuk és az így kapott pontszám alapján 40-54-ig kettes, 55-69-ig hármas, 70-84-ig négyes, 85-től jeles a jegy. 
  
• A vizsgán az 51 pont feletti pontok számítanak IMSc pontnak, a félév során legfeljebb 25 IMSc pont szerezhető (zhból és vizsgán összesen).
• Aki részt vett a vizsga második részén és azután legalább elégséges jegyet szerzett, de ezzel a jeggyel nem elégedett, az az eredményközlés napján szóbelizhet, itt egy jegyet lehet javítani vagy rontani a végső jegyen. Ezen a szóbelin elméleti kérdések várhatóak, nehézségük attól függ, hogy hányas jegyhez hány pont hiányzik.
• Mintafeladatsor elérhető lesz nemsokára a teszthez és a második részhez is a Moodleban. A próbavizsgán nincs korlát a próbálkozások számára, de itt is 30 perc van egy-egy kitöltésre a teszt esetén.
  
• Mindegyik vizsga előtt lesz konzultáció, a vizsgák javítása után pedig fogunk megoldásismertetőt és megtekintést tartani (itt először a megoldásismertetőben a kifejtős feladatok megoldásait és pontozását mondjuk el, majd lehet egyénileg is kérdezni a javítóktól). ezután fog sor kerülni a javító célú szóbelikre (egyéni Teams hívás keretében, előre egyeztetett időpontban).
  
• 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 40 pontra), 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) vette fel, akkor amennyiben bármelyik alkalommal (zh vagy pótzh) dolgozatot írt, akkor annak pontszáma számít félévközi pontszámnak, kivéve, ha a dolgozat nem érte 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.

pótzh: április 21.

pótpótzh: május 17., 12:00-kor

• Mindegyik vizsga előtt lesz konzultáció, erre a konzultációra jöjjenek a németes képzés hallgatói is és a matematikus hallgatók is. A Teamsben létrehoztam egy csatornát, ahova lehet kérdéseket feltenni a konzultáció előtt. Ezeket a kérdéseket vagy megválaszoljuk ott írásban (attól függően, hogy mennyire érünk rá, illetve, hogy meg lehet-e könnyen válaszolni rajzolás és hosszas magyarázat nélkül őket) vagy pedig a konzultáción beszélünk róluk élőben. Mivel a konzultáció pénteken van, a vizsga meg hétfőn, ezért lehet, hogy valakinek a konzultáció után támad kérdése. Ezeket is a Teams-es csatornában lehet feltenni, igyekszünk válaszolni, amennyire a hétvégén az időnk engedi.
  

• A vizsgán a teszt  eredménye azonnal kiderül, a kifejtős kérdések javítása azonban időbe telik. Másnapra igyekszünk kijavítani ezeket, az eredmény és a megoldásokhoz fűzött megjegyzések a Moodle-ban lesznek. Lesz minden vizsga után egy megtekintés is. A németes hallgatók és a matematikus hallgatók megtekintése külön lesz, ennek pontos idejéről és formájáról a németes előadótól, illetve a matekos gyakorlatvezetőjüktől fognak tájékoztatást kapni. A magyar nyelvű infósok megtekintésén először elmondjuk a kifejtős kérdések megoldását és vázoljuk a pontozást, majd akinek kérdése van a saját dolgozatával kapcsolatban, annak lesz lehetősége kétfős meetingben a javítóval beszélni. Szintén a megoldásismertető után kerül sor a szóbelikre, ha valaki javítani szeretne egy legalább elégséges jegyet. Mindkettőre (javítóval beszélni, szóbelire jelentkezni) a megoldásismertető végéig lehet  jelentkezni, Teams üzenetben vagy emailben. 
  

• A pontos időpontok itt vannak:

1. vizsga:

• konzultáció: május 28.,  péntek, 13-15
• vizsga: május 31., hétfő 12-14
• megtekintés: június 2., szerda  13 óra
  

2. vizsga:

• konzultáció: június 4.,  péntek, 13-15
• vizsga: június 7., hétfő 12-14
• megtekintés: június 9., szerda  13 óra

 
3. vizsga:

• konzultáció: június 11., péntek 13-15
• vizsga: június 14., hétfő, 12-14
• megtekintés: június 16., szerda 13 óra
  

4. vizsga:

• konzultáció: június 18., péntek 13-15
• vizsga: június 21., hétfő, 8-10
  
• megtekintés: június 21., hétfő 14 óra
  

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