évforduló - címke - Oldal 5 a 5-ből

Télapó probléma

2026. január 2.2017. december 6. Szerző: Kaczur Sándor

Az operációs rendszerek tervezésének fontos része az ütemezési, erőforrás- és szálkezelési feladatok problémamentes, holtpontmentes megoldása, szinkronizálása, amiről sok ismert szerző publikált már, néhányan közülük angol nyelven: W. Stallings, A. B. Downey, A. S. Tanenbaum, A. S. Woodhull., és magyarul is: Galambos Gábor, Knapp Gábor és Adamis Gusztáv. Ehhez a szakterülethez tartozik több népszerű probléma/esettanulmány, például a vacsorázó bölcsek problémája, illetve a Santa Claus Problem, vagyis a Télapó probléma.

A Télapó probléma specifikációját és megoldását a konkurens programozás eszközeire építve J. A. Trono készítette el (szemaforokkal), amire építve is – és kritizálva is azt – több Java implementáció is elkészült (például: P. Steiner), valamint több programozási nyelv szálkezelési lehetőségeinek összehasonlításáról is publikált J. Hurt és J. B. Pedersen és kliens-szerver elosztott környezetben is áttekintette a lehetőségeket D. Marchant és J. Kerridge. Ismert Haskell, Erlang, Polyphonic C# implementáció is.

A Télapó probléma meghatározása

A Télapó alszik az északi-sarki boltjában és csak akkor ébredhet fel, ha mind a 9 rénszarvas visszatér a dél-csendes-óceáni trópusi szigetén töltött rendes évi nyaralásukról, illetve ha akad néhány manó, akiknek nehézségei vannak az ajándékkészítés során. A 10 manó közül 1 manó problémája nem elég komoly ahhoz, hogy felébressze a Télapót (egyébként sosem aludna), így 3 manó megy egyszerre a Télapóhoz. Amikor a 3 manó problémáit közösen megoldották, akkor mind a 3 manónak vissza kell térnie a többi manóhoz, mielőtt egy újabb manólátogatás megtörténne. Ha a Télapó úgy ébred, hogy 3 manó várja őt a bolt ajtajánál és az utolsó rénszarvas is visszatért a trópusokról, akkor a Télapónak fontosabb, hogy olyan gyorsan elinduljon a szánnal, amilyen gyorsan csak lehetséges – így a manóknak várniuk kell karácsony utánig. Feltételezzük, hogy a rénszarvasok nem akarják elhagyni a trópusokat, ezért az utolsó pillanatig maradnak, amíg csak lehetséges. Lehet, hogy egyáltalán nem is jönnének vissza, ameddig a Télapó fizeti a számlát a paradicsomban… Ez is megmagyarázhatja az ajándékok kiszállításának gyorsaságát, hiszen a rénszarvasok alig várják, hogy visszatérhessenek oda, ahol meleg van. Az utolsóként érkező rénszarvas büntetést kap a Télapótól, mialatt a többi rénszarvas a meleg kunyhóban várja, hogy befogják őket a szán elé.

A Télapó probléma – egyik – megoldása

Találtam egy kb. 10 perces kiváló YouTube videót/animációt (The Santa Claus Problem Thread Synchronization), amely lépésenként felépíti a feladatot, érzékelteti a közben felmerülő problémákat, és megoldást is mutat. Ezt ajánlom december 6-án minden érdeklődő figyelmébe:

