Algoritmuselmélet programozási feladatok (BMETE91AM47/T§ - 2017/18/2) | Budapesti Műszaki és Gazdaságtudományi Egyetem

Oktató:

Kurzus típus:

Elmélet

Nyelv:

magyar

Félév:

2017/18/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. Kérdéseikkel keressék a tárgy demonstrátorát a szokemarton3 kukac gmail pont com címen.

Eredmények

Az eredmények táblázata itt van.

1. Mintaillesztés

Határidő: 2018-02-18 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. Nem kell ellenőrizni, hogy a megadott fá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, a Python sztringkezelő függvényeinek használata nem, kivéve a len() függvényt.
4. 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.
```
Egyszeru algoritmus:
A minta elofordul a szovegben a 2563. helyen.
2760 osszehasonlitast vegeztunk.

Gyorskereses:
A minta elofordul a szovegben a 2563. helyen.
247 osszehasonlitast vegeztunk.
```
  Akkor is adjuk meg az összehasonlítások számát, ha a minta nem fordul elő a szövegben:
```
Egyszeru algoritmus:
A minta nem fordul elo a szovegben.
2009 osszehasonlitast vegeztunk.

Gyorskereses:
A minta nem fordul elo a szovegben.
201 osszehasonlitast vegeztunk.
```
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

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ő: 2018-02-25 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
```
python automata.py szo
```
  vagy 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 kezdodik az automata leirasa:
```
és
```
# Idaig tart az automata leirasa.
```
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)!

3. Szélességi keresés

Határidő: 2018-03-06 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ó éllísta
```
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 2 Queue vagy 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!

4. Bal-levezetések keresése

Határidő: 2018-03-12 24:00

A szélességi keresés arra is alkalmas, hogy egy környezetfüggetlen nyelvtanban levezetést adjuk egy szóhoz.
1. Tekintsük a $G = (V, \Sigma, S, P)$ CF nyelvtant, és képezzük a $\vec{G} = ((V \cup \Sigma)^*, \vec{E})$ irányított gráfot, melynek csúcsai a terminális és nemterminális szimbólumokból képzett sztringek. Ennek a gráfnak megszámlálhatóan végtelen csúcsa van, de ezek közül elég lesz véges sokat bejárni, hogy egy levezetést találjunk.
2. A $\vec{G}$ gráf akkor és csakis akkor tartalmazza az $(\alpha, \beta)$ élt, ha az $\alpha \in (V \cup \Sigma)^*$ sztringből egy bal-levezetési lépéssel (az $\alpha$ sztringben legelőször előforduló nemterminális szimbólumra egy levezetési lépés alkalmazásával) elérhető a $\beta \in (V \cup \Sigma)^*$ sztring. Formálisan, \begin{equation*} (\alpha, \beta) \in \vec{E} \Longleftrightarrow \exists w \in \Sigma^* \; \exists \gamma, \delta \in (V \cup \Sigma)^* \; \exists A \in V \colon (A \rightarrow \delta) \in P, \alpha = wA\gamma \textrm{ és } \beta = w\delta\gamma. \end{equation*}
3. Ebben a gráfban a $w \in L(G)$ szó bal-levezetései épp a $\sigma \leadsto w$ utak, ahol $\sigma = \textit{"S"} \in (V \cup \Sigma)^*$. Az út minden éle megfelel valamelyik szabály alkalmazásának a legbaloldalibb nemterminális szimbólumra. A feladatban egy ilyen utat szeretnénk megkeresni.
A cf.py fájlban megadtuk a levezetést kereső program vázát. A program egyetlen parancssori argumentumot vár, a levezetendő szót. A megtalált levezetést a standard kimenetre írja.
A programban egy egyszerű módszerrel oldottuk meg a terminális és nemterminális szimbólumok különválasztását: az angol ábécé minden A–Z nagybetűjét lehetséges nemterminális szimbólumnak tekintjük, míg az összes többi karaktert terminálisnak.
1. A CF nyelvtant a Nyelvtan osztállyal reprezentáljuk, amely kezdőszimbólumot a kezdovaltozo konstruktor argumentumban kapja meg. Egészítsük ki az add_szabaly metódust úgy, hogy a megadott bal és jobb oldalú levezetési szabályt hozzávegye a nyelvtan szabályaihoz. Ha szükséges, módosítsuk az __init__ konstruktort úgy, hogy létrehozza a szabályok tárolására alkalmas adatstruktúrát.
2. A levezet metódus a paraméterül kapott szó egy bal-levezetését adja vissza egy listában. Ha biztosan nincs ilyen, akkor a False értékkel tér vissza. Ehhez segítségül hívja az előző feladatban bemutatott szélességi keresést, amit a _szelessegi_kereses privát metódus valósít meg. Mivel a gráf most nem véges, nem állíthatjuk elő az éllistáját. Ehelyett a _rakovetkezo függvényt használjuk, ami egy adott csucs sztringhez előállítja az onnan kimenő élen elérhető csúcsait a gráfnak.
  Egészítsük ki a _rakovetkezo metódust úgy, hogy a paraméterül kapott csucs sztringből megengedett bal-levezetési lépéssel kapható szavak listáját adja vissza! Például, ha a nyelvtan
  
  \begin{equation*} S \to aSB \mid bSA \mid \epsilon, \quad A \to aA \mid \epsilon, \quad B \to bB \mid \epsilon, \end{equation*}
  
  akkor
