2018. február 5., hétfő

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ásalgoritmus neve:
SZEKVENCIÁLISstruktúrákbemeneti struktúraBE: változók listája
vagy
adottak: változók listája
kimeneti struktúraKI: változók listája
vagy
eredmény: változók listája
értékadó műveletváltozónév: kifejezés
Az algoritmust lezáró utasításVé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ákHA ... AKKOR típusú struktúraHA feltétel(ek), akkor
      utasítássor
HA vége
HA ... AKKOR ... KÜLÖNBEN típusú struktúraHA 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ákelö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 ciklusMinden 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!");
   }
}

Nincsenek megjegyzések:

Megjegyzés küldése