Ha valaki nem járatos az informatika területén, hajlamos azt hinni, hogy egyféle ember létezik a szakmában, az „informatikus”, vagy multis terminológiával „IT-s” (ájtís).

Ha egy kicsit már többet tud róla, akkor el tudja különíteni azt a csoportot, aki programokat ír („programozó” vagy „fejlesztő”) a többiektől.

És míg magyarul szinte mindenki „fejlesztő” lesz, ha kezdőként állást talál ezen a területen, addig angol nyelvterületen sokkal színesebb a paletta:

computer programmer, software developer, software engineer, software architect, computer scientist,…

Most a computer science-ről / computer scientist-ről lesz szó.

Ebben a videóban (Intro 2. – IT-ról és szoftverfejlesztésről átfogóan) a többi angol megnevezésről viszonylag sokat beszéltem, a computer scientist-ről annyit mondtam csak, hogy egyetemen dolgozik és az algoritmusokat vizsgálja, fejleszti.

De akkor nézzük meg részletesen!

Először is egy fogalommagyarázat.

Az algoritmus a (számítógépes) lépéssorozatot jelenti, amelyet végrehajtva elérünk egy előre kitűzött célt. Ha a való életből akarok példát venni, akkor ott vannak a különböző műszaki eszközök használati utasításai, tehát pl. hogy kell használni egy DVD- vagy Blu-ray lejátszót. Lépésről lépésre le van írva, hogy mit kell tenned ahhoz, hogy a DVD elinduljon, és meg tudd nézni a filmet. Ebben az esetben rád van szabva az utasítássor, tehát te vagy a műveleteket végrehajtó „egység” is. A számítógépes algoritmusok esetében a számítógép az.

Vegyünk egy példaalgoritmust, amit otthon is ki tudsz próbálni:

Vegyél le a könyvespolcról 10 darab könyvet, tedd egymás mellé az asztalon.

Rendezd őket a szerző vezetékneve szerint ABC-sorrendbe!

Megvan?

Akkor most nehezítsünk a feltételeken!

(Keverd össze őket, majd) végezd el mindezt úgy, hogy kétféle dolgot csinálhatsz:

1. két könyv közül eldöntöd, hogy melyik szerzőjének a vezetékneve van előbb az ABC-ben,
2. megcserélsz két könyvet az asztalon.

Akárhogy is csinálod, valami ilyesmire képes a számítógép is.

Lehet, hogy úgy rendezted őket sorba, hogy fogtad az első könyvet, összehasonlítottad a másodikkal, és a szerző szerint előrébb lévőt összehasonlítottad a harmadikkal, és így tovább, mindig az addigi legkorábbit hasonlítottad össze a soron következővel. Majd ha ez megvolt, akkor a kiválasztottat (tehát a legelőrébb teendőt) kicserélted azzal, ami az asztalon a bal szélen volt. Majd ezt a könyvet kicsit arrébb tetted, és ugyanezt megcsináltad a többire.

Ha így dolgoztál, akkor maximumkiválasztásos rendezést (selection sort) hajtottál végre.

Hány összehasonlítást is végeztél?

Egyszer végighaladtunk a 10 könyvön, és végeztünk 9 összehasonlítást. Azután a maradék 9 könyvön 8-at, a maradék 8 könyvön 7-et, és így tovább. Összesen 45-öt. (Aki nem hiszi, járjon utána!)

Oké, és mi van akkor, ha kétszer annyi könyvünk van? Akkor hány összehasonlítás kell hozzá?

Nem 9-ről indulunk a számításban, hanem 19-ről, de ugyanúgy 1-ig adjuk össze a számokat.

190 lesz az eredmény, azaz nagyjából négyszer annyi, mint 10 könyvnél.

Ha pedig 100 elemet veszünk, akkor az összehasonlítások száma 4950-re nő.

A rendezés problémájára nem a fenti a leggyorsabb algoritmus.

Egy másik – merge sort a neve – 10 elemet 40, 100 elemet pedig 700 összehasonlításból tud rendezni, és a különbség az elemszám növekedésével egyre rohamosabb mértékben nő, és míg a merge sort 1.000.000 elemet „mindössze” 20.000.000 összehasonlításból rendezni tud, addig a maximumkiválasztásos rendezés ugyanennyi elemet 500 milliárdból.

Hogy jobban meg tudd fogni: ha a számítógépünk egy másodperc alatt 1 milliárd összehasonlítást végez, akkor a merge sort 2 századmásodperc alatt végez, addig a maximumkiválasztásosnak ehhez több mint 8 perc szükséges! (Most a cserék idejét nem vesszük figyelembe.)

A computer scientist azzal foglalkozik, hogy olyan új algoritmusokat találjon ki, amelyek elérik a kitűzött célt, de a lépésszám (itt pl. az összehasonlítások száma) a lehető legkevesebb lesz akkor, ha nagyon sok adatot kell feldolgozni.

Ez a terület közel áll a matematikához, sok bizonyítás, elméleti munka vár arra, aki ezen a területen dolgozik.

A jó hír az, hogy egy átlagos szoftverfejlesztőnek csak meg kell tanulnia a hatékony algoritmusokat (amiket már a computer scientistek kitaláltak), és – ha szükséges – meg kell valósítania.

De ez sem biztos.

A Java például beépítetten tartalmaz rendezési algoritmust (a merge sort egy változatát), tehát programozóként csak ki kell neki adni az utasítást, hogy „rendezz!”, és a Java megcsinálja.

Ha szeretnél a programozással megismerkedni, töltsd ki tesztünket!

Pasztuhov Dániel
CTO
StudiCore Kft.