Algoritmus, algoritmus tervezése, moduláris programozás

Algoritmus (eljárás, módszer, recept): Egy probléma megoldásához vezető véges számú cselekvéssor, melyet véges sokszor megismételve a probléma megoldását kapjuk.
Az algoritmusoknak azért van nagy szerepük a számítástechnikában, mert számítógépes programokkal csakis olyan feladat oldható meg, mely megoldása felbontható véges számú lépésre, azaz algoritmizálható.
Program: Elemi utasítások véges és logikus sorozata.

Az algoritmus leglényegesebb tulajdonságai, ill. a vele szemben támasztott követelmények

• Lépésekből (elemi tevékenységekből) áll.
• Minden lépésnek egyértelműen végrehajthatónak kell lennie.
• Mindig van tárgy, amit itt adatnak hívunk (absztrakció: csak a feladat végrehajtásához szükséges adatokat vesszük figyelembe).
• A végrehajtandó utasításoknak célja van, végrehajtás során változnak az adatok bizonyos tulajdonságai.
• Az algoritmusnak általában vannak bemenő adatai.
• Legalább egy kimenő adatot produkálnia kell. (kommunikáció a külvilággal)
• Véges számú lépésben el kell vezessen a megoldáshoz.
• Legyen hatékony!
• Legyen felhasználóbarát!

Az algoritmus tervezése

Egy jó algoritmus még a legegyszerűbb program írásánál is komoly segítséget jelenthet. Egy számítógépen megoldandó feladat felvetődése pillanatában máris erős a csábítás, hogy az ember leüljön a számítógép elé, és már gépeljük is az utasításokat. Miután kész vagyunk a beírással, a fordító által jelzett hibákat több-kevesebb idő alatt kijavítjuk. Az ilyen összedobott program azonban a legritkább esetben működik helyesen. És akkor elkezdődik a javítgatás. A program bizonyos adatokkal működik, másokkal nem. Ha valamit kijavítunk, helyette valami másik probléma jön elő. Előbb-utóbb úgy összekeveredünk, hogy már azt sem tudjuk, mi is volt a feladat tulajdonképpen. A toldozás-foltozás nem szerencsés módszer, megbízható programot kizárólag tervszerű programozással készíthetünk! Az algoritmus megtervezéséhez vezető első lépés a probléma körültekintő elemzése és megfogalmazása. A megoldási módszer keresése csak akkor kezdődhet el, ha a feladatot pontosan ismerjük. Ahhoz, hogy egyértelmű legyen, mi is a feladat, a feladat leírását írásban rögzíteni kell! A feladat leírását feladat specifikációnak is szokás nevezni. Az algoritmust csak a feladat pontos megfogalmazása után próbáljuk elkészíteni, mégpedig programnyelvtől függetlenül.
Az algoritmus tervezésének alapja a részekre bontás, az ún. dekompozíció (elemekre, összetevőkre való felbontás, szétbontás). Mivel nagyobb feladatok esetén a problémát egyszerre nem tudjuk megoldani, azt kisebb részekre kell bontani. A részeket meg kell oldani, majd a megoldott részeket össze kell állítani. A lebontás illetve összeállítás során a következő kérdések merülnek fel:

• Hogyan bontsuk részekre a nagy feladatot?
• A részekre bontás után hogyan fogjunk hozzá a megoldáshoz?
• Hogy történjen a megoldott részfeladatok összerakása?

A részekre bontásnál két irányzatot különböztetünk meg:

• Felülről lefelé (top-down módszer): A megoldást felülről lefelé fokozatosan, lépésenként finomítjuk és a kis feladatokat csak a végső fázisokban oldjuk meg.
• Lentről fölfelé (bottom-up módszer): Először megoldjuk a kisebb feladatokat, és aztán gondolkodunk az összeállítás struktúráján. Ez az alulról felfelé tervezés.

Moduláris programozás

Az emberek egy bizonyos bonyolultság után a feladatokat már nem tudják átlátni. Ilyenkor gyakran az ösztöneinkre hagyatkoznak. A programokat azonban ösztönből nem lehet megírni. A moduláris programozás azt jelenti, hogy a problémát olyan részfeladatokra bontjuk, melyeknek a bonyolultsága már nem okoz gondot, amit már egy modulban meg tud írni egy programozó, azaz csökkentjük a probléma bonyolultságát. Ha több ember dolgozik egy munkán, akkor is részekre kell fölosztani az elvégezendő feladatot. A részeknek az összekapcsolódását meg kell tervezni. A részek közötti együttműködési felületet interfésznek hívják, az ilyenfajta programozási módszert pedig moduláris programozásnak.

Strukturált program, mondatszerű leírás

Strukturált program

A cél az, hogy a teljes feladat olyan kis feladatelemekre legyen felosztva, amelyek egymással nincsenek átfedésben, egymáshoz meghatározott logika szerint kapcsolódnak és mindegyik megoldható valamilyen elemi struktúra, elemi programséma követésével.
Bármely algoritmus a következő elemekből építhető föl:

• Szekvencia (rákövetkezés, egymásutániság): Egymás után végrehajtandó tevékenységek sorozata.
• Szelekció (elágazás, választás): Választás megadott tevékenységek közül.
• Iteráció (ismétlődés, ciklus): Megadott tevékenységek ismételt, többszöri végrehajtása.
• Feltétel nélküli ugrás (goto): Vezérlés átadása a program egy megadott pontjára.

A csak szekvenciákból, szelekciókból és iterációkból építkező programot strukturált programnak nevezzük.

