Informatika2-2013/Eloadas

A MathWikiből
(Változatok közti eltérés)
23. sor: 23. sor:
 
* A feladat: Adott két pozitív egész szám, <math>m</math> és <math>n</math>, keresendő legnagyobb közös osztójuk.
 
* A feladat: Adott két pozitív egész szám, <math>m</math> és <math>n</math>, keresendő legnagyobb közös osztójuk.
 
* Az Euklideszi algoritmus lépései:
 
* Az Euklideszi algoritmus lépései:
   * E0 Ha <math>m<n</math> , akkor cseréljük meg a két számot: <math> m \leftrightarrow n</math>
+
 
   * E1 Osszuk el <math>m</math>-et <math>n</math>-nel, legyen a maradék <math>r</math>.
+
   ** E0 Ha <math>m<n</math> , akkor cseréljük meg a két számot: <math> m \leftrightarrow n</math>
   * E2 Ha <math>r=0</math>, akkor az algoritmus véget ért, az eredmény <math>n</math>.
+
   ** E1 Osszuk el <math>m</math>-et <math>n</math>-nel, legyen a maradék <math>r</math>.
   * E3 Legyen <math> m \leftarrow n</math> és <math> n \leftarrow r</math> és menjünk vissza E1 lépésre.
+
   ** E2 Ha <math>r=0</math>, akkor az algoritmus véget ért, az eredmény <math>n</math>.
 +
   ** E3 Legyen <math> m \leftarrow n</math> és <math> n \leftarrow r</math> és menjünk vissza E1 lépésre.
  
 
=== Programozás, programozási nyelvek===
 
=== Programozás, programozási nyelvek===

A lap 2013. február 17., 11:50-kori változata

Bevezetés

Gyakran egy matematikai probléma megoldását, vagy a megoldás egy lépését számítógép segítségével határozhatjuk meg. A probléma megfogalmazása után először a megoldáshoz vezető algoritmust kell megadnunk. Ezután következik az algoritmus implementálása, beprogramozása a számítógépbe.

Algoritmusok

Az algoritmusnak nincs egységesen elfogadott definíciója, így az alábbi megfogalmazás sem definícióként értendő.

Algoritmus: (Cormen, T., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms) Bármely jól meghatározott számítási eljárás, amelynek bemenete egy bizonyos érték vagy értékhalmaz, és amely létrehoz valamilyen értéket vagy értékhalmazt kimenetként.

Egy algoritmust sokféleképp jellemezhetünk. Knuth könyvében az alábbi, 5 fontos tulajdonságot emeli ki: (Knuth, D. E. - The Art of Computer Programming)

  • Végesség: Az algoritmus véges sok lépés után befejeződik.
  • Meghatározottság: Az algoritmus minden lépése pontosan definiált.
  • Bemenet (Input): Az algoritmus igényelhet olyan értékhalmazt (adatokat), amiket elindítása előtt meg kell adnunk.
  • Kimenet (Output): Az algoritmushoz tartozhat olyan kimeneti értékhalmaz, mely meghatározott kapcsolatban van a bemenettel.
  • Elvégezhetőség: Elvárjuk, hogy az algoritmust végre lehessen hajtani

Számítási módszernek nevezünk egy olyan eljárást, mely a végességet leszámítva teljesíti a fenti feltételeket.

Egy példa algoritmusra - Euklideszi algoritmus:

  • A feladat: Adott két pozitív egész szám, m és n, keresendő legnagyobb közös osztójuk.
  • Az Euklideszi algoritmus lépései:
 ** E0 Ha m < n , akkor cseréljük meg a két számot:  m \leftrightarrow n
 ** E1 Osszuk el m-et n-nel, legyen a maradék r.
 ** E2 Ha r = 0, akkor az algoritmus véget ért, az eredmény n.
 ** E3 Legyen  m \leftarrow n és  n \leftarrow r és menjünk vissza E1 lépésre.

Programozás, programozási nyelvek

Célunk algoritmusok beprogramozása a számítógépbe. Ehhez először a számítógép fogalmát kell megértenünk. A mai számítógépek Neumann János 1946-ban kidolgozott elvei szerint működnek. Felépítésük az ún. Neumann és Harvard architektúrák felépítését követi. Leegyszerűsített felépítésük a következő:

  • Processzor (CPU): beolvassa a memóriából az utasításokat és az adatokat, az utasítások alapján műveleteket végez, az eredményt visszaírja a memóriába; valamint vezérli a perifériákat - adatokat olvas belőlük, és ír ki
  • Memória: általános tároló, mely utasításokat és adatokat tartalmaz
  • Perifériák: háttértárolók, beviteli eszközök, monitor, ...

Egy algoritmust programozási nyelv használatával adjuk meg a számítógépnek. Egy programozási nyelvvel képesek vagyunk vezérelni, utasítások sorozatát előírni a számítógép processzorának. Az egyes nyelvek között compiler-ek fordítják át az utasításokat. Gépi kódnak nevezzük azon nyelvet, mellyel a számítógép processzora közvetlenül vezérelhető.

Példák programozási nyelvekre:

Személyes eszközök