Programozási ismeretek

Tematika

1. Alapfogalmak

1.1. Számítási probléma

Feladat, amely szerint bizonyos bemenő (input) adatok alapján olyan kimenő (output) adatokat kell kiszámítani, melyek meghatározott kapcsolatban állnak a bemenő adatokkal.

Speciális esetek:

Optimalizálási probléma
Olyan probléma, ahol valamilyen feltételek szerinti minimális vagy maximális értéket kell megkeresni.
Eldöntési probléma
Olyan probléma, ahol az output adat egy logikai érték (igaz vagy hamis).

Példák:

INT_MUL - Egész számok szorzása
Adott két egész szám.
Számítsuk ki a szorzatukat.
INT_DIV - Egész számok osztása
Adott két egész szám.
Számítsuk ki a hányadosukat.
INT_DIV_MOD - Egész számok maradékos osztása
Adott két egész szám.
Számítsuk ki a hányadosukat és az osztás maradékát.
INT_DIV-D - Egész számok oszthatósága
Adott két egész szám.
Igaz-e, hogy az első szám osztható maradék nélkül a másodikkal?
LNKO - Legnagyobb közös osztó kiszámítása
Adott két pozitív egész szám.
Számítsuk ki a legnagyobb közös osztójukat.
TSP - Utazó ügynök probléma
Adott egy térkép (városok, a köztük vezető utak és azok hossza).
Adjunk meg egy minimális hosszúságú körutat, vagyis egy olyan utvonalat, amely minden várost pontosan egyszer érint és az ilyenek közül a lehető legrövidebb.
TSP-D - Utazó ügynök probléma - eldöntési változat
Adott egy térkép (városok, a köztük vezető utak és azok hossza) és egy távolság.
Létezik-e olyan körút, amely minden várost egyszer érint és nem hosszabb a megadott távolságnál?
3-COLORING - 3-színezési probléma
Adott egy földrész politikai térképe (terület és a benne húzódó országhatárok).
Ki lehet-e színezni a térképeket három színnel úgy, hogy a szomszédos országok különböző színűek legyenek?
(Ha két szomszédos országot azonos színűre festünk, akkor nehéz látni, hol húzódik közöttük a határ.)
FACTOR - Egész számok prímtényezős felbontása
Adott egy pozitív egész szám.
Adjuk meg a prímtényezős felbontását.
PRIME - Prímtesztelés
Adott egy pozitív egész szám.
Igaz-e, hogy prímszám?

1.2. Algoritmus

Valamely számítási probléma megoldására szolgáló módszer véges leírása.

1.3. Program

Valamely programozási nyelven leírt algoritmus.

2. Kiszámíthatóság

A kiszámíthatóság elmélete azzal foglalkozik, hogy mely számítási problémákat lehet algoritmussal megoldani és melyeket nem. Ugyancsak a kiszámíthatóság témakörébe tartozik a különböző számítási modellek vizsgálata. Két számítási modellt ismertetünk röviden: az úgynevezett L programozási nyelvet és a Turing-gép modellt.

2.1. Az L programozási nyelv

Input változók: X1, X2, ... (végtelen sok)
Segéd változók: Z1, Z2, ... (végtelen sok)
Output változó: Y
Minden változó értéke egy tetszőleges (bármilyen nagy) nemnegatív egész szám lehet.
Címkék: L1, L2, ... (végtelen sok)
L-nyelvű program: Az alábbi alakú utasítások véges sorozata (a programban az utasításokat egymás alá írjuk és mindegyik utasítás előtt állhat egy címke is):

V = V + 1
Növeli 1-gyel a V változó értékét. A program végrehajtása a sorrendben következő utasításnál folytatódik.
V = V - 1
Csökkenti 1-gyel a V változó értékét. Ha V értéke nulla volt, akkor nulla marad (mert a változókban nem lehet negatív számot tárolni). A program végrehajtása a sorrendben következő utasításnál folytatódik.
if V != 0 goto L
Ha a V változó értéke nem nulla, akkor a program végrehajtása az L címkével megjelölt utasításnál folytatódik, különben a sorrendben következő utasítás kerül végrehajtásra. Ha nem létezik L címkével megjelölt utasítás vagy nincs sorrendben következő utasítás (ez a program utolsó sora), akkor a program megáll. Ha egynél több L címkével megjelölt utasítás is van a programban, akkor ezek közül az elsőnél folytatódik a végrehajtás.

