Informatika2-2010
(→3. előadás (2010-02-22)) |
|||
56. sor: | 56. sor: | ||
A program az előadáson megadott formátumú file-t olvassa be, az out-ban látható eredményt adja vissza. | A program az előadáson megadott formátumú file-t olvassa be, az out-ban látható eredményt adja vissza. | ||
− | |||
A programokat a következő címre küldjétek: fadyga@math.bme.hu | A programokat a következő címre küldjétek: fadyga@math.bme.hu | ||
Határidő: 2010.03.06 23.59 | Határidő: 2010.03.06 23.59 |
A lap 2010. február 23., 16:34-kori változata
Tartalomjegyzék |
Á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
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:
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 file és string osztály 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). 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, majd törli azokat, ehhez elkészítettem egy kódot, 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 és a kód itt megtalálható:
http://info.ilab.sztaki.hu/~kisstom/info2/3het
A program az előadáson megadott formátumú file-t olvassa be, az out-ban 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