A strukturált programozásban a ciklusból való kiugrás fogalma ismeretlen. Ebből következik, hogy a program minden szekvenciájának - és így az egész programnak is - egyetlen belépési és egyetlen kilépési pontja van, ennélfogva a program lényegesen áttekinthetőbb.
Az ilyen programozás során a teljes feladatot olyan kis feladatelemekre osztjuk, melyek egymással nincsenek átfedésben, egymáshoz meghatározott logika szerint kapcsolódnak és mindegyik megoldható valamilyen elemi struktúra, elemi programséma követésével.

Mondatszerű leírás

Egy bonyolultabb algoritmust nem lehet fejben megtervezni, ahhoz eszközök kellenek. Olyan eszközre van szükség, mely általánosan elfogadott, azaz mások is ismerik és használják is. Az algoritmusok áttekinthető formában való leírásához számtalan ún. algoritmus leíró eszköz ismert. Ilyenek pl. a következők:

• mondatszerű leírás,
• folyamatábra,
• struktogram

Sokszor a mondatszerű leírást szokták pszeudokódként (="álkód") is emlegetni, holott van köztük némi különbség. A mondtaszerű leírás ugyanis sokkal kevésbé kötött forma, mint a pszeudokód. A továbbiakban a pszeudokóddal foglalkozom, mert az a programozók körében jóval elterjedtebb, s igazi határ nincs is a mondatszerű leírás és a pszeudokód között.
Ez a leírási mód nagyon közel van a magas szintű programozási nyelvek által használt kódokhoz, de egyetlen programozási nyelvvel sem azonos a formája. Átmenetet képez a mondatszerű leírás és a kód (=programszöveg, forrásprogram) között. Tehát ez az emberi nyelvhez közel álló, szabályokkal kötött mondatszerű leírást jelent.

utasítás		általános alak
Az algoritmust nyitó utasítás		algoritmus neve:
SZEKVENCIÁLISstruktúrák	bemeneti struktúra	BE: változók listája vagy adottak: változók listája
	kimeneti struktúra	KI: változók listája vagy eredmény: változók listája
	értékadó művelet	változónév: kifejezés
Az algoritmust lezáró utasítás		Vége

Példa_1:

Téglalap:
Be: a,b
k := 2*(a+b)
t := a*b
Eredmény: "A kerület: ", k
Eredmény: "A terület: ", t
Vége

---

utasítás		általános alak
SZELEKCIÓS struktúrák	HA ... AKKOR típusú struktúra	HA feltétel(ek), akkor       utasítássor HA vége
	HA ... AKKOR ... KÜLÖNBEN típusú struktúra	HA feltétel(ek), akkor       utasítássor1 KÜLÖNBEN       utasítássor2 HA vége

Példa_2:

Téglalap:
Be a,b
Ha (a>0) és (b>0), akkor
 k:=2*(a+b)
 t:=a*b
 Eredmény "A kerület: ", k
 Eredmény "A terület: ", t
Különben
 Eredmény "Hibás oldalhossz!"
Ha vége
Vége

---

utasítás		általános alak
ITERÁCIÓS struktúrák	elöltesztelő ciklus (amíg)	Amíg feltétel(ek), végezd el       utasítássor Amíg vége
	hátultesztelő ciklus (ismételd)	Ismételd       utasítássor Ameddig feltétel(ek)
	számlálós ciklus	Minden i −> kezdőérték, végérték, lépésköz végezd el       utasítássor Minden vége

Példa_3:

Első_100_páros_szám:
Minden i:=2; i<200; i:=i+2 végezd el
 Ki: i
Minden vége

Szokás a fenti példát az alábbi módon leírni:

Első_100_páros_szám:
Ciklus i:=2-től 200-ig, lépésköz:=2
 Ki: i
Ciklus vége

Természetesen a fentebb leírtak nem kőbevésett szabályok (talán ez a jó a pszeudó kódokban???), nagyon sokféleképpen meg lehet még ezen módszerrel is adni egy algoritmus leírását.

Struktogram, folymatábra

Struktorgram

Adatbevitel

Kiiratás

Értékadás

Elágazás

Folyamatábra

Start

Ez a kezdőszimbólum, pontosan egy van belőle minden folyamatábrában.

Stop

Ez a zárószimbólum. Elvileg csak egy van belőle, de megengedett, hogy akár többet is használjunk.

Adatbevitel

A változók értékeit kérjük be vele. (Általában billentyűzetről.)

Kiiratás

A megadott kifejezés(ek) eredményét írhatjuk ki vele. (Általában a monitorra.)

Értékadás

Egy változó értékének beállítása.

Elágazás

Ha feltétel igaz, akkor az "i" ágon folytatódik tovább az algoritmus, ha hamis, akkor a "h" ágon. Mindig két ág van. A rombuszban egy egyértelműen eldönthető logikai kifejezésnek kell szerepelnie!

Jellemzői:

1. Minden folyamatábra tartalmaz pontosan egy START és legalább egy STOP szimbólumot.
2. Minden vonal irányított.
3. Minden pontba el lehet jutni a START-ból, és minden pontból el lehet jutni legalább egy STOP-ba.

---

Ez egy vicces, ugyanakkor hibás folymatábra. Miért?

Nézzük meg egy példában, mi a külömbség a programozási nyelvek között

Pascal

program hello;
begin
    writeln('Helló világ!');
end.

Java

public class hello
{  
        public static void main(String args[])
        {
           System.out.println("Helló világ!");
        }
}

C

#include <stdio.h>

int main(void) { 

    printf("Helló, világ!\n"); 

    return 0; 

}

C++

#include <iostream>
using namespace std;
void main()
{
    cout << "Hello World!" << endl;
}

C#

public class hello
{
   public static void Main()
   {
      System.Console.WriteLine("Helló világ!");
   }
}