Fő tartalom
1. témakör: Algoritmusok
A témakör tartalma:
A Dartmouth-i Egyetem két professzora, Tom Cormen és Devin Balkcom közreműködésével készítettük el az informatikai algoritmusok bevezető tanfolyamát, ahol szó lesz kereső algoritmusokról, rendezésről, rekurzióról, valamint gráfelméletről. Ebben a fejezetben szöveges tananyagok, megjelenített algoritmusok, programozási feladatok és kvízek segítségével tanulhatsz.
Mi az algoritmus, és miért lehet ez fontos ez számodra? Először általánosságban beszélünk az algoritmusokról, majd megvizsgálunk két játékot – a szám-kitalálós játékot és az útvonal-kereső játékot – ahol megfelelő algoritmus használatával hatékonyabb megoldást tudsz készíteni.
Ismerd meg a bináris keresést, ami hatékony módja a tömbökben való keresésnek azáltal, hogy a keresési tartományt minden egyes alkalommal megfelezi.
Tanuld meg, hogyan kell használni az aszimptotikus elemzést egy algoritmus hatékonyságának leírására. Ismerd meg az aszimptotikus jelölést (ordó jelölés, théta jelölés, omega jelölés), hogy még precízebben tudd meghatározni a hatékonyságot.
Tanulj!
Gyakorolj!
Tanuld meg a minimumkiválasztásos rendezést, ami egy egyszerű algoritmus tömbök rendezéséhez! Fedezd fel, miért nem ez a leghatékonyabb algoritmus!
Tanulj!
Tanuld meg, hogyan működik a beszúró rendezés, ami egy másik egyszerű, de nem túl hatékony módszer tömbök rendezéséhez.
Ismerkedj meg a rekurzió fogalmával, ami az algoritmusok sokszor használt eszköze! Tanuld meg, hogyan kell rekurziót használni faktoriális kiszámításához, számok hatványozásához, vagy művészeti alkotás létrehozásához!
Tanulj!
Oldd meg a Hanoi torony feladványt rekurzióval! Ezt a klasszikus matematikai feladványt állítólag szerzetesek próbálták megfejteni.
Tanulj meg egy hatékonyabb rendezési algoritmust, az összefésülő rendezést, ami erősen támaszkodik a rekurzióra, amikor résztömböket ismételten rendez és összevon.
Tanulj!
Tanuld meg a gyorsrendezést, egy másik hatékony rendezési algoritmust, amely a rekurzió felhasználásával gyorsabban rendez tömböket.
Tanulj!
Tanuld meg, hogyan kell leírni egy gráfot élek, csúcspontok és súlyok segítségével; hogyan lehet gráfok adatait tárolni, mi az éllista, a szomszédsági mátrix, a szomszédsági lista!
Tanuld meg, hogyan tudod bejárni a gráfot szélességi kereséssel úgy, hogy a gráfban szintenként navigálsz egy adott csúcspont megtalálásához, vagy azért, hogy az összes csúcspontot elérd!
Jótanácsok ahhoz, hogyan tudnád tovább mélyíteni ismereteidet az algoritmusok témakörben.