```
self._rakovetkezo('aSbbB') == ['aaSbbbB', 'abSAbbB', 'abbB']
```
3. Próbáljuk ki a programot, és keressünk levezetést néhány általunk választott szóhoz! Milyen nyelvet határoz meg a cf.py fájlban megadott nyelvtan? Mi történik, ha olyan szót adunk meg a programnak, ami nincs benne a nyelvben?
A szélességi keresés során a $\vec{G}$ gráf nagyon sok csúcsát előállítjuk és bejárjuk, mire meg tudunk találni egy utat az általunk kívánt szóhoz. Gondolkozzunk el azon, hogy hogy lehetne a gráfnak csak kisebb részét bejárni, és ezzel hatékonyabbá tenni a programot (ezt a részt már nem kell leprogramozni)!

5. Hatékony tanúsítvány

Határidő: 2018-03-18 24:00

Az algoritmuselmélet tárgyhoz kapcsolódó Turing gépek jegyzetben is szerepel, hogy a Hamilton-körrel rendelkező gráfok nyelvére $\textrm{HAM} \in \textrm{NP}$ teljesül. A bizonyítást a tanú-tétel segítségével végezhetjük el úgy, hogy egy – a Hamilton-kör létezését mutató – hatékony tanúsítványt megadunk. Ennek alapötlete, hogy egy adott gráfhoz megadunk egy számsorozatot, ami a feltételezett Hamilton-kör csúcsait jelöli egy körnek megfelelő sorrendben. Ha a számsorozatban minden csúcs pontosan egyszer fordul elő, valamint a számsorozatban egymásutáni csúcsok, illetve az első és az utolsó csúcs szomszédosak a gráfban, akkor a tanusítvány bizonyítja a Hamilton-kör létezését.
A feladat egy olyan Python program írása, mely a jegyzetben vázolt hatékony tanúsítvány algoritmusát valósítja meg: eldönti egy adott (gráf, számsorozat) párról, hogy az adott számsorozat egy Hamilton-kört reprezentál-e a gráfban.
A program a bemenetet parancssori argumentumok formájában kapja meg. Python 2 program esetén lehessen a programot
```
python 5KovacsJutka.py graf.text tanu.text
```
Python 3 program esetén pedig
```
python3 5KovacsJutka3.py graf.text tanu.text
```
módon indítani.
Az első bemenet (a példában graf.text) egy irányítatlan 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$ természetes számok találhatóak szóközökkel elválasztva, ahol
  - a $G = (V, E)$ egyszerű gráf csúcsainak halmaza $V = \{0, 1, 2, \ldots, N-1\}$,
  - az élek száma $\left| E \right| = M$.
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 E$ irányítatlan élnek. Egy él csak egyszer szerepel a fájlban.
3. A bemenet feldolgozására javasoljuk a 3. feladat gráf beolvasó függvényének módosítását. Figyeljünk arra, hogy most a fájl első sorában nem szerepelnek az $S$ és $T$ csúcsok. Mivel a gráf élei nincsenek irányítva, érdemes lehet az éleket mindkét végpontjuk éllistájába felvenni.
A program második bemenete egy egész számokból álló számsor. A program feladata eldönteni, hogy a számsor tanú-e arra, hogy a gráfban található Hamilton-kör.
Amennyiben a tanú megfelelő, a
```
Tanu
```
amennyiben nem, akkor a
```
NEM tanu
```
szöveget írjuk ki.
Próbáljuk ki a programot a graf.text gráffal és az alábbi (tanújelölt) bemenetekkel:
Fájlnév Elvárt kimenet
t1.text Tanu
t2.text NEM tanu
t3.text NEM tanu
t4.text NEM tanu
t5.text Tanu
t6.text NEM tanu
t7.text NEM tanu

