Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2011-2012‎ > ‎

4. óra

2011.10.10.

Ezen a szakkörön nem lesz új feladat, hanem az egy héttel ezelőtt elkészített megoldásokat fejlesztjük.
Az előző heti feladat: Telefonszámok

A "szótár" kezelését és a legrövidebb megoldás kiválasztását is végezhetjük "okosabban", ehhez két klasszikus módszert tanulunk.

Hasító függvények avagy HASH-elés

Az algoritmus egyik kulcslépése a lehetséges szavak hatékony keresése a megengedett szavak listájában. Mivel ez egy alapvető részfeladat a fordítóprogramok működésénél, több különböző megoldást adtak már rá.
Sedgewick-Wayne: Hashing

Az órai feladat megoldásához az is elegendő, ha a szótár szavait rendezzük, és bináris keresést használunk.

Legrövidebb út súlyozatlan, irányítatlan gráfban


Sedgewick-Wayne: Shortest Paths

A minimális felbontás megtalálása átfogalmazható egy súlyozatlan gráf pontjai közötti legrövidebb út megtalálásának feladatává. Ennek részleteit a feladat megoldásánál közöljük. A legrövidebb út meghatározásának algoritmusait a következő szakkörökön részletezzük.