Informatika2-2010

A MathWikiből
A lap korábbi változatát látod, amilyen Alukacs (vitalap | szerkesztései) 2010. március 19., 06:16-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.com - JAVÍTÁS, ez a helyes cím!!

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.07 23.59

4. előadás (2010-03-01)

Az előadáson az osztályokról volt szó. Az osztályok olyan struktúrák, amelyek tartalmazzák az adatokat és az őket kezelő függvényeket is (egységbezárás elve.) A python konstruktor __init__, reprezentáció __repr__, hossz __len__, nulla-e __nonzero__, + __add__, - __sub__, * __mul__, / __div__, tartalmazás __contains__ függvényeit vettük. Ezekről a függvényekről részletesen itt olvashattok a python manualban:

http://docs.python.org/reference/datamodel.html

Az előadás végén az exception fogalma került elő, a gyakorlaton készítettünk saját Exceptiont is (a benti gépeken nem működik a kód, de a Python IDLE-ben igen). Az exceptionok leírása itt található:

http://docs.python.org/tutorial/errors.html

A myset.py kód itt található:

http://www.math.bme.hu/~lagi/gyak4/myset.py

A modulon.py kód itt található:

http://www.math.bme.hu/~lagi/gyak4/modulon.py

HÁZI FELADAT: (határidő: 2010.03.18 20.00) Válasszatok egy tetszőleges matematikai vagy adat tárolási objektumot. Ezeken értelmezzetek valamennyit a fenti függvények közül, (konstruktor, reprezentáció mindenképp), néhány operator overload-ot, ill. saját függvényeket, és készítsetek egy osztályt. A beadott kódban legyenek minta hívások is (tehát hogy hogyan lehet az osztályt használni.).

Például:

  • kvaterniók (tárolás: együtthatók, műveletek: összeadás, szorzás, kivonás, abszolút érték (hossz), konjugálás
  • 2x2 -es mátrixok (tárolás: 4 db szám, műveletek: összeadás, kivonás, szorzás, inverz, nulla-e)
  • verem: push, pop: beteszek egy elemet, kiveszem a legfelsőt (ha nem üres). Összeadás: a másodikat a felső tetejére teszem. Megfordítás: fordított sorrendben legyenek benne az elemek. Hossz: hány db elem van benne, nonzero: üres-e, tartalmazás: benne van-e az elem.

Bármilyen egyéb, hasonló bonyolultságú dolog jöhet (és örülök neki)! A programokat a következő címre küldjétek: agicpp@gmail.com


KONZULTÁCIÓ: A 6. héten elmarad a hétfői előadás. Azon a héten pénteken 2010.03.19-én lenne egy szabad termünk reggel 8-10-ig. Arra gondoltam, tartanék konzultációt python-ból (nagyjából milyen feladatok lennének, egy-két minta megoldás) + lehetne kérdezni. Mivel előadás nincs azon a héten, gyakorlatot nem tartanék (mivel az csak az egyik csoportnak lenne), viszont ez lenne helyette.

UPDATE: A terem a T604. Mivel sokan mondtátok hogy jönnétek ezért akkor konzultáció lesz 8.30-tól.

A házi feladatokra kapott pontszámot itt nézhetitek meg:

http://spreadsheets.google.com/pub?key=tmL9WA0MdpOjN2VJ5d7MzJA&single=true&gid=1&output=html

5. előadás (2010-03-08)

Az előadáson osztályok öröklésével és a hozzá kapcsolódó fogalmakról volt szó. Bevezetésként készítettünk egy Point osztályt, mely kétdimenziós pontok reprezentálására alkalmas, illetve implementáltuk néhány egyszerű tagfüggvényét. Az óra második felében megvalósítottunk egy Sikidom osztályt, amely egy egységes felületet ad későbbi síkbeli osztályok létrehozásához (kör, háromszög). Az előadáson és gyakorlaton vett kódok itt megtalálhatók:

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

HÁZI FELADAT:

Hozzunk létre örökléssel osztályokat, melyek személyek, és dolgozók adatit tudja tárolni, illetve néhány jellemzőjüket tudja számítani. Az ősosztály neve legyen Szemely, __init__ tagfüggvénye kapja meg a személy életkorát illetve nevét. Ebből származtassunk le egy Alkalmazott nevű osztályt, mely az életkor és név mellett még az illető órabérét is eltárolja (az init függvényben használjuk a super függvényt az ősosztály adatainak eléréséhez). Az alkalmazott osztályt egészítsük ki egy szabadnapok_száma tagfüggvénnyel, ami 20-szal térjen vissza, ha az illető 35 évnél fiatalabb, egyébként 28-cal. Az alkalmazott osztályból származtassunk le két osztályt (félállású, illetve teljesállású) melyeknek legyen egy új fizetésszámít tagfüggvénye, félállású esetén 80 * oraber, teljesállású esetén 160*oraber legyen a visszatérési értéke. A teljesállású osztályból még származtassunk le egy fonok osztályt, melyhez egy premium nevű új adattagot vegyünk fel az előzőekhez, és a fizetésszámít függvényét módosítsuk a super függvény használatával úgy, hogy visszatérési értéke 40*oraber+premium legyen. Az előző linken találtok mintahívásokat az osztályokhoz.

Határidő: 2010.03.21 23.59

FIGYELEM: A 7. héten nem lesz előadás, hanem mindkét alkalommal gyakorlatot tartunk, ezért kérném, hogy a hétfői gyakorlat csoportja 8.30-ra jöjjön a H57-be, a pénteki pedig 8.30-ra a H27-be.

A korábbi házikra megoldásokat találtok az alábbi helyen:

http://info.ilab.sztaki.hu/~kisstom/info2/hazi_megoldasok

Személyes eszközök