Fájlnév	Elvárt kimenet
t1.text	Tanu
t2.text	NEM tanu
t3.text	NEM tanu
t4.text	NEM tanu
t5.text	Tanu
t6.text	NEM tanu
t7.text	NEM tanu

6. Euklideszi algoritmus

Határidő: 2018-03-27 24:00

Az euklideszi algoritmus segítségével két szám legnagyobb közös osztója hatékonyan meghatározható. Tudjuk, hogy ha $a, b \in \mathbb{Z}^+$ a bemeten kettes számrendszerben adott, akkor a bemenet hossza $O(\log a + \log b)$, az euklideszi algoritmus pedig $\mathop{\mathrm{lnko}}(a, b)$ értékét legfeljebb $O(\log a + \log b)$ lépésben meg tudja határozni.
Az euklideszi.py fájlban megadtunk egy olyan kódrészletet, ami a matplotlib Python csomag segítségével kirajzolja a $\log a + \log b$ függvény hőtérképét (heat map) az $(a, b)$ koordinátasíkon, úgy, hogy $a$ és $b$ értéke $1$ és $100$ közötti egész legyen. A hőtérkép a szivárvány színeivel jelzi a számok nagyságát, az ibolyakék a kicsi, a vörös a nagy számoknak felel meg, de a matplotlib csomag újabb verzióiban a színek csak a sárgáig változnak.
Módosítsuk a programot úgy, hogy bemutassa az euklideszi algoritmus futását! Jelenítsünk meg három hőtérképet, egymás mellett egy ablakban, az alábbiak valamelyikéhez hasonlóan (az eredmény a matplotlib verziójától függ):
$hoterkep.png$

$hoterkep1.png$

A hőtérképeken az alábbi függvények legyenek láthatóak:
1. Az első hőtérkép mutassa a $\log_2 a + \log_2 b$ függvényt, mint a kiadott kódban.
2. A második hőtérképen ábrázoljuk az euklideszi algoritmus lépésszámát az egyes $(a, b)$ párokon. Számoljuk meg, hány lépést tesz meg az euklideszi algoritmusban szereplő rekurzió, azaz hányszor végzünk maradékos osztást az $(a_i, b_i)$ párral, vagy döntünk a leállás mellet.
3. Végül a harmadik hőtérkép mutassa $\mathop{\mathrm{lnko}}(a, b)$ értékét.
Több ábra megjelenítéséhez használható a matplotlib subplot függvénye. Ennek argumentuma egy $nmk$ alakú szám, ami az ábra pozícióját határozza meg. Ennek jelentése: a rajzvásznat $n \times m$ részre osztjuk, és a továbbiakban ezek közül a $k$-adik részre rajzol. Így például a
```
plt.subplot(132)
    
```
hívás vízszintesen három részre osztja a vásznat, és a középső részre rajzolja a további plt hívások eredményeit.

