Informatika2-2010

A MathWikiből
A lap korábbi változatát látod, amilyen Fadyga (vitalap | szerkesztései) 2010. február 23., 15:36-kor történt szerkesztése után volt.

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 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). 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

Személyes eszközök