1 of 37

Bevezetés�2022.09.06

2 of 37

Kőrösi Gábor

SzTE TTIK, Informatikai Intézet, Számítógépes Algoritmusok és Mesterséges Intelligencia tanszék

​

kgabor@inf.u-szeged.hu

3 of 37

Miért járjunk gyakorlatra/előadásra?

    • 99 % érdektelen / 1% érdekes
    • 80% munka /szmélyes kapcsolatok

4 of 37

Követelmények

  • A gyakorlat „látogatása” nem kötelező
  • Két ZH, 2x50 pontért, Coospace,
  • Az előadás idejében
  • Utolsó héten javító / pótló (orvosi igazolás)

5 of 37

Követelmények

Ponthatárok :

0-50: elégtelen (1)

51-60: elégséges (2)

61-70: közepes (3)

71-85: jó (4)

86+ : jeles (5)

6 of 37

Követelmények

Pluszpontok szerezhetők…

Aktivitással

    • Válaszok a kérdésekre
    • Példák a következő órára
    • Stb.

Max. 10 pont

A minimumpontszámba (51) nem számítanak bele

7 of 37

Anyagok

Új algoritmusok

http://www.inf.u-szeged.hu/~rfarkas

Gelle Kitti korábbi jegyzete: 

http://www.inf.u-szeged.hu/~kgelle/?q=alga

Imreh Csanád példatára: 

http://www.inf.u-szeged.hu/~cimreh/feladatgyujt.pdf

Kőrösi Gábor korábbi jegyzete: 

http://www.inf.u-szeged.hu/~korosig/teach.html

​

​

​

8 of 37

Témakörök

1. Bevezetés – Tantárgy ismertetése, Kártyahúzás probléma

2. Algoritmusok futásidő elemzése

3. Oszd meg es uralkodj

4. Dinamikus programozás

5. Mohó algoritmusok

6. Adtaszerkezetek

7. Keresőfák

8. Hasító táblázatok

9. Elemi gráfalgoritmusok

9 of 37

Miért tanuljak algoritmusokat?

  • Algoritmikus gondolkodás!
    • Algoritmus eddig megoldatlan problémára?
    • Megfelelő algoritmusok és adatszerkezetek kiválasztása
    • Gondoljuk végig a helyességet és hatékonyságot!

10 of 37

Algoritmusok

Algoritmusnak nevezünk bármilyen jól definiált számítási eljárást, amely bemenetként bizonyos értéket vagy értékeket kap és kimenetként bizonyos értéket vagy értékeket állít elő.

11 of 37

Algoritmusok tervezése

  • Értsük meg mélyen a feladatot!
  • Nincs általános módszertan algoritmizálásra
  • A félév folyamán
    • megismerünk hasznos technikákat
    • látunk számtalan algoritmust különböző problémákra

ezek mintául szolgálhatnak a jövőben.

12 of 37

Algoritmusok elemzése

  • Helyesség

​

  • Hatékonyság:
    • előre megmondjuk, milyen erőforrásokra lesz szüksége az algoritmusnak
    • számítási idő, memória, sávszélesség

​

  • Cél: algoritmusok összehasonlítása

13 of 37

Feladat

14 of 37

Algoritmusok elemzése

1. Feladat

  • Adott a következő játék: egy magyar kártya pakliból kihúznak egy lapot.
  • Eldöntendő kérdésekkel kell kitaláljuk, hogy melyik a kihúzott lap.
  • Legkevesebb hány elöntendő kérdésből tudjuk biztosan megmondani, mely lapot húzta az illető?

15 of 37

Algoritmusok elemzése

Megoldás

  • A magyar kártya 32 lapból áll.
  • Ez 4 színből - tök, makk, piros, zöld - a színeken belül pedig a következőkből áll: 7, 8, 9, 10, alsó, felső, király, ász.

16 of 37

Algoritmusok elemzése

Legrosszabb megoldás

  • Ha végig kérdezzük sorban az összes lapot és épp az utolsót húzták ki, az 32 kérdés.
  • Ez a lehető legrosszabb verzió..

17 of 37

Algoritmusok elemzése

Legjobb (eset) megoldás

  • a legjobb eset az, amikor a elsőre kihúzzák

​

  • Ekkor csupán 1-et kell kérdeznünk.

18 of 37

Algoritmusok elemzése