7. Nyers erő

Határidő: 2018-04-15 24:00

Az NP-teljes problémák megoldásának egy lehetséges módszere a „nyers erő” alkalmazása. Ebben a megközelítésben generáljuk a bemenethez tartozó összes lehetséges tanút, és egyesével ellenőrizzük őket. Ha találunk egy jó tanút, akkor a bemenet benne van a vizsgált nyelvben, míg ha egyetlen generált tanú sem volt jó, akkor a bemenet biztosan nem eleme a nyelvnek. Természetesen ettől az eljárástól sem remélhetjük, hogy a feladatot polinom időben oldja meg.
A KLIKK nyelv az olyan $(G, k)$ párokból áll, ahol a $G$ egyszerű irányítatlan gráfban van pontosan $k$ elemű klikk (teljes részgráf). Arra, hogy $(G, k) \in {}$KLIKK, jó tanú egy $k$ elemű $K \subseteq V(G)$ klikk. Ha $|V(G)| = n$, akkor a $K$ halmazról $O(n^2)$ időben eldönthető, hogy minden $u, v \in K$ pontpár között van él a gráfban.
Készítsünk olyan programot, ami a parancssori argumentumként kapott fájlban leírt $(G, k)$ párról eldönti, hogy a KLIKK nyelvben van-e. Ha találtunk $k$ elemű klikket, akkor írjuk ki az elemeit a standard kimenetre. Ellenkező esetben jelezzük, hogy a gráfban nincs $k$ elemű klikk.
1. A klikk.py fájlban megadtuk a grafot_olvas függvényt, ami beolvassa a parancssori argumentumként megadott fájlból $G$ gráf éllistáját és a $k$ számot. A beolvasott fájl formátumát és a függvény visszatérési értékét a függvényhez tartozó docstring megjegyzésben dokumentáltuk.
2. Generáljuk a gráf $\{0, 1, \ldots, n - 1\}$ csúcsainak $k$ elemű kombinációit, és vizsgáljuk meg, hogy klikket alkotnak-e. Ha a $K$ kombináció klikk, akkor írjuk ki az elemeit a standard kimenetre, és állítsuk le a keresést. Ha egyetlen kombináció sem klikk, akkor jelezzük, hogy nem találtunk $k$ elemű klikket.
3. Segítségképp a kombinaciok függvényben megadtunk egy kódrészletet, amely az itertools csomag segítségével a standard kimenetre írja a $\{0, 1, \ldots, 9\}$ halmaz összes 3 elemű részhalmazát.
Próbáljuk ki a programot az alábbi fájlokkal! Azokhoz a bemenetekhez, melyek a KLIKK nyelvben vannak, megadtunk egy klikket is példaként a kimenetre. Természetesen más klikk is elfogadható jó tanúnak.
Fájl Klikk
klikk1.text 0 1 4 6
klikk2.text nincs
klikk3.text 1 2 4 13 14
klikk4.text nincs
klikk5.text 0 3 4 6 7
klikk6.text 0 3 4 6 16 24 27 37

Fájl	Klikk
klikk1.text	0 1 4 6
klikk2.text	nincs
klikk3.text	1 2 4 13 14
klikk4.text	nincs
klikk5.text	0 3 4 6 7
klikk6.text	0 3 4 6 16 24 27 37

8. Egészértékű lineáris programozás

Határidő: 2018-04-25 24:00

