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

Oktató: 
Kurzus típus: 
Elmélet
Nyelv: 
magyar
Félév: 
2018/19/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 a pontszám 20%-ának 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 az alg.progfel@gmail.com címre csatolmányként kell elküldeni, külön fájlban a Python programkódot, és ha van, külön fájlban az adatokat. 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. Ha Python3-ban oldja meg, a program nevének vége 3 legyen, példánkban 5KovacsJutka3.py. A levél tárgya 5. HF, az esetleges javításé 5. HF javítás legyen. 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 (2019-02-16 24:00)

1. Mintaillesztés

Határidő: 2019-02-16 szombat 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. Python 2 program esetén lehessen a programot
      python 1KovacsJutka.py szoveg.txt minta
      

      Python 3 program esetén pedig

      python3 1KovacsJutka3.py szoveg.txt minta
      

      módon indítani. Ekkor a program olvassa be a szoveg.txt szöveges fájl tartalmát, és keresse meg benne a minta minta első előfordulását. A parancssori argumentumok lekérdezhetőek a beépített sys.argv tömbben:

      import sys
      
      print('A fájl neve ' + sys.argv[1] + ', a keresett minta ' + sys.argv[2])
      

      (A sys.argv[0] értéke az éppen futtatott Python program neve.)

    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. Ha a programba bárhol – akár csak egy megjegyzésbe – ékezetes betűt írunk, akkor legyen a program első sora
      # -*- coding: utf-8 -*-
      

      Ezt majd a további feladatoknál se felejtsü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.
      Egyszerű keresés 2610 összehasonlítással, a találat helye: 2321
      Gyors keresés 270 összehasonlítással, a találat helye: 2321
      

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

      Egyszerű keresés 3652 összehasonlítással, nincs találat
      Gyors keresés 431 összehasonlítással, nincs találat
      
  • Ha Python2-ben egy print utasítás végére vesszőt teszünk, akkor a következő print utasítás eredménye ugyanabban a sorban folytatódik. Ugyanez Python3-ban az end opcióval érhető el, pl. print("Hello", end="").
  • Próbáljuk ki a programot az alább letölthető két szövegfájllal és a megadott mintákkal! Hogyan függ az összehasonlítások száma a bemenettől?
    Fájlnév Minta
    1.text overscrupulous
    1.text zombies
    2.text aaaaaaaaa
    2.text bbbbbbbbb
    2.text aaaaaaaab
    2.text aaaaaaaba