Algoritmus

Definíció

Egy folyamat pontos és részletes leírása véges számú lépésben.

A gyakorlati életben használt algoritmusok véges számú lépések sorozataként vannak kifejezve, de az általános definícó nem követeli meg a végességet (pl. nemdetermininsztikus algoritmusok).

Algoritmusok vizsgálata

Hatékonyság

A hatékonyságot a lépésszám és a memóriaigény határozza meg.

Lépésszám

Lépésszám alatt az algoritmus által megtett lépések számát értjük a bemenet hosszának függvényében.

Példa: Egy számítógép <math>$10^10 \frac{lépés}{perc}$</math> sebességgel működik. ...

Algoritmusleíró eszközök

Folyamatábrák

A folyamatábra (flowchart) segítségével a program dinamikus viselkedését, "folyamatát" részletekbe menően ábrázolni tudjuk. E jelölésrendszer szabad kezet ad bármilyen folyamat ábrázolásában, így a strukturálatlan algoritmusokat is könnyűszerrel lerajzolhatjuk. A szabad kéz természetesen nem minden esetben jelent előnyt, hiszen tudjuk, hogy a "nagy szabadság könnyen káoszt okozhat".

T valamilyen tevékenységet, utasítást jelöl, F egy feltételt, a program folyását nyilak mutatják.

• Tevékenység-csomópont: A tevékenységet téglalappal jelöljük, melybe beírjuk a nevét. A tevékenység-csomóponton áthaladva a tevékenység végrehajtódik.
• Döntés-csomópont: Hozzá érkezve az F feltételtől függően a vezérlés az igaz vagy a hamis ágon folytatódik.
• Gyűjtő-csomópont: A nyilak az algoritmus végrehajtása során összefuthatnak. A gyűjtő-csomóponton áthaladva a végrehajtás ugyanazzal a tevékenységgel folytatódik, függetlenül attól, mi történt a csomópont előtt. A gyűjtő-csomóponton való áthaladás mindig egyértelmű. A csomópont kis karikája elhagyható.
• Részletezés: A részletezéssel jelölt tevékenység nem elemi tevékenység, az egy külön folyamatábrán kifejtésre kerül.
• Program eleje: Tulajdonképpen a program kezdetét jelöljük vele.
• Program vége: A program végét jelöljük így.
• Adatbevitel: Adatbekérésre szolgáló jelölési mód.
• Adatkiírás: Adatok ki íratását reprezentáló jelölés.
• Növekményes ciklus: A növekményes ciklus előállítható az első három elem segítségével. E jelölés csak ábrázolási könnyebbség. A v jelentése : változó, illetve a ... -ra kerül a kezdeti, illetve a vég érték.
• Kapcsolódási pont: Akkor használjuk, ha - helyhiány miatt - ábránkat egy másik lapon folytatjuk.

• Folyamatábrák
• 

  Tevékenység-csomópont.

• 

  Döntés-csomópont.

• 

  Gyűjtő-csomópont.

• 

  Részletezés.

• 

  Program eleje.

• 

  Program vége.

• 

  Adatbevitel.

• 

  Adatkiírás.

• 

  Növekményes ciklus.

• 

  Kapcsolódási pont.

Most nézzük meg, hogyan építhetjük fel a különböző struktúrákat folyamatábra segítségével.

• Szekvencia: a nyilak irányában felsorolt egymás utáni tevékenységek alkotják.
• Egyágú, illetve kétágú szelekció: döntés-csomópont segítségével oldjuk meg.
• Előltesztelő és hátultesztelő ciklus pascalban.

Végül nézzük meg, hogyan nézhet ki a "tea főzés" algoritmusa:

Struktogram

A struktogram egy strukturált programozási módszer, megalkotója Chapin ezért Chapin-chart-nak is hívják. E jelölés annyiban hasonlít a folyamatábrához, hogy a tervezés itt is kívülről befelé történik. Sajnos ahogy a struktúrában lejjebb megyünk, úgy egyre kevesebb hely marad tevékenységeink leírásához. (foly.köv)

Mondatszerű leírás

E pszeudokód lényege, hogy a programot mondatszerű elemekből építjük fel. Annyiban tér el a folyamatos magyar írástól, hogy itt be kell tartanunk bizonyos szabályokat. Ugyanis a struktúrák képzésére megállapodás szerinti formákat és szavakat használunk. Nézzük az alapelemeket:

• Bevitel, kivitel:

 Be:...felsorolás...[megszorítások]
 Ki:...felsorolás...[kiírási formák]

• Szekvencia:

 Tevékenység1
 Tevékenység2
 Tevékenység3

Egy sorba írt tevékenységeket kettőspont választja el:

 Tevékenység1 : Tevékenység2 : Tevékenység3

• Szelekciók:

Egyágú szelekció: Ha a Feltétel teljesül, akkor Tevékenység(ek) végrehajtásra kerül(nek), egyébként nem. A program az Elágazás vége után folytatódik. Itt az Elágazás vége el is hagyható.

 Ha Feltétel akkor
   Tevékenység(ek)
 Elágazás vége

Kétágú szelekció: Ha a Feltétel teljesül, akkor Tevékenység(ek)1 kerül(nek) végrehajtásra, egyébként Tevékenység(ek)2. Mindkét esetben a program az Elágazás vége után folytatódik.

 Ha Feltétel akkor
   Tevékenység(ek)1
 Egyébként
   Tevékenység(ek)2
 Elágazás vége

Többágú szelekció: Az i. Feltétel teljesülése esetén az i. Tevékenység(ek) kerülnek végrehajtásra. Ha egyik feltétel sem teljesül, akkor az Egyéb esetben ágra kerül a vezérlés. Minden esetben a program az Elágazás vége után folytatódik.

 Elágazás
   Feltétel1 esetén Tevékenység(ek)1
   Feltétel2 esetén Tevékenység(ek)2
   ...
   FeltételN esetén Tevékenység(ek)N
   Egyéb esetben Tevékenység(ek)N+1
 Elágazás vége

• Ciklusok:

Elöltesztelő ciklus:

 Ciklus amíg Feltétel1
   Tevékenység(ek)1
 Ciklus vége

Hátul tesztelő ciklus: Belépési feltétel megfogalmazása esetén.

 Ciklus
   Tevékenység(ek)
 amíg Feltétel
 Ciklus vége

Kilépési feltétel megfogalmazása esetén.

 Ciklus
   Tevékenység(ek)
 mígnem Feltétel
 Ciklus vége

Növekményes (számláló) ciklus:

 Ciklusváltozó = ...tól ...-ig
   Tevékenység(ek)
 Ciklus vége

• Program, eljárás, illetve függvény leírása:

Program:

 Program:
   Tevékenység(ek)
 Program vége

Eljárás:

 Eljárás Eljárásnév (Formális paraméterlista):
   Tevékenység(ek)
 Eljárás vége

Függvény:

 Függvény Függvénynév (Formális paraméterlista): Típus
   Tevékenység(ek)
   Függvénynév := Kifejezés
 Függvény vége