Az NP-teljes problémák megoldásának egy másik ismert módszere az, hogy a problémát visszavezetjük egy másik, jól ismert NP-teljes problémára. Ha a jól ismert problémára rendelkezésünkre áll egy hatékony heurisztikus megoldó, akkor általában jobb eredményt tudunk elérni, mint a nyers erővel.
A feladatban egészértékű lineáris programozás (EP) segítségével oldjuk meg az előző hétről ismerős KLIKK problémát. Az egészértékű lineáris programot a PuLP Python csomag segítségével oldjuk meg. A csomag a Python beépített pip csomagkezelőjével a
```
pip install pulp
    
```
paranccsal telepíthető.
A pulppelda.py fájlban megadtunk egy egyszerű példaprogramot, ami a \begin{align*} \max\, &x_0 + x_1,\\ \text{ahol } x_0, x_1 &\in \mathbb{Z},\\ x_0 &\ge 0, \\ x_1 &\ge 0, \\ 2 x_0 + x_1 &\le 10, \\ x_0 + 2 x_1 &\le 10 \end{align*}
egészértékű programozási feladat egy megoldását a standard kimenetre írja. Tanulmányozzuk a programot! A megértéshez segítséget nyújthat a PuLP csomag dokumentációja.
Készítsünk programot a KLIKK probléma megoldására!
1. Olvassuk be a probléma bemenetét, azaz a $G$ irányítatlan gráfot és a $k$ számot az előző feladatból megismert formátumú fájlból. A program az előző feladathoz hasonlóan a fájl nevét parancssori argumentumként fogja megkapni.
2. Fogalmazzuk meg a KLIKK problémát egészértékű programozási feladatként.
3. Programozzuk le az egészértékű programozási feladatot a PuLP csomaggal, és hívjuk meg rá a megoldót. Ügyeljünk arra, hogy mind a feladatnak, mind a feladatban szereplő változóknak egyedi szöveges nevet kell adni, mert ezekkel hivatkozik a probléma elemeire a PuLP, amikor átadja őket a külső megoldónak. Ha a változók nevei nem egyediek, akkor hibajelzést fogunk kapni.
4. Ha találtunk $k$ elemű klikket, akkor írjuk ki az elemeit is a standard kimenetre. Ellenkező esetben jelezzük, hogy a gráfban nincs $k$ elemű klikk. Ha a feladatot maximalizálási problémaként fogalmazzuk meg, akkor érdemes arra figyelni, hogy a PuLP a célfüggvény értékét nem egész, hanem lebegőpontos számként adja vissza. A lebegőpontos számábrázolás sajátosságai miatt érdemes lehet a célfüggvény értékét nem közvetlenül a $k$ egészhez, hanem egy kicsit nagyobb, például $k + 0.1$ számhoz hasonlítani, vagy összehasonlítás előtt egészre kerekíteni.
Futtassuk le a programot az előző feladatban kiadott bemenetekkel! Milyen esetben lett gyorsabb az egészértékű programozás, mint a nyers erő?

9. Ládapakolás

Határidő: 2018-04-29 24:00

A ládapakolás feladatban a bemeneten megadott $(s_i)_{i = 1}^n$, $(0 < s_i \le 1)$ súlyokról kell meghatározzuk, hogy minimálisan hány $1$ kapacitású ládába férnek el. A probléma NP-teljes, így hatékony megoldás (jelenlegi ismereteink szerint) nem áll rendelkezésre, ám számos közelítő algoritmus született rá. Ebben a feladatban néhány közelítő heurisztika vizsgálata lesz a cél.
A ladak.py fájlban megadtunk egy olyan keretprogramot, ami egy fix bemeneten vizsgál egy alsó korlátot és három közelítő algoritmust a ládapakolás problémára:
1. Az OPT értéke a tárgyak összsúlyának felső egészrésze, ami egy alsó korlát a szükséges ládák számára.
2. Az előadáson tanult FF algoritmus minden tárgyat az első olyan ládába teszi, ahol az elfér.
3. A szintén tanult FFD algoritmus hasonló az FF-hez, ám előbb csökkenő sorrendbe rendezi a tárgyakat.
4. A BF (best-fit) heurisztika minden tárgyat abba a ládába helyez el, ahol a legkevesebb szabad hely marad.
Módosítsuk a ladak.py fájlt és fejezzük be a program elkészítését!
1. Valósítsuk meg a first_fit_pakol függvényben az FF algoritmust.
2. Valósítsuk meg az ffd_pakol függvényben az FFD algoritmust. Ügyeljünk arra, hogy a Python a listákat referencia szerint adja át, így ha a súlyokat tartalmazó listát rendezzük, az a hívó által átadott listát közvetlenül módosítja. Ehelyett inkább dolgozzunk a lista egy másolatával.
3. A fix targyak lista helyett állítsunk elő (a program minden futtatásakor más) 1000 elemű, 0 és 1 közötti súlyokat tartalmazó listát, és hívjuk meg ezzel a pakoló függvényeket.
Futtassuk néhányszor a programot! Mit tapasztalunk, hogy működnek a közelítő algoritmusok a generált véletlen bemeneteken?