Átlagos megoldás

  • ha nem akarjuk végig kérdezni az összes lapot egyenként, akkor érdemes a paklit elfelezgetni.

​

  • Ez által egyre jobban specifikálni a lapot.

19 of 37

Algoritmusok elemzése

Megoldás

  • Az első, ami szerint rendszerezhetünk pl. a 4 szín: tök, makk, piros, zöld.

20 of 37

Algoritmusok elemzése

Megoldás

  • 2 kérdést kell feltennünk (ne feledjük, csak eldönthető kérdések lehetnek!):
  • Tök vagy makk?
  • Ha igen a válasz, felezzük el ezt is: Tök?
  • Ha nem a válasz, a maradék két színt felezzük el: Piros?

21 of 37

Algoritmusok elemzése

Megoldás

  • Tudjuk a színt…
  • A harmadik kérdés tehát ez: Szám?

22 of 37

Algoritmusok elemzése

Megoldás

  • Ha már tudjuk, hogy szám vagy figura-e további 4 lap közül kell döntenünk.
  • Rákérdezünk egy tetszőleges két elemű részhalmazra és választól függően egy elemre

23 of 37

Algoritmusok elemzése

Megoldás

  • Ez így összesen 5 kérdés.
  • Ennél kevesebből nem tudjuk pontosan meghatározni a kihúzott lapot, viszont ennyi már épp elég hozzá.

24 of 37

Algoritmusok elemzése

Megoldás

Nézzünk meg egy példát: A kihúzott lapom a Piros Király.

25 of 37

Algoritmusok elemzése

-Ennél kevesebb kérdésből nem is lehet megcsinálni

- ha leírjuk a válaszokat (pl 0 a ,,nem” és 1 az ,,igen”) sorrendben, akkor

N kérdés után egy N-bites bináris stringet kapun.

26 of 37

Algoritmusok elemzése

- a cél, hogy ebből az N-bites stringből egyértelműen meg tudjuk mondani, hogy melyik lapról beszélünk.

27 of 37

Algoritmusok elemzése

- Ha ezt 4 kérdésből csináljuk,

akkor 24 = 16-féle stringet tudunk előállítani, ami kevesebb, mint a lapok száma (32)

- minimum 5 kérdés kell ahhoz, hogy biztosan meg tudjuk mondani. 25 = 32, tehát ez épp elég lesz.

28 of 37

Feladat

29 of 37

Algoritmusok elemzése

2. Feladat

Egy egyetemista a fesztiválon átbulizott éjszaka után elfelejti, hogy a kempingben hol is volt a sátra. A kempingben n sátorhely van, amelyek egy sorban helyezkednek el.

30 of 37

Algoritmusok elemzése

Az egyetemista csak akkor ismeri fel a sátrát, mikor másodszor is alaposan megnézi.

31 of 37

Algoritmusok elemzése

A következő stratégiát alkalmazza: először elmegy a kemping másik széléig, miközben minden sátor helyét megvizsgálja.

32 of 37

Algoritmusok elemzése

Majd mivel elsőre nem találja meg a sátrát, visszafordul, és újra megvizsgálja az összes sátor helyét, amíg rá nem lel a sajátjára.

33 of 37

Algoritmusok elemzése

Hányszor kell az egyetemistának vizsgálódnia a legjobb, a legrosszabb és az átlagos esetben?

34 of 37

Algoritmusok elemzése

Legjobb eset:

A sátor az n. helyen van, így végigmegy egyszer (ez n db sátor megvizsgálása)

majd amint visszafordul rá is lel a saját sátrára, mikor másodjára megnézi (+1). Összesen: n+1 sátor megnézése

35 of 37

Algoritmusok elemzése

Legrosszabb eset:

A sátor az 1. helyen van. Ekkor végig nézi egyszer az összes sátrat (n db sátor végig nézése) majd visszajön az elejéig teljesen (újabb n db sátor megnézése). Azaz 2n db sátrat néz meg.

36 of 37

Algoritmusok elemzése

Átlagos eset:

ha a sátor hátulról az i-edik helyen van, akkor elmegy a végére és i helyet jön

vissza. Tehát n + i sátor helyét kell megnéznie. Így az átlagos eset

37 of 37

Algoritmusok elemzése

Hogy jött ez ki

http://www.inf.u-szeged.hu/~kgelle/sites/default/files/upload/alga-gyak-01.pdf