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

Télapó probléma

2024. január 5.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

2023. augusztus 4.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, mint algoritmikus építőelem – ez az iteratív megoldás. A rekurzív megoldás tipikus rossz megoldásként ismert, lássuk ennek 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 (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), 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 (például 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.