10. Akrobaták

Határidő: 2018-05-06 24:00

Cirkuszi akrobaták egymás vállára állva minél nagyobb tornyot szeretnének létrehozni (a toronyban minden szinten csak egy akrobata lesz). Esztétikai és gyakorlati szempontok miatt egy ember vállára csak olyan állhat, aki nála alacsonyabb és könnyebb is. Feladatunk, hogy meghatározzuk a lehetséges legtöbb emberből álló toronyban található emberek számát.
Az akrobata.py fájlban megadtunk egy példaprogramot, ami beolvassa az akrobatákat a parancssori argumentumban megadott nevű fájlból, majd magasság szerint nemnövekvő sorrendben kiírja őket a standard kimenetre. A fájl formátuma a következő:
1. A fájl első sorában egyetlen pozitív egész szám szerepel, az akrobaták $N$ darabszáma.
2. A következő $N$ sorban $M_i$ $S_i$ számpárok szerepelnek. A fájl $i + 1$. sorában szereplő számpár rendre az $i$. akrobata magasságát és súlyát adja meg.
3. Az akrobaták beolvasásáról az akrobatakat_beolvas függvény gondoskodik, mely az Akrobata osztály példányait tartalmazó listával tér vissza. Az akrobaták rendelkeznek az azonosito, magassag és suly tulajdonságokkal, valamint egy raallhat metódussal, mely megadja, hogy egy akrobata ráállhat-e egy másikra.
Dinamikus programozás segítségével határozzuk meg az akrobatákból a szabályok szerint építhető legtöbb emberből álló toronyban található emberek számát! Az elkészült programot próbáljuk ki az alábbi bemeneteken, melyekhez megadtuk azt is, hány emberből áll a legtöbb embert tartalmazó torony:
Bemenet Maximális torony
cirkusz1.text 2
cirkusz2.text 3
cirkusz3.text 1
cirkusz4.text 100
cirkusz5.text 15
cirkusz6.text 37

Bemenet	Maximális torony
cirkusz1.text	2
cirkusz2.text	3
cirkusz3.text	1
cirkusz4.text	100
cirkusz5.text	15
cirkusz6.text	37

11. Intervallumok uniója

Határidő: 2018-05-13 24:00

Adott a számegyenesen $n$ zárt intervallum, $[A_1, B_1], [A_2, B_2], \ldots [A_N, B_N]$, ahol $A_i$ és $B_i$ természetes számok. Szeretnénk meghatározni az intervallumok összhosszát, vagyis az $\bigcup_{i = 1}^N [A_i, B_i]$ halmazban levő természetes számok darabszámát.
Az intervallum.py fájlban megadtunk egy példaprogramot, ami beolvassa az intervallumokat a parancssori argumentumban megadott nevű fájlból. A fájl formátuma a következő:
1. Az első sorban egyetlen természetes szám található, az intervallumok $N$ száma.
2. A következő $N$ sorban szereplő $A_i$ $B_i$ számpárok határozzák meg az intervallumok határait, ahol $0 < A_i < B_i$.
3. Az intervallumokat_olvas függvény a megadott fájlból Intervallum objektumok listáját olvassa be. Az Intervallum osztálynak két tulajdonsága van, a kezd kezdőpontja és veg végpontja.
Egészítsük ki az osszhossz függvényt úgy, hogy kiszámítsa az intervallumok összhosszát! Törekedjünk a hatékony, $O(N \log N)$ lépésszámú megvalósításra.
Próbáljuk ki a programot az alábbi bemeneteken. A hatékony, $O(N \log N)$ lépésszámú algoritmus az alábbi bemenetek mindegyikén lefut néhány másodperc alatt. A bemenetek mellett megadtunk az intervallumok összhosszát is.
Bemenet Összhossz
interv1.text 9
interv2.text 596
interv3.text 6541
interv4.text 94581377
interv5.text 632741470

