Mi az algoritmus, és miért fontos?

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.