L-nyelvű program futtatása: Az X1, ..., Xn input változókba betöltjük az input adatokat, az összes többi változóba 0-t töltünk, majd elindítjuk a programot az első utasításnál. Ha a program megáll, akkor a számítás eredménye az Y változó értéke a megállás pillanatában.

Példák L-nyelvű programra

 X1 = X1 + 1
L1:X1 = X1 - 1
 Y = Y + 1
 if X1 != 0 goto L1

Makro utasítások

További példák:

  1. Változó nullázása.
  2. Adott szám betöltése változóba.
  3. Összeadás.
  4. Kivonás.
  5. Szorzás kettővel.
  6. Szorzás.

2.2. Turing-gépek

Lásd Wikipédia.

2.3. Számítási modellek ekvivalenciája

A Church-Turing tézis szerint tetszőleges P számítási problémára az alábbi állítások ekvivalensek:

  1. P megoldására létezik algoritmus.
  2. P megoldható L nyelvű programmal.
  3. P megoldható Turing-géppel.

2.4. L-nyelvű programok kódolása nemnegatív egész számokkal

2.5. Megoldhatatlan problémák

Léteznek algoritmikusan megoldhatatlan számítási problémák. Például az alábbi eldöntési probléma megoldhatatlan:

A megállási probléma
Adott két nemnegatív egész szám, p és x.
Döntsük el, hogy a p kódú L nyelvű program véges lépésben megáll-e az x inputon.

Tegyük fel ugyanis, hogy a megállási probléma algoritmikusan megoldható. Akkor a Church-Turing tézis szerint megoldható L-nyelvű programmal. Legyen H egy olyan L-nyelvű program, ami megoldja a megállási problémát. Tekintsük az alábbi P programot:

 X2 = X1
 H
L:if Y != 0 goto L

Legyen p a fenti P program számkódja. Kérdés: megáll-e a P program a p inputon? Kövessük végig a P program működését úgy, hogy kezdetben az X1 változóba a p számot töltjük. Azt látjuk, hogy a H program X1 = p és X2 = p kezdeti értékekkel fut le, ami azt jelenti, hogy megválaszolja a Megáll-e a P program a p inputon? kérdést.

Tegyük fel, hogy a P program megáll a p inputon. Akkor a H program az 1 értéket tölti az Y változóba, ami azt jelenti, hogy az L címkével megjelölt if utasítás fog a végtelenségig ismétlődni, vagyis a P program nem áll meg a p inputon - ellentmondás.

Ugyancsak ellentmondást kapunk, ha feltesszük, hogy a P program nem áll meg a p inputon, hiszen ekkor a H program a 0 értéket tölti az Y változóba, ezért az L címkével megjelölt if utasítás feltétele nem teljesül, tehát a P program megáll a p inputon.

Ez az ellentmondásos helyzet csak abból adódhat, hogy a kezdeti feltevésünk, miszerint a megállási probléma megoldható L-nyelvű programmal, hamis.

3. Számítási bonyolultság

Determinisztikus tár- és időigény fogalma.

3.1. Polinomiális Church tézis

Tetszőleges P számítási problémára az alábbi állítások ekvivalensek:

  1. P gyakorlatilag megoldható.
  2. P megoldható polinom időigényű determinisztikus Turing-géppel.

3.2. Eldöntési problémák bonyolultsági osztályai

Példák: palindrómák felismerése, prímtesztelés, 3-színezhetőség

A P, NP és co-NP bonyolultsági osztályok.

NP-teljes problémák.

3.3. Mire jók a nehezen megoldható problémák?

