Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 1. témakör
1. lecke: Bevezetés az algoritmusokbaMi az algoritmus, és miért fontos?
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
Mi az az algoritmus? Definiálhatjuk úgy, mint lépések
sorozatát egy feladat végrehajtásához. Lehet egy algoritmus az iskolából hazafelé vezető út, a sajtos melegszendvics készítése, vagy egy áru megkeresése a boltban. Az informatikában az algoritmus egy feladat végrehajtásához
szükséges programlépések sorozata. Az algoritmusok jelentik
a tudományt a számítástudományban. Azzal, hogy jó algoritmust választasz és azt a helyzethez illően alkalmazod,
érdekes és fontos programokat írhatsz. Nézzünk néhány híres algoritmust! Hogyan továbbítja az élő videót
a Google Hangouts ilyen gyorsan az Interneten? Audio és videó tömörítő algoritmusok
alkalmazásával. Hogyan találja meg a Google Maps a texasi Dallasból a floridai Orlandóba
vezető utat, hogy eljuthass a Disney Worldbe? Útvonalkereső algoritmust használ. Hogyan színezi be a Pixar egy karakter
háromdimenziós modelljét egy virtuális szoba fényforrása alapján? Képgeneráló eljárást használnak. Hogyan választja meg a Nasa,
hogy hogy rendezze el a napelemeket egy nemzetközi űrállomáson, és honnan tudja, mikor
kell átrendezni azokat? Optimalizáló és ütemező
eljárást alkalmaznak. Ezek az algoritmusok sokkal
összetettebbek a hétköznapi algoritmusoknál, mint amilyen a melegszendvics
készítése. De a lényeg ugyanaz, lépések sorozata egy feladat
elvégzéséhez. Ha már ismersz algoritmusokat, akkor erőfeszítést takaríthatsz meg, és gyorsabb programokat tudsz írni azzal, ha a megfelelő algoritmust használod. Például tegyük fel, hogy egy játékot írsz, és azt szeretnéd, hogy a játékos játszhasson a gép ellen. Vegyük például a dámajátékot. Programozók írtak egy olyan dámaprogramot, ami sosem veszít. Egy minimax kereső algoritmussal
navigáltak a lehetséges lépéseket leíró
hatalmas fán. Ha a játékod hasonlít a dámához, akkor használhatsz ezeken
a technikákon alapuló algoritmusokat. Ha nem, akkor annak tudatában, hogy
mik ezeknek az algoritmusoknak a korlátai, áttervezheted a játékodat, ha erős számítógépes
játékost szeretnél. Fontos azt is tudni, hogyan kell
új algoritmust tervezni, és hogyan kell elemezni a hibamentességet
és hatékonyságot. A biológia területén sorra készülnek
új algoritmusok azért, hogy új molekulákat tervezzenek, amikből gyógyszerek fejleszthetők. A fizika területén klímát
és időjárást szimuláló algoritmusokat készítenek. Más algoritmusok azt az óriási adattömeget
kutatják és elemzik, amit automatizált űrteleszkópok gyűjtenek
a csillagokról. Minden tudományterületen,
de még olyan weboldalakhoz is, mint például a Khan Academy,
hatékony algoritmusok kellenek ahhoz, hogy nagy adatbázisokat lehessen elemezni,
vagy nagyszámú döntés közül lehessen választani. Bármilyen terület is érdekel téged, új algoritmusok hatalmas számítási
potenciája fogható be olyan dolgok elvégzésére, amire
az embereknek szükségük van, és ami fontos nekik. Na most, nem minden algoritmus egyforma. Mitől jó egy algoritmus? A két legfontosabb kritérium az, hogy az adott problémát megoldja, és hogy a megoldás hatékony legyen. Legtöbbször azt szeretnénk, hogy
az algoritmusról tudjuk azt, hogy mindig jó eredményt ad. Viszont van úgy, hogy el tudunk fogadni
olyan algoritmust is, ami nem adja meg a pontos,
vagy a legjobb választ, ugyanis a tökéletes algoritmus bizonyos problémák esetén nagyon-nagyon hosszú időt venne igénybe. Például tegyük fel, hogy olyam programot
szeretnénk, ami megadja egy csomagkézbesítő teherautó számára a leghatékonyabb útvonalat, ami a raktárból indul, és oda érkezik
vissza. A program hetekig futna amíg végigvenne minden lehetőséget. De ha megelégszel egy olyan programmal, ami elég jó útvonalat ad, de talán nem a legjobbat, akkor az lehet, hogy másodpercek alatt
le tud futni. Van úgy, hogy az elég jó is jó. Hogyan mérhető egy algoritmus
hatékonysága? Lemérhetjük a kód futási idejét, de ez csak egy adott programozási nyelven egy adott gépen meghatározott inputtal futó adott implementációról adna információt. Ehelyett az informatikusok egy
aszimptotikus elemzésnek nevezett technikát alkalmaznak, ami lehetővé teszi az algoritmusok
összehasonlítását függetlenül az adott nyelvtől vagy géptől, és ez alapján megállapítható, hogy igen, egyes algoritmusok
hatékonyabbak a többinél. A Khan Academyn tanulhatsz az
algoritmusokról és az aszimptotikus elemzésről két dartmouthi egyetemi professzor közreműködésének köszönhetően. Tom Cormen a fő szerzője a világ legnépszerűbb
algoritmusokról szóló egyetemi tankönyvének, valamint az Algorithms Unlocked
című könyvnek. Devin Balkcom állította össze
a Dartmouth Bevezetés az informatikába kurzusát
és robotikát kutat. Ő építette a világ első
origami hajtogató robotját. Tom és Devin sok olyan
algoritmussal ismertet meg, amit az egyetemen az informatikai
bevezető kurzusokon tanítanak, például kereső algoritmusokkal,
rendezésekkel, rekurzív algoritmusokkal,
és az én kedvencemmel, a gráf-algoritmusokkal. Lesz egy csomó interaktív
vizualizáció, kvíz és kódolási feladat, ami mind segít abban, hogy megértsd, amit tanulsz.