Informatika2-2010

A lap 2010. február 28., 12:44-kori változata

Általános információk

• A tárgy előadói és gyakorlatvezetői: Lukács Ágnes, Kiss Tamás

Email címek: {lagi, fadyga} KUKAC math PONT bme PONT hu

• Az előadás időpontja és helye: hétfő 08:15-9:00 H46.

A gyakorlatok időpontja és helye: hétfő 09:15-10:00 H57, péntek 9:15-10:00 H27

• Követelmények

Tananyag

A félév első felében Python, illetve objektum-orientált programozás, második felében a C nyelv. Ajánlott irodalom Pythonhoz:

• Python tutorial
• http://www.greenteapress.com/thinkpython/thinkpython.html

A félév során a Python 2.6.4-es verzióját fogjuk használni, mely innen letölthető: http://python.org/download/

1. előadás (2010-02-08)

Az előadáson átismételtük a Sage-ben tanultakat, a következő fogalmak kerültek elő:

• típus
• operátor
• vezérlési szerkezetek
• függvény definiálás

Az előadáson átvett kódok a következő linken elérhetők: http://info.ilab.sztaki.hu/~kisstom/info2/

A következő gyakorlatra két házi feladat van kitűzve:

• Írjunk Python-ban rekurzív függvényt, mely egy input egész n-re ellenőrzi a 3*n+1 algoritmus helyességét, és végül visszatér egy listával, mely tartalmazza azokat az egészeket, melyekre az algoritmus meghívódott. A helyesség ellenőrzése alatt azt értem, hogy a függvény addig hívja rekurzívan önmagát, amíg a kapott egész nem 1, ekkor egy üres listával return-nöl, egyébként meg a rekurzívan megkapott listával, amelyhez appendolja n jelenlegi értékét.
• Írjunk Python-ban függvényt, mely bemenetként egy n egészet vár, és az Erátoszthenészi szita algoritmusát használva kiírja n-ig a prímszámokat.

2. előadás (2010-02-15)

Az előadáson egy konvex burok meghatározó algoritmust vettünk. A lényege röviden: minden élre ellenőrizzük, hogy az él végpontjait nem számítva, az összes pont az él egy adott oldalán van. Azt, hogy az él adott oldalán van, az élből és a pontból kapott háromszög előjeles területének előjeléből tudjuk meg.

A gyakotlaton vettünk egy másik algoritmust, amely először sorbarendezi a pontokat (x koordináta szerint), majd a felső konvex burkot aszerint határozza meg, hogy az aktuális legszélsőhöz képest "feljebb" van, akkor megtarjuk, ha lejjebb van, eldobjuk.

Ezen elgoritmusok forráskódjait megtaláljátok itt: http://math.bme.hu/~lagi/gyak2

A következő gyakorlatra a következő feladatok közül lehet választani:

• Jó ötlet alapján, az élek listájából a pontok listájának meghatározása (bonyodalom: 3 pont egy egyenesen, akkor mind a 3 él bent van.)
• (javasolt): olyan algoritmus, amely az x sorrend alapján elindul, majd a szög alapján "legfelső" pontot választja ki, az ilyenekből állítja össze a konvex burkot.
• Bármilyen más konvex burok algoritmus implementálása, pár sor magyarázattal együtt.

A programokat a következő címre küldjétek: agicpp@gmail.hu

Határidő: 2010.02.28 23.59

3. előadás (2010-02-22)

Az előadás első felében a python file és string osztályainak használatáról, fontosabb tagfüggvényeiről volt szó, melyek segítségével egy file-ban eltárolt irányitott gráfot olvastunk be. A második felében átismételtük a mélységi bejárás algoritmusát, ami felhasználható arra, hogy meghatározzuk egy irányított körmentes gráf egy topologikus rendezését (a csúcsok olyan sorba rendezése, melynél minden él kisebb indexűből vezet nagyobb indexűbe). Ezekről bővebben itt olvashattok:

http://fi.inf.elte.hu/adatszerkezet/ii_felev/graf/kricsi/

http://hu.wikipedia.org/wiki/Topologikus_sorrend

A házi feladat is ehhez kapcsolódik:

Készítsük el, egy irányított, körmentes gráf egy olyan szintekre bontását, melyekben az egy szinten levő csúcsok között nem vezet él. A javasolt algoritmus egy iterációban meghatározza a gráf forrásait(azokat a csúcsokat melyekbe nem vezet irányított él), majd törli azokat. A feladathoz elkészítettem egy kódot(partition.py), amelyben már csak két függvényt kell megírni, bármilyen ettől független jó megoldás beküldhető. Az előadás anyaga, a kód, valamint azok futtatása és kimenete itt megtalálható:

http://info.ilab.sztaki.hu/~kisstom/info2/3het

A program az előadáson megadott formátumú file-t olvassa be, a futtatas_es_kimenet.txt-ben látható eredményt adja vissza.

A programokat a következő címre küldjétek: fadyga@math.bme.hu

Határidő: 2010.03.06 23.59