A nyilvános kulcsú titkosítás alapelve.

Az RSA kódolás (titkosítás)

A leginkább elterjedt nyilvános kulcsú titkosítási módszer, melyet 1978-ban talált fel három matematikus: Ron Rivest, Adi Shamir és Leonard Adleman.

Az algoritmus leírása:
RSA eljárás - Wikipédia
RSA leírás (angol) és JAVA nyelvű megvalósítás

Felhasználási lehetőségek:

  1. Titkosított üzenetek küldése.
  2. Dokumentumok aláírása.

3.4. A Turing-gépnél gyorsabb számítási modellek

DNS számítógép

Viszonylag nagy méretű NP-teljes feladatok gyors megoldása.
Leonard Adleman: Hamilton-kör keresés (egyszerűsített utazó ügynök probléma) megoldása.
DNA computing - Wikipedia

Kvantum számítógép

NP-teljes problémák determinisztikus polinom időben történő megoldását ígéri, de a gyakorlati megvalósítás még nagyon kezdeti stádiumban van.
Quantum computer - Wikipedia

4. A program életútja

  1. Specifikáció (9%)
  2. Elemzés (1%)
  3. Tervezés (25%)
  4. Kódolás (20%)
  5. Tesztelés és hibakeresés (35%)
  6. Dokumentálás (10%)
  7. Karbantartás

4.1. Specifikáció

A programozási feladat pontos meghatározása.
A megrendelő és a programozó részletesen megbeszéli és általában írásban (szerződésben) is rögzíti, hogy mit kell tudnia a készítendő programnak.

4.2. Elemzés

Megoldható-e a feladat? Ha igen, milyen eszközökkel?

4.3. Tervezés

Az adatszerkezetek és algoritmusok tervezése.
Algoritmus-leíró eszközök:

4.4. Kódolás

A program megírása a választott programozási nyelven.

Fontos, hogy olvasható, könnyen értelmezhető legyen a program. Ezt segíti elő:

  1. az indentálás (beljebbírás),
  2. megjegyzések elhelyezése a kódban (JAVA: dokumentációs megjegyzések),
  3. a "beszédes", de nem túl hosszú változó- és függvénynevek használata.

4.5. Tesztelés és hibakeresés

Tesztelés: A program minden inputon a specifikáció szerinti outputot adja-e?

Hibakeresés: Ha teszteléskor hibát találunk, akkor azt a program melyik pontján kell javítani?
Adott input esetén a hiba helyének felderítésére szolgáló hatékony módszer a nyomkövetés, melynek során lépésről-lépésre hajtjuk végre a programot és közben folyamatosan figyeljük, ellenőrizzük a változók értékét.

Ha hibát találunk, akkor a program hibás részét javítjuk (Kódolás). A tesztelést, hibakeresést és javítást addig folytatjuk, amíg már nem találunk több hibát.

4.6. Dokumentálás

Felhasználói dokumentáció: A program használói számára írja le a program kezelését, működését.

Fejlesztői dokumentáció: Ha később módosítani vagy javítani kell a programot, akkor segíti a programozó munkáját.

4.7. Karbantartás

A felhasználók által talált hibák javítása.

Ha új igény merül fel, akkor újra végig kell járni a teljes életciklust az első lépéstől kezdve.

Verziószámok használata.

Ajánlott irodalom

Martin D. Davis, Ron Sigal, Elaine J. Weyuker
Computability, complexity, and languages : fundamentals of theoretical computer science - 2. ed. - Boston etc. : Academic P., 1994.

Michael R. Garey, David S. Johnson
Computers and intractability : a guide to the theory of NP-completeness - 22. print. - New York, N. Y. : Freeman, 2000.

Christos H. Papadimitriou
Számítási bonyolultság; Bp., Novadat, 1999. (1-3. és 9. fejezet)

List of important publications in theoretical computer science

Angster Erzsébet
Objektumorientált tervezés és programozás; Bp., Kör Bt., 2004.

Valid XHTML 1.0 Strict