Algoritmuselmélet programozási feladatok (BMETE91AM47/T0)

Oktató: 
Kurzus típus: 
Elmélet
Nyelv: 
magyar
Félév: 
2019/20/2

A tárgy célja az Algoritmuselmélet című tárgy tematikájához kapcsolódó programozási feladatok megoldásán keresztül a hallgatók programozási képességeinek szinten tartása, és egyúttal az algoritmusok működésének, hatékonyságának, bonyolultságának... jobb megértése.

A tárgy 1 kredites, ami összesen 30 óra, azaz heti 2-3 óra programozási munka elvégzését kívánja. Olyan feladatokat igyekszünk adni, melyek érdekesek lesznek mindenki számára, és amelyek megoldása sok haszonnal fog járni. A feladatok száma 12, összpontszáma 60. Követelmény a feladatok legalább 80%-ának határidőre való leadása (illetve 1 pont elvesztése mellett legföljebb 1 héttel későbbi, késedelmes leadása) és a feladatokra kapható maximális összpontszám legalább 50%-ának elérése. A hibásan megoldott feladat az eredmény kihirdetése utáni 1 héten belül javítható. A feladatok megoldását egyelőre az alg.progfel@gmail.com címre csatolmányként kell elküldeni (ez várhatóan változni fog a szemeszter köben), külön fájlban a Python programkódot. A programfájl neve a feladat sorszámával kezdődjön, folytatásul a hallgató neve legyen szóközök nélkül, pl. Kovács Jutka 5-dik házi feladatát 5KovacsJutka.py, adatfájlját 5adatKovacsJutka.txt néven küldje el. Minden feladatot Python3-ban kell megoldani! Minden házi feladat kísérő levelébe az alábbi szöveget kell írni:


E programot magam kódoltam, nem másoltam vagy írtam át más kódját, és nem adtam át másnak!
Aláírás saját névvel

Az, hogy a program kódját mindenkinek magának kell beírnia, programkódot átadnia, mástól kérnie és elfogadnia, letöltenie és átírnia nem szabad, nem zárja ki az együtt gondolkodás vagy a segítségkérés lehetőségét! Konzultáció is kérhető, személyes is.

Tartalomjegyzék

  1. Mintaillesztés (2020-02-23 24:00)
  2. Nemdeterminisztikus véges automata (2020-03-03 24:00)
  3. Szélességi keresés (2020-03-08 24:00)

1. Mintaillesztés

Határidő: 2020-02-23 vasárnap 24:00

  • Írjunk programot az órán tanult két mintaillesztési algoritmus összehasonlítására!
    1. A program a bemenetet parancssori argumentumok formájában kapja meg, a következőképp indítható:
      python3 1KovacsJutka.py szoveg.txt minta
      

      Ekkor a program olvassa be a szoveg.txt szöveges fájl tartalmát, és keresse meg benne a minta első előfordulását. A parancssori argumentumok lekérdezhetőek a beépített sys.argv tömbben, ami a következő 3-soros mintaprogrammal kipróbálható:

      import sys
      
      print('Fájlnév: {0}, minta: {1}.'.format(sys.argv[1], sys.argv[2]))
      print("E program neve {0:2} betű".format(len(sys.argv[0]))) # {:2} is ugyanaz
      

      A sys.argv[0] értéke az éppen futtatott Python program neve, len() függvény annak hosszát adja meg, a {0:2} azt jelenti, hogy a format függvény 0-dik argumentumát kell beírni 2 karakternyi helyre. Ezt a lehetőséget használjuk majd a program megírásakor is.

    2. Fájl beolvasására javasoljuk a Python fájlkezelő függvényeit, például az alábbi módon:
      f = open(fajlnev, 'r')
      szoveg = f.read().strip()
      f.close()
      

      A strip() metódus segítségével levághatjuk az esetlegesen előforduló sorvége karaktereket és felesleges szóközöket a bemenet elejéről és végéről.

    3. Python3-ban a programba bárhol írhatunk ékezetes betűket is, de a fájl utf-8 kódolású legyen. Lehetnek a változónevekben is ékezetes karakterek, de ezt inkább kerüljük el!
    4. Nem kell ellenőrizni, hogy a megadott szövegfájl létezik-e, vagy hogy valóban szöveget tartalmaz-e. A minta mindig legfeljebb olyan hosszú, mint a szöveg. A szöveg csak az angol ábécé a–z kisbetűit és szóközöket tartalmaz. A mintában csak kisbetűk vannak, szóköz nincs. Az algoritmusoknak megfelelően a programban csak a szöveg és a minta egy-egy karakterének összehasonlítása megengedett, de a Python sztringkezelő függvényeinek használata nem, kivéve a len() függvényt.
    5. Futtassuk le az egyszerű mintaillesztő algoritmust és a gyorskeresést (quick search) a megadott szöveggel és mintával. A program írja ki, hogy előfordul-e a minta a szövegben, és hány összehasonlítást végeztünk az első előfordulás megkereséséig. A keresések számára 5 karakter helyet biztosítsunk, a találat helyére 4 karaktert a formázott kimenetben.
      Lassú:  3260 összehasonlítás, találat helye: 3568
      Gyors:   397 összehasonlítás, találat helye: 3568
      

      Akkor is adjuk meg az összehasonlítások számát, ha a minta nem fordul elő a szövegben:

      Lassú:  5239 összehasonlítás, nincs találat
      Gyors:   768 összehasonlítás, nincs találat
      
  • Python3-ban az end="..." opcióval érhető el, hogy a print() függvény ne egy új-sor-karakterrel fejezze be a kiírást, hanem az opcióban megadott karakterlánccal, így a következő print() hívás kimenete ugyanabban a sorban folytatódik. Például print("szöveg", end=" ") kiírja a szöveget, szóközt tesz a végére, és a következő print() hívás kimenetét ott folytatja.
  • Próbáljuk ki a programot az alább letölthető két szövegfájllal és a megadott mintákkal! (Tesztelési fázisban természetesen érdemes saját text fájlokkal és mintákkal kísérletezni.)
    Fájlnév Minta
    1.text overscrupulous
    1.text zombies
    2.text aaaaaaaaa
    2.text bbbbbbbbb
    2.text aaaaaaaab
    2.text aaaaaaaba