Megjegyzés: a videót nem mi készítettük. 2017-től 2020-ig az eredeti linkről ágyaztuk be a blog bejegyzésbe a videót. 2020-ban a videót az eredeti linkről (https://www.youtube.com/watch?v=pqO6tKN2lc4) eltávolították. A blog bejegyzésbe jelenleg beágyazott videó a 2017-es mentett változat.

A feladatot részletekbe menően és komplex módon gondolkodva kell megtervezni, és implementációi komoly nyelvi eszköztárat igényelnek. Érdemes P. Steiner Java megoldását részletesen átnézni, újragondolva – újabb nyelvi eszköztárral – implementálni.

A feladat a Java EE szoftverfejlesztő tanfolyam 1-4. óra: Elosztott alkalmazások, webszolgáltatások, illetve 5-8. óra: Szálkezelés, párhuzamosság alkalmaihoz kapcsolódik.

Fibonacci nap

2025. június 15.2017. november 23. Szerző: Kaczur Sándor

A Fun Holidays – Fun, Wacky & Trivial Holidays weboldal sokféle különleges ünnepnapot listáz. Ezek leírása többnyire vicces, emlékezős, de néhány igazán érdekes, régi-régi hagyományt elevenít fel.

Ma van (november 23.) a Fibonacci nap. Fibonacci középkori matematikus volt, ő tette közismertté a Fibonacci-sorozat-ot. A (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, … sorozat igen népszerű azok közében is, akik programozást tanulnak. A sorozat első két eleme 1 és 1 (ha szükséges, akkor nulladik elemmel is dolgozhatunk), és minden további elem az előző két elem összege. Többféle történet is fűződik ehhez, talán az egyik legismertebb a nyúlpárok szaporodásához kötődik.

Honnan származik a Fibonacci nap? A mai nap hh.nn. formátumban 11.23. , és a számjegyek részei a Fibonacci-sorozatnak. Mindössze ennyi, ilyen egyszerű. 😉

A sorozat elemei könnyen előállíthatók néhány változó használatával. Ha a kezdő programozó már ismeri a ciklust – algoritmikus építőelemként –, akkor ez az iteratív megoldás. A rekurzív megoldás tipikus rossz megoldásként ismert. Lássuk az utóbbi Java megvalósítását:

public class FibTeszt {

final static int N=5;

static int fib(int n) {

for(int i=1; i<=N-n; i++)

System.out.print("-");

System.out.println("fib("+n+")");

if(n<2)

return n;

return fib(n-1)+fib(n-2);

}

public static void main(String[] args) {

System.out.println(fib(N));

}

Ha kiadnám a fenti Java forráskódot papíron ezt egy dolgozatban, zárthelyin, állásinterjú szakmai részén azzal a kérdéssel, hogy mit ír ki a program a képernyőre, akkor bizony sokan bajban lennének. Meg is történt ez már sokszor, tapasztalatból írom. A rekurzió első leszálló ágáig szinte mindenki eljut, de az ott induló első felszálló ágat követően sokan belezavarodnak a részlépések egymásutániságába. A végeredményt szinte mindenki tudja, de itt most arra helyezzük a hangsúlyt, hogy hogyan jutunk el odáig. Persze n=5-re fib(5)=5. Alig fordult még elő, hogy valaki hibátlanul leírta volna az alábbi eredményt:

fib(5)

-fib(4)

--fib(3)

---fib(2)

----fib(1)

-----fib(0)

----fib(1)

---fib(2)

----fib(1)

-----fib(0)

--fib(3)

---fib(2)

----fib(1)

-----fib(0)

----fib(1)

A megoldás során – emlékeztetek arra, hogy ez atipikus megközelítés – sok-sok redundáns lépés történik. Hiszen például a fib(3)-at tudni kell a fib(4)-hez és a fib(5)-höz is, hiszen fib(4)=fib(2)+fib(3) és fib(5)=fib(3)+fib(4), valamint ebben az implementációban nincs semmilyen emlékezet (puffer, adatszerkezet), amivel a sok feleslegesnek vélhető számítást elkerülhetnénk.

Nyert ügye lehet annak, aki „fejben összerakja” az alábbi fát – akár dinamikusan, menet közben hozzáadva és törölve elemeket – és ebben navigálva (ezt bejárva) válaszolja meg a kérdést:

Az alábbi animáció segíthet a megértésben. 45 lépésben mutatja be az aktuális részlépést/részfeladatot (leszálló ág) és/vagy az aktuális részeredményt (felszálló ág):

A Fibonacci-sorozat többféleképpen kapcsolódik a természethez, természeti jelenséghez, növényekhez, állatokhoz. Például: virágszirmok száma, levelek elfordulása, napraforgók magjai, fenyőtoboz pikkelyei, nautilus háza, aranymetszés, zenei hangolás, zeneművek tagolása). A Fibonacci-sorozat felhasználható algoritmusok futási idejének becsléséhez, fa adatszerkezetek építéséhez is. Az aranymetszésről megoszlanak a vélemények. Vannak akik szinte mindenben ezt látják (művészet: festészet, szobrászat), mások módszeresen cáfolják ezt. Utóbbira példa Falus Róbert: Az aranymetszés legendája, Magyar Könyvklub, 2001, második, javított kiadás, ISBN 963-547-332-X.

A bejegyzéshez tartozó teljes forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 9-12. óra: Metódusok, rekurzió alkalmához kötődik.

Húsvétvasárnap

2023. augusztus 4.2017. április 16. Szerző: Kaczur Sándor

A nyugati kereszténység húsvétvasárnapja legkorábban március 22-ére, legkésőbb április 25-re esik. Másképpen: a húsvét mozgó ünnep, azaz nem esik az év ugyanazon napjára minden évben. Az első niceai zsinat 325-ben úgy határozott, hogy legyen a keresztény húsvét időpontja a tavaszi napéjegyenlőség utáni első holdtöltét követő vasárnap.

A húsvét kiszámítására a legismertebb algoritmus Gauss módszere. A Java implementációban az easterGauss() függvény által elfogadható év paramétert életszerűen lekorlátoztam 1900-2099-ig terjedő évekre, valamint a vezérlés az aktuális és a rákövetkező 19 évben ír ki eredményt:

private static final int MIN_YEAR=1900, MAX_YEAR=2099;

public static String easterGauss(int y) {

if(y<MIN_YEAR || y>MAX_YEAR)

throw new IllegalArgumentException(

y+" not in ["+MIN_YEAR+", "+MAX_YEAR+"]");

int a=y%19, b=y%4, c=y%7, d=(19*a+24)%30, e=(2*b+4*c+6*d+5)%7,

h=22+d+e;

if(e==6 && d==29) //1. kivétel

h=50;

if(e==6 && d==28 && a>10) //2. kivétel

h=49;

String message="Húsvétvasárnap "+y+" évben: ";

if(h<=31) //március

message+="március "+h+".";

else //április

message+="április "+(h-31)+".";

return message;

}

public static void main(String[] args) {

System.out.println("Mikor van húsvétvasárnap az alábbi években?");

int startYear=

Math.max(MIN_YEAR, Calendar.getInstance().get(Calendar.YEAR));

int endYear=Math.min(startYear+19, MAX_YEAR);

for (int y=startYear; y<=endYear; y++)

System.out.println(easterGauss(y));

}

Az algoritmus részletes magyarázata alapján könnyen kiegészíthető úgy, hogy tetszőleges évre, illetve különböző naptárakra is működjön.

A kapott eredmények megtekinthetők:

Mikor van húsvétvasárnap az alábbi években?

Húsvétvasárnap 2017 évben: április 16.

Húsvétvasárnap 2018 évben: április 1.

Húsvétvasárnap 2019 évben: április 21.

Húsvétvasárnap 2020 évben: április 12.

Húsvétvasárnap 2021 évben: április 4.

Húsvétvasárnap 2022 évben: április 17.

Húsvétvasárnap 2023 évben: április 9.

Húsvétvasárnap 2024 évben: március 31.

Húsvétvasárnap 2025 évben: április 20.

Húsvétvasárnap 2026 évben: április 5.

Húsvétvasárnap 2027 évben: március 28.

Húsvétvasárnap 2028 évben: április 16.

Húsvétvasárnap 2029 évben: április 1.

Húsvétvasárnap 2030 évben: április 21.

Húsvétvasárnap 2031 évben: április 13.

Húsvétvasárnap 2032 évben: március 28.

Húsvétvasárnap 2033 évben: április 17.

Húsvétvasárnap 2034 évben: április 9.

Húsvétvasárnap 2035 évben: március 25.

Húsvétvasárnap 2036 évben: április 13.

A feladat – a kivételkezeléstől eltekintve – a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 5-8. óra: Vezérlési szerkezetek alkalmához kötődik.

Nemzetközi IT-s nőnap

2024. február 4.2017. március 8. Szerző: Kaczur Sándor

A nemzetközi nőnap (március 8.) alkalmából olyan nőkre emlékezünk, akik maradandót alkottak a számítástechnika, informatika, szoftverfejlesztés, programozás területén. A válogatás alapját a Women in computing gyűjtemény adta. A lista természetesen nem teljes, ezért érdemes tovább böngészni a témában. (Aktualizálva: 2020. szeptember 1.)

Ada Lovelace (1815-1852, angol matematikus) leírást készített a Babbage-féle analitikai gépéhez. Valószínűsíthető, hogy ehhez a géphez programokat is készített (pl.: a Bernoulli-számok kiszámításának algoritmusát, 1843-ban), így az első programozónak tekinthető.

Edith Clarke (1883-1959, amerikai villamosmérnök) feltalálta a Clarke számológépet 1921-ben – 10-szer gyorsabban oldaná meg az egyenleteket a korábbi módszereknél –, amely villamos áramot, feszültséget és impedanciát tartalmazó egyenleteket oldott meg az erőátviteli vezetékekben.

Hedy Lamarr (1914-2000, osztrák feltaláló) torpedók irányítási problémáival foglakozott és zavarásuk ellen kidolgozott egy lyukszalag segítségével működő gyorsan váltakozó frekvenciát az adónál és a vevőnél egyaránt (titkos kommunikációs rendszer, 1940).

Joan Clarke (1917-1996, angol kriptográfus) bekerült Alan Turing csapatába, ahol matematikusok, kódfejtők és titkos ügynökök dolgoztak azon a II. világháború idején, hogy megfejtsék az akkor használt (többedik generációs) német Enigma gép által küldött titkos üzeneteket.

Betty Holberton (1917-2001, amerikai számítástechnikus) egyike volt az ENIAC programozóinak 1946-ban. Ez volt az első általános célú elektronikus digitális számítógép. Feltalálta a töréspontokat, amelyeket a számítógépes hibakeresés (debugging) során használunk.

Grace Murray Hopper (1906-1992, amerikai matematikus) készítette az első fordítóprogramot (compiler) 1952-ben. Felvázolta a számítógéptől független programozási nyelv ötletét (amiből később megszületett a COBOL 3. generációs programozási nyelv). Neki köszönhetjük a hibakeresés (debugging) kifejezés elterjesztését.

Erna Schneider Hoover (1926-, amerikai matematikus) olyan számítógépes telefonos kapcsolási módszert talált fel 1954-ben, amely a call center forgalom nyomon követésével (prioritások meghatározásával) megakadályozta a rendszer túlterhelését.

Jean E. Sammet (1928-2017, amerikai számítástechnikus) az IBM-nél dolgozott és 1962-ben kifejlesztette a FORMAC programozási nyelvet. Tanulmányozta, hogyan lehetne használni programozási nyelvként a korlátozott angolt – mint természetes nyelvet – matematikai programokban.

Mary Kenneth Keller (1913-1985, amerikai számítógép-úttörő) részt vett a BASIC programozási nyelv létrehozásában (1964), számos eljárást és függvényt specifikált. Ő volt az első nő, aki PhD tudományos fokozatot szerzett az informatika területén az USA-ban.

Margaret Hamilton (1936-, amerikai számítástechnikus, rendszermérnök) alkotta meg a szoftverfejlesztés fogalmát. Az MIT-n azt a labort vezette, amelyik fedélzeti repülési szoftvert fejlesztett a NASA Apollo űrprogramhoz, a Hold misszióihoz az 1960-as években.

Karen Spärck Jones (1935-2007, brit számítógép-kutató) kidolgozta az IDF koncepciót (inverse document frequency) 1972-ben, amelyen ma is alapszik a keresőmotorok működése. Erősen kampányolt azért, hogy minél több nő foglalkozzon számítástechnikával.

Radia Perlman (1951-, amerikai programozó és hálózati mérnök) – az „internet anyja” – megalkotta az STP protokollt 1985-ben, amely alapvető a hálózati kommunikáció megvalósításában, ezzel nagymértékben hozzájárult a hálózatok szabványosításához, valamint kifejlesztette a LOGO programozási nyelv gyermekbarát változatát TORTIS néven 1974-ben.

Sophie Wilson (1957-, brit számítógéptudós) megtervezte az Acorn mikroszámítógépet 1979-ben, és kifejlesztette az ARM processzorok első generációjának utasításkészletét 1985-ben. Korunk mobil eszközei szinte kizárólag ARM technológiára épülnek.

Roberta Williams (1953-, amerikai videójáték-tervező) az 1980-as években a PC-s játékok tervezésének egyik meghatározó egyénisége. Munkássága a Sierra Entertainment céghez kötődik, ahol az első grafikus kalandjáték, illetve az első színes grafikájú játék is elkészült.

Frances Allen (1932-2020, amerikai számítógéptudós) szakterülete a számítógépes fordítóprogramokhoz, program(kód) optimalizáláshoz és párhuzamosításukhoz kötődött az IBM-nél. 2006-ban első nőként kapott Turing-díjat.