Bemenet	Összhossz
interv1.text	9
interv2.text	596
interv3.text	6541
interv4.text	94581377
interv5.text	632741470

12. Bináris keresőfa

Határidő: 2018-05-20 24:00

Ebben a feladatban egy bináris keresőfa adatszerkezetet fogunk készíteni. A binfa.py programban megadtuk a keresőfa implementációjának egy részét.
1. A bináris fát a BinarisFa osztály reprezentálja. A fa gyökere a gyoker tagváltozóban van tárolva. Ha a fa üres, ennek értéke None, egyébként a gyökér a FaCsucs osztály egy példánya.
2. A csúcsok a FaCsucs osztály példányai. A bal és jobb tagváltozók értéke vagy None, ha az adott gyerek nem létezik, vagy a gyerekcsúcsot reprezentáló FaCsucs példány.
3. A fához tartozó műveletek a BinarisFa osztály beszur, keres, szintszam és preorder_nyomtat metódusai. Ezek ellenőrzik, hogy van-e a fának gyökere, majd továbbhívnak a FaCsucs osztály megfelelő, rekurzióval megvalósított metódusaira.
4. A beszur és keres műveletek közös rekurzív része a FaCsucs csucsot_keres metódusa. Ez bejárja a fát a paraméterül kapott értéket keresve, és visszaadja azt a csúcsot, ahol a bejárás elakad. Ez vagy az a csúcs, amelyik tartalmazza a keresett értéket, vagy ha az érték nincs a fában, akkor az a csúcs, melynek az új értéket tartalmazó csúcs a közvetlen gyereke kell legyen.
5. A főprogram egész számokat olvas be parancssori argumentumként megadott nevű fájlból, minden sorból egyet, majd beszúrja őket a bináris fába. Ezután preorder sorrendben a standard kimenetre írja a fában tárolt értékeket, és kiszámítja a fa szintjeinek a számát.
Egészítsük ki a binfa.py programot az implementáció hiányzó részével!
1. A BinarisFa beszur metódusában szúrjuk be a kapott értéket a fába. Ehhez segítségül hívhatjuk a FaCucs csucsot_keres metódusát, amely azt a csúcsot adja vissza, amely vagy tartalmazza a keresett értéket, vagy a keresett értéket a csúcs közvetlen gyerekeként kell beszúrni. Ennek a metódusnak a használatát mutatja be a BinarisFa keres metódusa is. Ügyeljünk arra, hogy a beszúrás üres bináris fán is működjön, illetve olyanon is, amely már tartalmazza a beszúrni kívánt értéket. Az utóbbi esetben a beszúrás idempotens.
2. A FaCsucs preorder_nyomtat metódusában írjuk ki a fa csúcsait rekurzió segítségével preorder sorrendben a standard kimenetre.
3. A FaCsucs szintszam metódusában szintén rekurzió segítségével határozzuk meg a fa szintjeinek a számát.
Az elkészült programot próbáljuk ki a binfa1.text fájlban található bemenettel! Más bemenetekre hogyan viselkedik a program?

Budapesti Műszaki és Gazdaságtudományi Egyetem ALGEBRA ÉS GEOMETRIA TANSZÉK
Algebra Csoport

Algoritmuselmélet programozási feladatok (BMETE91AM47/T§ - 2017/18/2)