Algoritmus

A Programozás Wiki wikiből

Definíció[szerkesztés]

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[szerkesztés]

Hatékonyság[szerkesztés]

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

Lépésszám[szerkesztés]

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[szerkesztés]

Folyamatábrák[szerkesztés]

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.


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: FAszekvencia.PNGa nyilak irányában felsorolt egymás utáni tevékenységek alkotják.
  • Egyágú, FAegyagu szelekcio.PNG illetve kétágú FAketagu szelekcio.PNG szelekció: döntés-csomópont segítségével oldjuk meg.
  • Előltesztelő FAeloltesztelo.PNG és hátultesztelő FAhatultesztelo.PNG ciklus pascalban.

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

Struktogram[szerkesztés]

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[szerkeszté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
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