Belépés címtáras azonosítással
magyar nyelvű adatlap
angol nyelvű adatlap
A programozás alapjai 1
A tantárgy angol neve: Basics of Programming 1
Adatlap utolsó módosítása: 2022. augusztus 24.
https://www.hit.bme.hu/portal/args/munkatarsak/oktatok_kutatok
A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.
A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.
A számítógép-programozás a villamosmérnöki ismeretek nélkülözhetetlen részét képezi. A tantárgy célkitűzése, hogy a hallgatók készség szinten alkalmazható ismereteket szerezzenek a számítógépes problémamegoldás módszereinek és alapvető eszközeinek használatában. További cél, hogy a megszerzett ismereteket és készségeket további tanulmányaik során hatékonyan legyenek képesek alkalmazni.
A célkitűzés teljesítését egy magas szintű, mégis gépközeli programozási nyelv, a C megismerése teszi lehetővé. Amellett, hogy a hallgatók megismerkednek az imperatív programozási paradigma fogalomkörével, és ezzel egyben megalapozzák a további programozási nyelvek elsajátítását is, megismerkednek a számítógép hardverelemeivel is. A számítógépes laborgyakorlatok folyamatosan követik az előadások tematikáját, és bevezetik a hallgatókat a modern fejlesztőkörnyezetben végzett programozási munka alapjaival.
1. Alapfogalmak: Az imperatív programozási paradigma. Algoritmus és annak leírása. Pszeudokód, folyamatábra. Kifejezések. Állandók és változók. A C nyelv alapjai. Forráskód, megjegyzések, kulcsszavak. Változók deklarálása. Értékadás. Beolvasás és kiírás.
2. Strukturált programok. A strukturált programozás tétele. A struktorgram. Strukturált programozás C-ben: az if és while utasítások. Egyéb strukturált elemek: for, do-while, switch. Összetett vezérlési szerkezetek.
3. Vektoralgoritmusok. A soros adatfeldolgozás: összegzés, számlálás, szélsőérték-keresés. Összetett logikai kifejezések. Tömbök: deklarálás, kezdetiérték-adás, indexelés. A túlindexelés. Egyszerű tömbös algorimusok: hisztogram. Ciklikus indexelés: körbuffer megvalósítása. Nemstrukturált vezérlő elemek: break, continue.
4. A C nyelv aritmetikai típusai: Az egész típusok. Ábrázolás, túlcsordulás. A logikai típus megjelenítése. A karakter típus: Az ASCII-tábla. Műveletek karakterekkel. A lebegőpontos típus: Ábrázolás, relatív pontosság. A gépi számábrázolási pontosság.
5. Függvények. A funkcionális dekompozíció. Függvények definiálása és hívása. A függvényhívás mechanizmusa. A verem. Lokális és globális változók láthatósága és élettartama. A felsorolt típus.
6. Struktúrák és a rajtuk végezhető műveletek. Struktúrákon végzett műveletek megvalósítása függvényekkel. Típusnév-hozzárendelés.
7. Indirekció. Memóriacímek és mutatók. Indirekt változóhozzáférés mutatókon keresztül. Cím szerinti paraméterátadás. Függvény által paraméterlistán visszaadott értékek. Mutatóaritmetika. Mutatók és tömbök kapcsolata. Sztringek és műveleteik. Szabványos sztringkezelő függvények.
8. Dinamikus memóriakezelés. Memóriafoglalás és -felszabadítás. Memóriaszivárgás. A heap fogalma. Dinamikusan foglalt tömbök és sztringek. Operátorok és kifejezések. Kifejezésfák felépítése. Operátorok precedenciája és asszociativitása. A kifejezésfák kiértékelése, operandusok kiértékelési sorrendje. A logikai rövidzár. Mellékhatásos kifejezések. Balérték és jobbérték fogalma. Kifejezések kiértékelésének sorrendhatár-pontjai.
9. Fájlkezelés C-ben. Műveletek szöveges fájlokkal: megnyitás, írás, olvasás, bezárás. A pufferelt fájlkezelés. Műveletek bináris fájlokkal: megnyitás, írás, olvasás, bezárás. Többdimenziós tömbök. Többszörös (sorfolytonos) indexelés. Többdimenziós tömb átadása függvénynek. Dinamikusan foglalt többdimenziós tömbök. Mutatótömbök, sztringtömbök.
10. Dinamikus adatszerkezetek. Önhivatkozó adatszerkezetek. Egyszeresen láncolt listák. Lista bejárása, keresés, beszúrás, törlés listából. Többszörösen láncolt listák. Strázsás listák. Listákkal megvalósított speciális adatszerkezetek: FIFO, LIFO, több szempont szerint rendezett listák, körkörösen láncolt listák.
11. Rekurzió. A rekurzió fogalma egyszerű példákon keresztül. A rekurzió megvalósítása a veremben. Iteráció és rekurzió összehasonlítása. Rekurzív algoritmusok: útvonalkeresés. Bináris fák. Bináris fa felépításe, bejárása, elem keresése, beszúrása. Mélységi bejárások: inorder, preorder, postorder.
12. Keresés és rendezés. Lineáris keresés rendezett és rendezetlen adatvektorban (tömbben és listában). Logaritmikus keresés tömbben. A keresések lépésszáma. Rendező algoritmusok: közvetlen kiválasztás, közvetlen beszúrás, buborékrendezés. Gyorsrendezés. Rendező algoritmusok lépésszámának összehasonlítása.
13. Függvénymutatók. Függvény mint függvény paramétere. Generikus algoritmusok. Típusfüggetlen generikus algoritmusok megvalósítása. Generikus keresés és rendezés.
A gyakorlatok és laborok részletes tematikája:
1. Gyakorlat: Hétköznapi és egyszerű matematikai algoritmusok, folyamatábraszerű rajz készítése, algoritmusok lejátszása. Labor: A HSZK használata. Operációs rendszer, parancssor, egyszerűbb parancsok, program indítása parancssorból, program indítása paraméterekkel, átirányítás.
2. Gyakorlat: Algoritmizálás strukturált elemekkel: struktogram, strukturált pszeudókód, C kód. Labor: IDE bemutatása. Egyszerű, kézhez kapott programok fordítása, átalakítása.
3. Gyakorlat: Adatsorok feldolgozását igénylő egyszerű problémák. Tömbök használata, beolvasás tömbbe; elemek megváltoztatása, kiíratása, indexelés. Labor: Vezérlési szerkezetek (ciklusok, elágazás), beépített függvények. Egyszerű számelméleti algoritmusok kódolása, kiíratás, egyes beépített matematikai függvények használata.
4. Gyakorlat: Egyszerű matematikai jellegű függvények, karakter-feldolgozó függvények. Összetettebb problémák dekompozíciója. Karakter típusú változók és tömbök használat, feldolgozása. Labor: Végjeles adatsor feldolgozása. Tömbkezelés programban, beolvasás tömbbe; elemek megváltoztatása, kiíratása, indexelés, túlindexelés.
5. Gyakorlat: Függvények használata. A funkcionális dekompozíció. Labor: Függvények kódolása, egyszerű matematikai jellegű függvények. Karaktereket feldolgozó függvények és programok. Nyomkövető (debug) funkció megismerése, lépésenkénti végrehajtás, változók megfigyelése.
6. Gyakorlat: Struktúrák használata, struktúrákat kezelő függvények. Felsorolt típus használata. Labor: Struktúra, struktúra mint paraméter. Egész típusok bináris megjelenítése, túlcsordulás. Lebegőpontos ábrázolás pontatlansága.
7. Gyakorlat: Függvények és pointerek, cím szerinti paraméterátadás. Tömb átadása függvénynek. Sztringkezelés saját függvényekkel. Labor: Pointerek, tömbök, sztringek kezelése függvényekkel. Beépített sztringkezelő függvények. Kapcsolódó nyomkövetési funkciók.
8. Gyakorlat: Dinamikus memóriakezelés. Dinamikus tömbök. Labor: Dinamikus tömbök. Szöveges fájlkezelés.
9. Gyakorlat: Formázott olvasás és írás szöveges fájlból és sztringből. Labor: Egyszerű lista építése bináris fájlból. Összetettebb listás feladat továbbfejlesztése.
10. Gyakorlat: Dinamikusan foglalt struktúrák. Listák kezelése. Adatszerkezet építése. Labor: Egyszerű lista építése bináris fájlból. Összetettebb listás feladat továbbfejlesztése.
11. Gyakorlat: Rekurzió fogalma. Valódi és álrekurzió. Fák, mint rekurzív adatszerkezetek. Fák bejárása, keresőfák és dekódoló fák Labor: Fa építése, bejárása, törlése. Fésűs lista adatszerkezet.
12. Gyakorlat: A program kapcsolata a külvilággal. Parancssori paraméterek feldolgozása. Labor: Fésűs lista adatszerkezeten alapuló egyszerű program fejlesztése, beleértve a hibakeresést és az egyszerű tesztelést is.
13. Gyakorlat: Bitműveletes feladatok, maszkolás. Függvénypointerek. Függvény átadása függvénynek, keresési feladat paraméterként átadott függvény feltétellel. Gyakorlás a nagyzárthelyire. Labor: Függvény átadása paraméterként. Szabványos kereső és rendező függvények használata. Többdimenziós tömbök gyakorlása.
A tárgyból heti egy alkalommal előadást tartunk a teljes évfolyamnak és heti egy alkalommal tantermi gyakorlatot tartunk a tanulókörök számára. A tárgyból számítógépes laboratóriumi foglalkozásokat is tartunk a Hallgatói Számítóközpont (HSZK) termeiben, az órarend szerinti időpontokban, kiscsoportos oktatással. Az előadások anyagát lefedő oktatóvideók elérhetőek a tantárgy honlapján. Az otthoni gyakorlást a tárgyhonlapon megvalósított online feladatbeadó és tesztelő rendszer segíti.
A félév végi jegy megszerzésének feltételei az alábbiak:
- Jelenlét: az órákon (előadás, gyakorlat, labor) való rendszeres részvétel. A hiányzások megengedett mértékét a TVSz rögzíti (30%). A feltételnek mindhárom óratípuson külön-külön is teljesülnie kell. A laborgyakorlatokon az aktív részvételt a laborfeladatok egy részének online feltöltésével és tesztelésével ellenőrizzük. Az elégtelen felkészültség mulasztott laboralkalomnak számít.
- Kis zárthelyik (ellenőrző dolgozat): a félév során hat alkalommal kis zárthelyit íratunk a gyakorlatokon. Ezek három témakört ölelnek fel, azaz három dolgozatpárost jelentenek. Minden pár közül a jobban sikerült eredménye számít; ez kell elérje az adott dolgozatra szerezhető pontszám 40%-át. A meg nem írt ZH pontszámát nullának tekintjük.
- Nagy zárthelyi: a szorgalmi időszak alatt két alkalommal, az évfolyam terhelési táblázata szerinti időpontban nagy zárthelyi dolgozatot íratunk. Ezeknek egyenként nincs minimumkövetelménye, csak az összegüknek. Az összpontszám el kell érje a két zárthelyire szerezhető összpontszám 50%-át. A meg nem írt ZH pontszámát nullának tekintjük.
- Nagy házi feladat: minden hallgatónak egy egyéni nagy házi feladatot kell megoldania, önálló munkával. Ennek elfogadható szintű teljesítése a félév követelménye. A nagy házi feladatokat a 6. héten adjuk ki és a 13. héten kell beadni a megoldásokat. Az előrehaladást a félév közben részfeladatok alapján ellenőrizzük.
A félévközi jegy a nagy zárthelyik, a páronként jobban sikerült kis zárthelyik pontszáma, és a nagy házi feladat pontszáma alapján számítódik ki. A nagy zárthelyikre maximum 2×40 pont, a kis zárthelyikre maximum 3×10 pont szerezhető, a nagy házi feladatra 20, ez összesen 130 pont. Ha a minimumkritériumok teljesülnek, a jegy nem lehet rosszabb elégségesnél. A felkészülést egyéni szorgalmi feladatok is segítik, melyek megoldása nem kötelező.
A jelenlét és a laborgyakorlatokon írt beugrók nem pótolhatóak.
A kis zárthelyik félév közbeni pótlását az teszi lehetővé, hogy páronként mindig a jobban sikerült számít. Az egyik kis zárthelyi pótlására a pótlási héten is biztosítunk lehetőséget, különeljárási díj megfizetése mellett.
Nagy zárthelyi pótlására a pótlási héten van lehetőség. A két nagy zárthelyi összevontan javítható vagy pótolható, ilyen esetben az új pontszám kétszerese számít az eredeti pontszámok összege helyett. Második pótlási lehetőség a vizsgaidőszakban különeljárási díj megfizetése mellett egyszer biztosított.
A nagy házi feladat pótlólagos beadására csak a szorgalmi időszak végéig (utolsó tanítási napon, 12.00 óráig), van mód, azon túl a nagy házi feladat nem adható be. Pótlás esetén különeljárási díj fizetendő. Javítani csak előzőleg már elfogadott megoldást lehet.
- Elektronikus óravázlat (fóliasor) a tantárgy honlapján
- N. Wirth: Algoritmusok + adatstruktúrák = programok, Műszaki Könyvkiadó, 1982
- B.W. Kernigham, D.M. Ritchie: A C programozási nyelv, Műszaki Könyvkiadó, 1996