2. Nemdeterminisztikus véges automata

Határidő: 2020-03-03 24:00

  • Az automata.py fájlban megadtunk egy programot, ami egy egyszerű nemdeterminisztikus véges automata futását szimulálja.
    1. A programot a
      python3 automata.py szo
      	

      paranccsal futtathatjuk, ahol a szo a felismerni kívánt szó.

    2. A program a Python beépített halmazkezelő függvényeit használja, hogy a nemdeterminisztikus véges automata számítási fájában aktuálisan elérhető állapotokat számon tartsa.
    3. Rajzoljuk le az automatát, és magyarázzuk meg saját szavainkkal: (1) hogyan szimulálja a program a működését, (2) milyen nyelvet ismer fel az automata? (A kísérőlevélben csak ez utóbbi két kérdésre kell válaszolni, a rajzot nem kell mellékelni.)
  • Módosítsuk az automata leírását az automata.py fájlban
    # Itt kezdődik az automata leírása:
        

    és

    # Idáig tart az automata leírása.
    

    sorok között úgy, hogy a program épp azon szavakat fogadja el, melyek páros sok a betűt tartalmaznak, vagy tartalmazzák az algel karaktersorozatot (vagy akár mind a kettőt)! Például az 'aaalgelbbb' és 'asdaefaa' szavakat elfogadja, az 'aaalgbb' szót nem.

3. Szélességi keresés

Határidő: 2020-03-08 24:00

  • A Kombinatorika és gráfelmélet 1. tárgyból megismert szélességi keresés algoritmussal megtalálhatunk egy lehető legkevesebb élből álló utat egy gráfban két adott csúcs között. A feladat ennek az algoritmusnak a beprogramozása.
  • Az algoritmus bemenete egy irányított egyszerű gráf, amit a következő módon adunk meg egy szöveges (.text) fájlban:
    1. A fájl első sorában az \(N\), \(M\), \(S\) és \(T\) természetes számok találhatóak szóközökkel elválasztva.
      • A \(\vec{G} = (V, \vec{E})\) irányított egyszerű gráf csúcsai a \(V = \{0, 1, 2, \ldots, N-1\}\) számok.
      • Az élek száma \(\left| \vec{E} \right| = M\).
      • Az \(S \in V\) csúcsból szeretnénk egy legkevesebb élből álló utat keresni a \(T \in V\) csúcsba (\(S \ne T\)).
    2. A fájl további \(M\) sora rendre \(U_i\), \(V_i\) számpárokat tartalmaz. Egy ilyen számpár megfelel egy \((U_i, V_i) \in \vec{E}\) élnek. Egy él csak egyszer szerepel a fájlban.
    3. A program, ha létezik út az \(S\) és \(T\) csúcsok között, akkor az \(S\) csúccsal kezdve sorban megadja annak csúcsait a \(T\) csúcsig. Ha nincs út, akkor kiírja, hogy „Nem létezik út!”.
  • Segítségképp megadjuk a graf.py fájlban a gráfot beolvasó és a megtalált utat kiíró függvényt, így csak magát a keresést kell megvalósítani az utat_keres függvényben.
    1. A függvény első, graf paramétere a gráf éllistás ábrázolása. Az éllistát egy szótárral (dictionary) adjuk meg, melyben minden csúcshoz egy lista tartozik. A lista elemei a kimenő éleken elérhető csúcsok. Például az alábbi fájlban leírt gráfhoz
      6 8 2 5
      1 0
      2 1
      3 2
      1 3
      0 5
      2 4
      4 5
      4 3
      	

      tartozó éllista

      graf = {0: [5], 1: [0, 3], 2: [1, 4], 3: [2], 4: [5, 3], 5: []}
      	
    2. A honnan paraméter az út első, \(S\) csúcsát, míg a hova paraméter az út utolsó, \(T\) csúcsát adja meg.
    3. A megoldáshoz felhasználható az utat_kiolvas függvény, ami egy (nem feltétlenül teljes) szélességi fából kiolvas egy utat a honnan és hova csúcsok között. A szélességi fát a szulo szótárban kell megadni, ahol az egyes csúcsokhoz rendelt érték a szülőjük azonosítója a szélességi fában. Például
      szulo = {1: 2, 4: 2, 0: 1, 3: 1, 5: 4}
      honnan = 2
      hova = 5
      	

      esetén egy legrövidebb út [2, 4, 5].

    4. Az algoritmus megvalósításánál nem szükséges az éleket fa-, előre-, vissza- és keresztélekre bontani, mivel ezek nélkül is kiolvasható egy legrövidebb út. Az egész gráfot sem kell bejárni, elég akkora részét, hogy meg lehessen találni egy legrövidebb utat.
    5. Várakozási sor megvalósítására alkalmasak a beépített listák append és pop(0) függvényei, de ki lehet próbálni a Python 3 queue modulját is.
  • Próbáljuk ki az elkészült programot a graf1.text és graf2.text bemenetekre, de teszteljük más, saját készítésű teszbemeneteken is!