1. Algoritmusok alapjai
Algoritmus fogalma: Jól meghatározott utasítások véges folyamata, amelynek bemenete egy bizonyos érték vagy értékhalmaz, és a amely létrehoz valamilyen értéket vagy értékhalmazt kimenetként.
Algoritmus készítésének lépései:
- A folyamatokat elemi lépésekre bontjuk
- Figyelembe vesszük az összes felmerülő lehetőséget
- Ügyelünk, hogy algoritmusunk véges sok lépésben véget érjen
Példa:
1. Válaszd ki a pizzát!
2. Tárcsázd az étterem számát!
3. Ha nem veszik fel/foglalt rakd le és várj 5 percet, majd ismételd meg a 2. pontot!
4. Várd meg a futárt!
5. Fizesd ki a pizzát!
Vezérlési szerkezetek:
- Szekvencia: Egy utasítást közvetlenül egy másik után végzünk el.
- Elágazás: Adott (legalább) 2 darab feltétel-program páros. A teljesülő feltételhez tartozó programrész (utasítások) végrehajtása.
- Ciklus: Megadott feltétel teljesülése esetén egy programrész (ciklusmag) többszöri végrehajtása.
Algoritmus leíró eszközök:
Blokkdiagram: Teendők és kérdések összekötése nyilakkal.
Szekvenciára és elágazásra van jelölés, ellenben ciklust csak a kettő kombinálásával tudunk jelölni!
Hátrányai:
- Nyilak és vonalak kesze-kusza rendszere
- Teljesen ad-hoc elrendezésű, két ugyanolyan algoritmus leírása a rajzolótól függően lehet teljesen más elrendezésű is
Struktogram: Teendők és kérdések strukturáltan kötött, mindíg téglalap alakú képi reprezentációja.
Szekvencia: 
Feltétel: 
Ciklus: 
Hátrányai:
- Nehezen módosítható
- Az elkészítése és értelmezése néha bonyolult és nehézkes
Pszeudokód: Teendők és kérdések között kifejezésekkel való szöveges leírása, nagy mértékben hasonlít a programnyelvek felépítéséhez.
Szekvencia:
Utasítás1
Utasítás2
Utasítás3
Feltétel:
Ha feltétel akkor
Utasítás1
különben
Utasítás2
Elágazás vége
Többirányú elágazás:
Elágazás
Feltétel1 esetén
Utasítás1
Feltétel2 esetén
Utasítás2
Feltétel3 esetén
Utasítás3
különben
Utasítás4
Elágazás vége
Elöltesztelős ciklus (akkor lépünk be és addig maradunk a ciklusban, amíg a feltétel igaz):
Ciklus amíg feltétel
Utasítás
Ciklus vége
Hátultesztelős ciklus (addig maradunk a ciklusban, amíg a feltétel igaz. Ez mindenképpen lefut egyszer!):
Ciklus
Utasítás
Ciklus amíg feltétel
Számlálós ciklus (a ciklusváltozó(i) érté minden ciklusban inkrementálódik, vagy dekrementálódik amíg i értéke meghaladja i1 értékét):
Ciklus i<-i0-tól i1-ig
Utasítás
Ciklus Vége
Algoritmusok hatékonyságának jellemzése:
Algoritmus lépésszáma:
- Egy algoritmus lépésszáma alatt az értjük, hogy hány elemi műveletet kell végrehajtani adott bemenet mellet.
- Egy algoritmus futási ideje függ az algoritmust megvalósító programtól, programozási nyelvtől, számítógéptől stb..
- Az algoritmuselméletben a futási időt a lépésszámmal jellemezzük.
Futási idő analízisének fajtái:
- Legrosszabb eset analízis: Maximális futási idő, amely az algoritmus futásához maximum szükséges.
- Átlagos eset analízis: A várható futási idő, amely az algoritmus futásához szükséges.
- Legjobb futási idő: Nem ad releváns eredményt a program futásáról.
Nagy ordó jelölés:
f(x) és g(x) egyváltozós függvények.
f(x) = O(g(x))
akkor és csak akkor, ha léteznek olyan M és x0 pozitív valós számok, hogy minden x > x0 esetén |f(x)| <= M*|g(x)|
Felhasznált Irodalom: Sergyán Szabolcs – Programozás I – 1. előadás diasor
Kommentek
Powered by Facebook Comments