statisztika - címke - it-tanfolyam.hu

Rácsrejtjelezés

2024. április 5.2024. január 18. Szerző: Kaczur Sándor

Időnként készítünk oktatóprogramokat is tanfolyamainkon. Most az volt a cél, hogy kódolás/dekódolás szakterület egyik ismert betűkeveréses algoritmusának működését mutassa be lépésről-lépésre az oktatóprogram. A rácsrejtjelezést választottuk.

Az elkészült program Java swing-es felületű és Windows Classic look-and-feel bőrrel így néz ki működés közben:

A rácsrejtjelezés a képernyőképen látható 4×4-es Kódrács használatán alapul.

A titkosítandó szöveget karakterenként beleírjuk az aktuális kódrácsba soronként lefelé, azon belül balról jobbra haladva. Ha a négy pozíció betelt, akkor el kell fordítani a kódrácsot az óramutató járásával megegyező irányban 90 fokkal. Ha a szöveg hosszabb 16 karakternél, akkor elölről kell kezdeni. Ha készen vagyunk, akkor soronként haladva leírjuk egymás után a kódrácsban található karaktereket.

A megfejtéshez ismernünk kell a titkosított karaktersorozaton kívül a felhasznált kódrácsot is. A karaktersorozatot soronként lefelé haladva beírjuk a kódrácsba, az ismert kódrácsot ráhelyezve soronként lefelé, azon belül balról jobbra haladva kiolvashatjuk a megfejtést. Természetesen a kódrácsot most is forgatni kell minden negyedik karakter után.

Megfigyelhető, hogy bármely karaktert tudunk titkosítani és megfejteni. Ezért a rácsrejtjelezés ebből a szempontból univerzális módszer.

A kódrács ismerete nélkül a titkosított szöveg nem fejthető meg, tartalmára csak nehézkes következtetést adhatunk. Például, ha tudjuk, hogy milyen nyelvű a titkosított szöveg, akkor támpontot adhat a megfejtéséhez a nyelv ábécéjében előforduló betűk ismert gyakorisága.

A képernyőkép éppen a megfejtés egyik pillanatában készült. A feladó továbbította a titkosított szöveget és a kódrácsot a címzettnek, aki elkezdte annak megfejtését. A negyedik karakter a b volt, utoljára erre kattintott a (4;4) pozícióban. Ezt követte egy rácsforgatás, amelyhez tartozik egy ablak, amely megjeleníti a „Rácsforgatás következik.” szöveget. Ezután a kódrács elfordult, és a következő cella a második sor első cellája lesz. Ha hibás cellára, pozícióra kattintunk, akkor a következő hibaüzeneteket kaphatjuk: „Hibáztál! Folytathatod a titkosítást.” vagy „Hibáztál! Folytathatod a megfejtést.” Ha befejeztük a titkosítást, vagy a megfejtést, akkor a következő üzeneteket kaphatjuk: „A kódolás sikerült.” vagy „A megfejtés sikerült.”

A program tartalmaz egy gyakorlást támogatandó szövegkészletet. Ennek minden eleme 16 hosszúságú, az egyszerűség kedvéért – így nem kell véletlenszerű karakterekkel feltölteni a rács kimaradt celláit, illetve nem kell 16-os csoportokkal foglalkozni.

A Titkosítás és megfejtés fülön látható egy véletlenszerűen kiválasztott szöveg, amelyet karakterenként kódolni lehet a kódrács megfelelő cellájára kattintva. Ha kész, a Továbbítás gombbal a feladó elküldi a címzettnek a titkosított karaktersorozatot, aki hasonlóan megfejti. „Útközben” megfigyelhető, hogy éppen hányadik elforgatásnál tartunk és természetesen megjelenik az aktuális ráccsal titkosított szöveg is.

Az űrlapon lévő Kódrács csoportablak az aktuálisan, véletlenszerűen legenerált kódrácson kívül a kiválasztott cellák pozícióit is tartalmazza. Az (1;1) pozícióban a bal felső cella található. A kódrács a Másik nyomógombbal véletlenszerűen újragenerálható. Ennek megvalósításakor több probléma, ötlet is felmerülhet. Például használható visszalépéses keresés algoritmus.

Most nem specifikáljuk részletesebben, például objektumorientált tervezés, eseménykezelés, háttérbeli objektumok vagy GUI komponensek működésének/vezérlésének szintjén. Aki kedvet kapott és úgy érzi, hogy meg tudja ugrani ezt a kihívást, akkor bátran elkészítheti. Hajrá! Mivel oktatóprogram, szükséges hozzá Leírás és Teszt is.

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 Java SE szoftverfejlesztő tanfolyamunkon, a szakmai modul Objektumorientált programozás témakörét követő 29-36. óra Grafikus felhasználói felület alkalmain már tudunk egyszerűbb oktatóprogramot tervezni, kódolni, tesztelni.

Doktoranduszok programoznak – újratöltve

2024. január 5.2024. január 5. Szerző: Kiss Balázs

it-tanfolyam.hu doktoranduszok programoznak

Saját doktorandusz csoporttársaimmal én is többször beszélgettem már arról – ahogyan Sándor is tette 2018-ban –, hogyan tudnák/tudják használni a programozás eszköztárát, módszereit, lehetőségeit saját kutatási munkájukban, beépítve a kutatási folyamat egyes lépéseibe, illetve disszertációjuk elkészítésébe.

A 7 fős csoportban mindenkinek más az alapvégzettsége, így szoftverfejlesztéshez, programozáshoz közös szókincs és terminológia haladó szinten természetesen nincs, viszont közös bennünk, hogy mindannyian alkotunk különféle modelleket és elemzünk adatokat. A csoport teljesen inhomogén, több szempontból is: ki melyik évfolyamot végzi, hol tart a kutatómunkájában, vannak-e ipari kapcsolatai, nappali vagy levelező képzésben végzi tanulmányait és persze ki mikor ér rá.

Különféle modelleket alkotunk

a mérnökök, fizikusok, geográfusok, biológusok többféle kísérletet végeznek el, szimulációkat terveznek és futtatnak, mérőeszközöket és műszereket használnak,
az informatikusok különböző matematikai eszközöket alkalmazva objektumorientált – vagy másféle – modellezést végeznek, szoftvereket terveznek, javítanak, újraírnak.

Adatokat is elemzünk, ki-ki előképzettségének megfelelően

kérdőívező szoftverekből exportálva valamit,
Excel munkalapokon, függvényekkel, adatbázis-kezelő funkciókkal, kimutatásokkal (Pivot táblák),
különböző fájlformátumokkal (CSV, XML, JSON, egyedi) dolgozunk és konvertálunk A-ból B-be,
távoli adatbázisokhoz, felhőbeli adattárházakhoz csatlakozunk, lekérdezünk és kapunk valamilyen – többnyire szabványos – adathalmazt,
matematikai, statisztikai szoftvereket használunk, például: MATLAB, Derive, Maple, SPSS.

Az öt évvel ezelőtti tematikát újragondoltuk. Kérdőívben felmértük a csoporttársak koncepcionális és konkrét igényeit. Más doktori iskolák hallgatói közül is toboroztunk. Ehhez kötődően köszönjük a DOSZ segítségét. Ezek alapján összeállítottunk egy olyan 3 részből álló tematikát, ami mindannyiunk számára hasznos. A 72 óra három 24 órás modulból áll: Java programozás, MATLAB programrendszer, mesterséges intelligencia.

Java programozás modul

1-6. óra: Objektumorientált modellezés, MVC rétegek, algoritmus- és eseményvezérelt programozás
7-12. óra: Fájlkezelés és szövegfeldolgozás (XLS, CSV, XML, JSON formátumú adatok írása, olvasása, feldolgozása), helyi és távoli adatforrásból
13-18. óra: Adatbázis-kezelés JDBC alapon (SQL parancsok, CRUD műveletek, hierarchikus lekérdezések), helyi és távoli adatforrásból, natív módon és készen kapott API-kkal
19-24. óra: Komplex adatfeldolgozási feladatok megoldása programozási tételek használatával, egyszerű statisztikai funkciók implementálásával

MATLAB programrendszer modul

1-6. óra: Bevezetés az MATLAB nyelvbe (R2012 vs. R2022), utasításkészlet, vektorok, mátrixok, szkriptek, függvények, grafika
7-12. óra: Szimulációk tervezése és készítése, numerikus módszerek áttekintése, algoritmizálása, tesztelés, analitikus megoldás, egyenletek megoldása
13-18. óra: Adatok importálása helyi és távoli adatforrásból is, fájlkezelés: szövegfájlok, Excel-fájlok, import, feldolgozás, export, statisztikai alapok
19-24. óra: Statisztikai próbák (illeszkedés- és függetlenség vizsgálata), hisztogramok készítése, differenciálegyenletek megoldása

Mesterséges intelligencia modul

1-6. óra: Klasszikus és újabb megközelítések, alap AI funkcionalitás, megerősítéses és gépi tanulás lehetőségei és korlátai, OpenAI GPT nyelvi modell
7-12. óra: Általános csevegés lehetőségei, korlátai, hasznos tanácsok; csevegés fájlok (szöveg, multimédia) tartalmáról; generatív AI funkciói; kép, ábra, grafikon, térkép, hang, animáció, videó generálása és ezek tömeges feldolgozása; programozási tételek alkalmazása multimédia analitikával együtt
13-18. óra: Statisztikai adatok elemzése AI eszközökkel, automatikus tételbizonyítás AI eszközökkel, gráfelméleti kérdések kontra AI, hatékonysághoz kötődő kérdések AI eszközök esetén
19-24. óra: Objektum- és aspektusorientált tervezés AI eszközökkel, kutatómunkát támogató AI eszközök

Mivel mindenki doktorandusz a csoportban, így a különböző MSc-s alapvégzettsége ellenére mindannyiunknak vannak strukturális programozáshoz kötődő alapismeretei, valamint adatok elemzéséhez szükséges elméleti matematikai/statisztikai alapjai.

A csoport órái szeptembertől decemberig, szombatonként zajlottak. Sándor tartotta a 24 órás Java programozás modult. Ez nagyban lefedi a Java SE szoftverfejlesztő tanfolyamunk tematikáját és kapcsolódik a Java EE szoftverfejlesztő tanfolyamunk és a Java adatbázis-kezelő tanfolyamunk tematikájához is. Én tartottam a 24 órás MATLAB programrendszer modult. Ketten közösen tartottuk a 24 órás Mesterséges intelligencia modult. Igazán tartalmas őszi időszakot jelentett számunkra ez a 12 szombat. Mindenki elvitte, amit beletett.

A koncepciót once-in-a-lifetime jelleggel dolgoztuk ki 🙂 (újratöltve) azzal a fő szándékkal, hogy hatékonyabban működjünk együtt a jövőben. A visszajelzések alapján bátran állíthatom, hogy ez gördülékenyen fog menni. Egyben köszönöm mindenkinek az aktív, konstruktív részvételt.

Születésnap-paradoxon

2023. szeptember 3.2023. szeptember 2. Szerző: Kaczur Sándor

Mennyi a valószínűsége, hogy n ember között van kettő, akiknek egy napon van a születésnapja? A meglepő a dologban az, hogy már 23 ember esetén a kérdéses valószínűség 1/2-nél nagyobb. Másképpen: már 23 ember esetén nagyobb annak az esélye, hogy megegyezik a születésnapjuk, mint az ellenkezőjének. Ez a 23 nagyon kevésnek tűnik. Ezért paradoxon.

Közismert néhány hétköznapi valószínűség. Íme néhány szabályos eset. A pénzfeldobás során 1/2 az esélye a fej és 1/2 az esélye az írás eredménynek (másképpen 50%-50%, azaz fifty-fifty). A kockadobás esetén 1/6 az esélye bármelyik számnak 1-től 6-ig. Két kocka esetén blogoltam már a dobott számok összegének alakulásáról, eloszlásáról: Kockadobás kliens-szerver alkalmazás.

Néhány egyszerűsítés

Az év 365 napból áll. Nem számítanak a 366 napos szökőévek.
A születések eloszlása egyenletes, azaz minden nap körülbelül ugyanannyian születnek. Nem számít, hogy hétköznap, hétvége, ünnepnap. Az áramszüneti városi legendák sem.
Nem vesszük figyelembe az azonos napon született ikreket. Persze ikrek születhetnek különböző napokon is.

Azonos születésnap valószínűsége grafikonon

Lássuk, hogyan alakul az azonos születésnap valószínűsége az emberek számától függően! Grafikonon ábrázolva:

A fenti grafikonhoz szükséges adatok könnyen előállíthatók az alábbi Java forráskóddal:

private static String scatterChartData() {

List<String> list=IntStream.range(1, 71).boxed().

map(n->String.format(Locale.US,

"%10c[ %d, %.4f ]", ' ', n, 1-Math.pow(364.0/365, n*(n-1)/2))).

collect(Collectors.toList());

return String.join(",\n", list);

}

A fenti Google Chart típusú szórásgrafikon (Scatter Chart, korrelációs diagram) megjelenítéséhez adatpárok sorozata szükséges. Ezek a konkrétumok (70 db adatpár), görgethető:

[ 1, 0.0000 ],

[ 2, 0.0027 ],

[ 3, 0.0082 ],

[ 4, 0.0163 ],

[ 5, 0.0271 ],

[ 6, 0.0403 ],

[ 7, 0.0560 ],

[ 8, 0.0739 ],

[ 9, 0.0940 ],

[ 10, 0.1161 ],

[ 11, 0.1401 ],

[ 12, 0.1656 ],

[ 13, 0.1926 ],

[ 14, 0.2209 ],

[ 15, 0.2503 ],

[ 16, 0.2805 ],

[ 17, 0.3114 ],

[ 18, 0.3428 ],

[ 19, 0.3745 ],

[ 20, 0.4062 ],

[ 21, 0.4379 ],

[ 22, 0.4694 ],

[ 23, 0.5005 ],

[ 24, 0.5310 ],

[ 25, 0.5609 ],

[ 26, 0.5900 ],

[ 27, 0.6182 ],

[ 28, 0.6455 ],

[ 29, 0.6717 ],

[ 30, 0.6968 ],

[ 31, 0.7208 ],

[ 32, 0.7435 ],

[ 33, 0.7651 ],

[ 34, 0.7854 ],

[ 35, 0.8045 ],

[ 36, 0.8224 ],

[ 37, 0.8391 ],

[ 38, 0.8547 ],

[ 39, 0.8690 ],

[ 40, 0.8823 ],

[ 41, 0.8946 ],

[ 42, 0.9058 ],

[ 43, 0.9160 ],

[ 44, 0.9254 ],

[ 45, 0.9339 ],

[ 46, 0.9415 ],

[ 47, 0.9485 ],

[ 48, 0.9547 ],

[ 49, 0.9603 ],

[ 50, 0.9653 ],

[ 51, 0.9697 ],

[ 52, 0.9737 ],

[ 53, 0.9772 ],

[ 54, 0.9803 ],

[ 55, 0.9830 ],

[ 56, 0.9854 ],

[ 57, 0.9875 ],

[ 58, 0.9893 ],

[ 59, 0.9909 ],

[ 60, 0.9922 ],

[ 61, 0.9934 ],

[ 62, 0.9944 ],

[ 63, 0.9953 ],

[ 64, 0.9960 ],

[ 65, 0.9967 ],

[ 66, 0.9972 ],

[ 67, 0.9977 ],

[ 68, 0.9981 ],

[ 69, 0.9984 ],

[ 70, 0.9987 ]

Hasonló grafikon készítéséről szintén blogoltam már: Céline Dion – Courage World Tour.

Párok előállítása

Az emberek születésnapjainak összehasonlítása párokban történik. 23 ember esetén 23*22/2=253 pár van. Általános esetben n ember esetén (n*(n-1))/2 pár adódik. A levezetés részletei a források között megtalálható. 59 ember esetén 1711 pár adódik és szinte garantált az előforduló azonos születésnap, hiszen már 0,99 ennek a valószínűsége.

Az alábbi Java forráskód – rekurzív módon – előállítja a 23 konkrét esetre a párokat, az embereket 1-23-ig sorszámozva. Kombinációk:

private static void combinationsInternal(

List<Integer> input, int k,

List<List<Integer>> output,

ArrayList<Integer> acc, int i) {

int needToAcc=k-acc.size(), canAcc=input.size()-i;

if(acc.size()==k)

output.add(new ArrayList<>(acc));

else if(needToAcc<=canAcc) {

combinationsInternal(input, k, output, acc, i + 1);

acc.add(input.get(i));

combinationsInternal(input, k, output, acc, i + 1);

acc.remove(acc.size()-1);

}

public static List<List<Integer>> combinations(

List<Integer> input, int k) {

List<List<Integer>> output=new ArrayList<>();

combinationsInternal(input, k, output, new ArrayList<>(), 0);

return output;

}

public static void main(String[] args) {

for(int i=23; i<=23; i++) {

List<Integer> list=IntStream.range(1, i+1).

mapToObj(x->x).collect(Collectors.toList());

List<List<Integer>> combinationList=combinations(list, 2);

Collections.reverse(combinationList);

System.out.println(

i+" db elemből:\n"+

list+"\n"+

combinationList.size()+" db pár:\n"+

combinationList);

}

A main() metódusban az i változó paraméterezhető és a konkrét eset könnyen intervallumra változtatható. Eredményül ezt írja ki a program a konzolra, görgethető:

23 db elemből:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23]

253 db pár:

[[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 10], [1, 11], [1, 12], [1, 13], [1, 14], [1, 15], [1, 16], [1, 17], [1, 18], [1, 19], [1, 20], [1, 21], [1, 22], [1, 23],

[2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10], [2, 11], [2, 12], [2, 13], [2, 14], [2, 15], [2, 16], [2, 17], [2, 18], [2, 19], [2, 20], [2, 21], [2, 22], [2, 23],

[3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [3, 9], [3, 10], [3, 11], [3, 12], [3, 13], [3, 14], [3, 15], [3, 16], [3, 17], [3, 18], [3, 19], [3, 20], [3, 21], [3, 22], [3, 23],

[4, 5], [4, 6], [4, 7], [4, 8], [4, 9], [4, 10], [4, 11], [4, 12], [4, 13], [4, 14], [4, 15], [4, 16], [4, 17], [4, 18], [4, 19], [4, 20], [4, 21], [4, 22], [4, 23],

[5, 6], [5, 7], [5, 8], [5, 9], [5, 10], [5, 11], [5, 12], [5, 13], [5, 14], [5, 15], [5, 16], [5, 17], [5, 18], [5, 19], [5, 20], [5, 21], [5, 22], [5, 23],

[6, 7], [6, 8], [6, 9], [6, 10], [6, 11], [6, 12], [6, 13], [6, 14], [6, 15], [6, 16], [6, 17], [6, 18], [6, 19], [6, 20], [6, 21], [6, 22], [6, 23],

[7, 8], [7, 9], [7, 10], [7, 11], [7, 12], [7, 13], [7, 14], [7, 15], [7, 16], [7, 17], [7, 18], [7, 19], [7, 20], [7, 21], [7, 22], [7, 23],

[8, 9], [8, 10], [8, 11], [8, 12], [8, 13], [8, 14], [8, 15], [8, 16], [8, 17], [8, 18], [8, 19], [8, 20], [8, 21], [8, 22], [8, 23],

[9, 10], [9, 11], [9, 12], [9, 13], [9, 14], [9, 15], [9, 16], [9, 17], [9, 18], [9, 19], [9, 20], [9, 21], [9, 22], [9, 23],

[10, 11], [10, 12], [10, 13], [10, 14], [10, 15], [10, 16], [10, 17], [10, 18], [10, 19], [10, 20], [10, 21], [10, 22], [10, 23],

[11, 12], [11, 13], [11, 14], [11, 15], [11, 16], [11, 17], [11, 18], [11, 19], [11, 20], [11, 21], [11, 22], [11, 23],

[12, 13], [12, 14], [12, 15], [12, 16], [12, 17], [12, 18], [12, 19], [12, 20], [12, 21], [12, 22], [12, 23],

[13, 14], [13, 15], [13, 16], [13, 17], [13, 18], [13, 19], [13, 20], [13, 21], [13, 22], [13, 23],

[14, 15], [14, 16], [14, 17], [14, 18], [14, 19], [14, 20], [14, 21], [14, 22], [14, 23],

[15, 16], [15, 17], [15, 18], [15, 19], [15, 20], [15, 21], [15, 22], [15, 23],

[16, 17], [16, 18], [16, 19], [16, 20], [16, 21], [16, 22], [16, 23],

[17, 18], [17, 19], [17, 20], [17, 21], [17, 22], [17, 23],

[18, 19], [18, 20], [18, 21], [18, 22], [18, 23],

[19, 20], [19, 21], [19, 22], [19, 23],

[20, 21], [20, 22], [20, 23],

[21, 22], [21, 23],

[22, 23]]

Kísérleti ellenőrzés

Tekintsünk például 1000 esetet! Készítsünk Java programot, amely 23 db véletlen születésnapot generál! Legyen ez a születésnap sorszáma az évben (másképpen hányadik napon született az ember az évben). Ez lényegesen egyszerűsíti a megoldást, összevetve a dátumkezelésen alapuló megközelítéssel. Ajánljuk a szakmai blog dátumkezelés címkéjét az érdeklődőknek, ahol megtalálhatók a témához kapcsolódó Java forráskódrészletek részletes magyarázatokkal kiegészítve. Íme a többféle generikus listát és programozási tételt használó forráskód:

public static void main(String[] args) {

final int COUNT=1000;

ArrayList<String> list1=new ArrayList<>();

int count2=0;

for(int i=1; i<=COUNT; i++) {

ArrayList<Integer> dayList=new ArrayList<>();

for(int n=1; n<=23; n++) {

int day=(int)(Math.random()*365+1); //1-365

dayList.add(day);

}

Collections.sort(dayList);

System.out.println(dayList);

ArrayList<String> list2=new ArrayList<>();

int n=0;

while(n<dayList.size()) {

int currentDay=dayList.get(n), count1=0;

while(n<dayList.size() && dayList.get(n)==currentDay) {

count1++;

n++;

}

if(count1>1)

list2.add(i+","+currentDay+","+count1);

}

if(!list2.isEmpty()) {

list1.add(list2.toString());

count2++;

}

System.out.println("\n"+list1+"\n"+COUNT+" esetből "+

count2+" kedvező eset fordult elő");

}

Érdemes elemezni, tesztelni a fenti forráskódot: milyen lépésekben, milyen adatszerkezeteket épít. Hasznos lehet lambda kifejezésekkel kiegészíteni, módosítani a programot. Részlet a program szöveges eredményéből:

[4, 14, 31, 34, 73, 85, 88, 110, 119, 125, 132, 140, 148, 183, 241, 249, 255, 265, 272, 289, 303, 353, 355]

[7, 16, 40, 67, 72, 72, 79, 89, 96, 128, 141, 142, 203, 215, 217, 219, 230, 243, 250, 272, 273, 321, 325]

[63, 70, 70, 87, 92, 106, 112, 113, 115, 123, 124, 131, 138, 139, 164, 165, 173, 177, 179, 180, 241, 310, 357]

[45, 48, 73, 75, 94, 103, 117, 161, 168, 170, 202, 223, 231, 235, 240, 252, 254, 255, 260, 272, 274, 284, 301]

[2, 2, 3, 13, 39, 47, 66, 94, 148, 151, 153, 160, 161, 166, 179, 212, 223, 254, 280, 311, 316, 324, 340]

[5, 32, 36, 71, 74, 80, 96, 115, 120, 150, 167, 167, 169, 219, 255, 259, 283, 289, 304, 306, 317, 336, 359]

[4, 5, 17, 46, 65, 78, 78, 79, 95, 106, 116, 138, 189, 228, 251, 253, 304, 332, 332, 334, 337, 347, 362]

[12, 14, 15, 67, 76, 77, 113, 126, 154, 161, 184, 195, 204, 214, 216, 225, 225, 225, 227, 229, 235, 236, 348]

[5, 7, 18, 28, 55, 71, 83, 126, 126, 129, 150, 158, 169, 221, 224, 231, 242, 253, 267, 300, 321, 326, 329]

[19, 37, 47, 49, 80, 89, 94, 122, 145, 165, 174, 190, 211, 215, 241, 265, 286, 287, 295, 297, 325, 354, 361]

...

[[2,72,2], [3,70,2], [5,2,2], [6,167,2], [7,78,2, 7,332,2], [8,225,3], [9,126,2]...

1000 esetből 506 kedvező eset fordult elő.

A 12. sorban lévő számhármasok jelentése: esetszám 1-től, azonos nap, előfordulás száma. Például: a kísérlet során a 8. esetben az év 225. napja azonos 3 embernél. Természetesen nincs garancia arra, hogy az 1000 eset vizsgálatánál mindig 500-nál nagyobb kedvező esetet kapunk.

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 17-28. óra Objektumorientált programozás alkalmaihoz kötődik.

Források

Születésnap-paradoxon – Wikipédia
Stráhl, I. (2016): Születésnap paradoxon – lesz olyan, aki osztozik a tortán?
Kasnyik, M. (2019): Harmadával kevesebb gyerek születik hétvégéken és ünnepnapokon, mint hétköznap
J. Frost (2020): Answering the Birthday Problem in Statistics
K. Azad (2018): Understanding the Birthday Paradox
Vsause2 (2019): The Birthday Paradox – YouTube
P. Com, M. Habib, T. Suresh, L. Weinstein, C. Lin, J. Khlm, E. Ross (2022): Birthday Problem | Brilliant Math & Science Wiki
Baeldung (2022): Overview of Combinatorial Problems in Java

Egy matematika érettségi feladat megoldása programozással 2021

2023. augusztus 4.2021. május 4. Szerző: Kaczur Sándor

A 2021-es középszintű matematika érettségi feladatsor 12. feladata inspirált arra, hogy a programozás eszköztárával oldjuk meg ezt a feladatot. Szükséges hozzá néhány programozási tétel: sorozatszámítás, eldöntés, megszámolás, kiválogatás. Többféle megoldás/megközelítés is előkerül. Érdekes belegondolni, hogy mennyire más lehetne a problémamegoldás, ha programozhatnánk a matematika érettségi vizsgán. A teljes feladatsor a megoldásokkal együtt letölthető az oktatas.hu-ról.

12. feladat

A háromjegyű pozitív egész számok közül véletlenszerűen kiválasztunk egyet. Mennyi annak a valószínűsége, hogy a kiválasztott szám számjegyei különbözők? Megoldását részletezze!

1. megoldás

static void feladat12Megoldas1() {

int db=0;

for(int szazas=1; szazas<=9; szazas++)

for(int tizes=0; tizes<=9; tizes++)

for(int egyes=0; egyes<=9; egyes++)

if(szazas!=tizes && tizes!=egyes && szazas!=egyes)

db++;

System.out.println("1. megoldás: "+db/900.0);

}

Az 1. megoldás egymásba ágyazott ciklusokkal behelyettesíti a szóba jöhető 900 db háromjegyű szám számjegyeit. A feltétel 648 esetben teljesül. Három számjegy azonosságát két részfeltétel és kapcsolatával eldönthetnénk a trichotómia miatt. Három számjegy különbözőségéhez három részfeltétel és kapcsolatából áll össze a feltétel. A válasz a kedvező és összes eset aránya/hányadosa, azaz 0,72. Másképpen 648 db szám a 900 db háromjegyű szám közül. A megoldás lépésszáma 900.

2. megoldás

static void feladat12Megoldas2() {

int db=0;

for(int szazas=1; szazas<=9; szazas++)

for(int tizes=0; tizes<=9; tizes++)

if(szazas!=tizes)

for(int egyes=0; egyes<=9; egyes++)

if(tizes!=egyes && szazas!=egyes)

db++;

System.out.println("2. megoldás: "+db/900.0);

}

Az egymásba ágyazott ciklusok lépésszáma összeszorzódik. A legbelső ciklus az előtte lévő feltételtől függően kevesebbszer is végrehajtódhat, hiszen a százas és tízes helyiértéken lévő számjegyek egyezése esetén nincs értelme az egyes helyiértéken lévő számjegy vizsgálatának. Így a 2. megoldás lépésszáma 810, azaz 10%-kal kevesebb. Ez a három részből álló feltétel két részre bontásával érhető el.

3. megoldás

static void feladat12Megoldas3() {

int db=0;

for(int i=100; i<=999; i++) {

int szazas=i/100;

int tizes=i%100/10;

int egyes=i%100%10;

if(szazas!=tizes && tizes!=egyes && szazas!=egyes)

db++;

}

System.out.println("3. megoldás: "+db/900.0);

}

A 3. megoldásban egyetlen ciklus végzi a vizsgálatot, a megszámolást. A ciklusváltozó már nem számjegy, hanem maga a háromjegyű szám, amiről döntést kell hozni: különbözik-e mindegyik számjegye vagy sem. Három beszédes nevű segédváltozó segít értelmezni a Java forráskódot. Ezek az egész osztás és a maradékos osztás műveleteivel állíthatók elő.

4. megoldás

static boolean kulonbozoSzamjegyek(int i) {

int szazas=i/100;

int tizes=i%100/10;

if(szazas==tizes)

return false;

int egyes=i%100%10;

if(tizes==egyes || szazas==egyes)

return false;

return true;

}

static void feladat12Megoldas4() {

int db=0;

for(int i=100; i<=999; i++)

if(kulonbozoSzamjegyek(i))

db++;

System.out.println("4. megoldás: "+db/900.0);

}

A 4. megoldás logikai visszatérési értékű segédfüggvényt alkalmaz. Ez egy menekülőutas megoldás. Ha kizáró feltétel szerint már döntést tudunk hozni (például megegyezik a százas és a tízes helyiértéken lévő számjegy), akkor hamis értékkel menekülünk. Egyébként ág nélkül ezután következhet az egyes helyiértéken lévő számjegy összehasonlítása a többivel. A második feltétel az eddigiekhez képest tagadott, mert a menekülés a cél. Ha nincs menekülés amiatt, hogy volt két megegyező számjegy, akkor – a feltételek egymásra épülése miatt – nincs más hátra, mint igaz értékkel visszatérni (ami azt jelenti, hogy nem volt egyezés, azaz minden számjegy különbözött).

5. megoldás

static long kulonbozoSzamjegyDb(int i) {

return IntStream.of(i/100, i%100/10, i%100%10).distinct().count();

}

static void feladat12Megoldas5() {

int db=0;

for(int i=100; i<=999; i++)

if(kulonbozoSzamjegyDb(i)==3)

db++;

System.out.println("5. megoldás: "+db/900.0);

}

Az 5. megoldás segédfüggvénye a háromjegyű szám esetén a különböző számjegyek darabszámával tér vissza. A röptében előállított százaz, tízes, egyes helyiértékeken lévő számjegyekből folyam adatszerkezet készül, aminek feldolgozását a Stream API műveletei (egyediesítő, megszámoló) végzik el. Ezt a vezérlő ciklusban hárommal összehasonlítva léptethető a megszámolást megvalósító változó, hiszen ha teljesül a feltétel, akkor eggyel több megfelelő szám van, mint előtte volt.

6. megoldás

static void feladat12Megoldas6() {

int db=0;

for(int i=100; i<=999; i++) {

int szazas=i/100;

int tizes=i%100/10;

int egyes=i%100%10;

if(szazas==tizes || tizes==egyes || szazas==egyes)

db++;

}

System.out.println("6. megoldás: "+(900-db)/900.0);

}

Az 6. megoldás újra másképpen közelít. Ha könnyebbnek tűnik az a feltétel, hogy mikor nem jó (kedvezőtlen) nekünk egy szám, akkor beépíthetjük ezt is. Megszámoljuk azokat a háromjegyű számokat, amelyeknél egy vagy két számjegy azonos, majd ez kivonjuk a háromjegyű számok darabszámából.

7. megoldás

static void feladat12Megoldas7() {

long db=IntStream.range(100, 1000).

filter(i -> IntStream.of(i/100, i%100/10, i%100%10).

distinct().count()==3).count();

System.out.println("7. megoldás: "+db/900.0);

}

A 7. megoldás már mindent folyamokkal old meg, azok képességeire építve. Az összes háromjegyű számot előállítja, majd rajtuk kiválogatás programozási tételt (szűrőt) használ (az 5. megoldás segédfüggvényére építve), végül a folyamban maradó számokat megszámolja. Ez a megoldás már olyan haladóknak való, akik magabiztosan építik össze a Stream API műveleteit és a lambda kifejezéseket. Mindent egyben. Persze hol itt a hatékonyság? Hozzászólásokban megbeszélhetjük.

8. megoldás

static void feladat12Megoldas8() {

long db=IntStream.range(100, 1000).

filter(i -> !(i/100==i%100/10 && i%100/10==i%100%10)). //1. szűrő

filter(i -> !(i/100==i%100/10)). //2. szűrő

filter(i -> !(i%100/10==i%100%10)). //3. szűrő

filter(i -> !(i/100==i%100%10)). //4. szűrő

count();

System.out.println("8. megoldás: "+db/900.0);

}

A 8. megoldás szintén folyam adatszerkezettel működik, de négy egymást követő lépésben végez szűrést (kiválogatást). A 900 db háromjegyű számból indulunk ki. Az 1. szűrő kihagyja a 9 db AAA számot, amelyek számjegyei azonosak és így marad utána 891 db szám. A 2. szűrő után marad 810 db szám, mert kimarad az a 81 db AAB alakú szám (ahol a százas és tízes helyiértéken lévő számjegyek megegyeznek) az összesen 90 db-ból, ami még a folyamban maradt az 1. szűrő után. A 3. szűrő kihagy 81 db ABB alakú számot és meghagy 729 db számot. A 4. szűrő kihagy 80 db ABA alakú számot és meghagy 648 db ABC alakú számot.

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

Ajánljuk matematika érettségi feladat címkénket, mert a témában évről-évre blogolunk.

A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 5-8. óra: Vezérlési szerkezetek, 13-16. óra: Tömbök, valamint 21-24. óra: Objektumorientált programozás, 2. és 3. rész alkalmaihoz kötődik.

Rómeó és Júlia

2023. augusztus 4.2021. február 14. Szerző: Kaczur Sándor

Vajon hogyan kerül elő a Rómeó és Júlia az it-tanfolyam.hu szakmai blogban témaként? Hiszen mégiscsak egy Shakespeare színműről/tragédiáról van szó. Vajon mit programozhatunk Java nyelven ehhez kötődően épp Valentin-napon? Mindjárt kiderül.

Tegyünk fel egy kérdést és próbáljunk rá válaszolni! Vajon ki szereti jobban a másikat? Rómeó vagy Júlia?

Induljunk el az adatforrásból, amihez alkalmazkodnunk kell. A színmű angol nyelven publikusan elérhető XML formátumban: The Tragedy of Romeo and Juliet. Az XML fájlok könnyen feldolgozhatók Java nyelven. Részletek a fájlból (görgethető):

<?xml version="1.0"?>

<LINE>Two households, both alike in dignity,</LINE>

<LINE>In fair Verona, where we lay our scene,</LINE>

<LINE>From ancient grudge break to new mutiny,</LINE>

<LINE>Where civil blood makes civil hands unclean.</LINE>

...

</SPEECH>

<SPEAKER>ROMEO</SPEAKER>

<LINE>Is the day so young?</LINE>

</SPEECH>

<SPEAKER>ROMEO</SPEAKER>

<LINE>Stay, fellow; I can read.</LINE>

<STAGEDIR>Reads</STAGEDIR>

<LINE>'Signior Martino and his wife and daughters;</LINE>

<LINE>County Anselme and his beauteous sisters; the lady</LINE>

...

<LINE>assembly: whither should they come?</LINE>

</SPEECH>

<SPEAKER>ROMEO</SPEAKER>

<LINE><STAGEDIR>To JULIET</STAGEDIR> If I profane with my unworthiest hand</LINE>

<LINE>This holy shrine, the gentle fine is this:</LINE>

<LINE>My lips, two blushing pilgrims, ready stand</LINE>

<LINE>To smooth that rough touch with a tender kiss.</LINE>

</SPEECH>

<STAGEDIR>Enter JULIET</STAGEDIR>

</ACT>

Az XML fájl felépítését tanulmányozva (1-5 alapján) megállapíthatóak az alábbiak:

A színmű öt felvonásból áll, ezeket <ACT></ACT> csomópontok jelölik.
Egy „adagnyi” beszédet a <SPEECH></SPEECH> csomópont fog össze.
A csomópontban található, hogy ki beszél: ez a <SPEAKER></SPEAKER> elem. A mesélő, kar esetén ez az elem üres, és a null-t nem szabad feldolgozni.
A csomópontban találhatók a szabadvers kimondott sorai: ezek a <LINE></LINE> elemek. Legalább egy sor minden beszédben van, és nem tudjuk előre a számukat.
Nem következetes helyen a DOM-ban, többféleképpen beágyazva és önállóan is előfordulhatnak <STAGEDIR></STAGEDIR> elemek. Ezek a színmű Kosztolányi-féle magyar fordításában dőlt betűvel megjelenő – cselekvésre utaló – színpadi utasítások. Van köztük csók is, amit az XML-ből nem szabad feldolgozni, bár erősen ráutaló magatartás. 🙂
Nem tudjuk előre, hogy hány csomópont található a fájlban.

A Java program készítése, tesztelése közben – mintegy mellékesen – megtudhatjuk, hogy Rómeó 612 sorban 24075 betűnyi, Júlia 544 sorban 21855 betűnyi szöveget mond. Persze nem mindet egymásnak mondják. Eközben vajon hányszor mondják ki a szeret, szeretem, szeretlek szavakat? A ragoktól, toldalékoktól, kis- és nagybetűket nem megkülönböztetve és attól is eltekintve, hogy éppen kinek/kiknek mondják amit éppen mondanak, egy becsléshez elegendő, ha a love szóra fókuszálunk (számíthatna a loving alak is).

Az alábbi Java forráskód betölti az XML fájlt a memóriába. Ezután kiválogatja a beszédeket. Ha a beszélő élő ember (szereplő), akkor érdekes, hogy mit/miket mond. Ha ROMEO vagy JULIET mondja az adott sort, akkor azt a program kiválogatja két generikus listába ( romeoLineList és julietLineList) beszédnyi adagokban. Ez nem szétválogatás programozási tétel, mert nem minden beszéd minden sora kerül valahová. A kivételkezelés nem kidolgozott.

private static ArrayList<String> getLineList(final Node SPEECH) {

ArrayList<String> lineList=new ArrayList<>();

NodeList nodeList=((Element)SPEECH).getElementsByTagName("LINE");

for(int i=0; i<nodeList.getLength(); i++) {

String line=

((Element)nodeList.item(i)).getFirstChild().getNodeValue();

lineList.add(line);

}

return lineList;

}

public static void main(String[] args) {

ArrayList<String> romeoLineList=new ArrayList<>();

ArrayList<String> julietLineList=new ArrayList<>();

try {

NodeList speechList=DocumentBuilderFactory.newInstance().

newDocumentBuilder().parse(new File("./files/r_and_j.xml")).

getDocumentElement().getElementsByTagName("SPEECH");

for(int i=0; i<speechList.getLength(); i++) {

Node speech=speechList.item(i);

Node speaker=((Element)speech).getElementsByTagName("SPEAKER").

item(0).getFirstChild();

if(speaker!=null)

switch(speaker.getNodeValue()) {

case "ROMEO":

romeoLineList.addAll(getLineList(speech));

break;

case "JULIET":

julietLineList.addAll(getLineList(speech));

}

catch(ParserConfigurationException | SAXException | IOException e) {

e.printStackTrace();

}

//...

}

Könnyen megkaphatjuk, hogy Rómeó hány darab olyan sort mond, amely tartalmazza a love szót. Például ennek a lambda kifejezésnek kiíratva az eredményét a konzolra:

romeoLineList.stream().

filter(f->f!=null).filter(f->f.toLowerCase().contains("love")).

count();

Könnyen megkaphatjuk Rómeótól a 53 sornyi szöveget is így:

romeoLineList.stream().

filter(f->f!=null).filter(f->f.toLowerCase().contains("love")).

forEach(line->System.out.println(line));

Íme Rómeó kiválogatott sorai (az 5. sorban kétszer is előfordul a love, de ez most nem számít):

Out of her favour, where I am in love.

Alas, that love, whose view is muffled still,

Here's much to do with hate, but more with love.

Why, then, O brawling love! O loving hate!

This love feel I, that feel no love in this.

Why, such is love's transgression.

With more of thine: this love that thou hast shown

Love is a smoke raised with the fume of sighs;

Being purged, a fire sparkling in lovers' eyes;

Being vex'd a sea nourish'd with lovers' tears:

In sadness, cousin, I do love a woman.

A right good mark-man! And she's fair I love.

From love's weak childish bow she lives unharm'd.

She hath forsworn to love, and in that vow

widow of Vitravio; Signior Placentio and his lovely

One fairer than my love! the all-seeing sun

Under love's heavy burden do I sink.

Is love a tender thing? it is too rough,

Did my heart love till now? forswear it, sight!

It is my lady, O, it is my love!

O, that I were a glove upon that hand,

Call me but love, and I'll be new baptized;

With love's light wings did I o'er-perch these walls;

For stony limits cannot hold love out,

And what love can do that dares love attempt;

And but thou love me, let them find me here:

Than death prorogued, wanting of thy love.

By love, who first did prompt me to inquire;

If my heart's dear love--

The exchange of thy love's faithful vow for mine.

Wouldst thou withdraw it? for what purpose, love?

Love goes toward love, as schoolboys from

But love from love, toward school with heavy looks.

How silver-sweet sound lovers' tongues by night,

Then plainly know my heart's dear love is set

And bad'st me bury love.

I pray thee, chide not; she whom I love now

Doth grace for grace and love for love allow;

A gentleman, nurse, that loves to hear himself talk,

Then love-devouring death do what he dare;

Tybalt, the reason that I have to love thee

But love thee better than thou canst devise,

Till thou shalt know the reason of my love:

Wert thou as young as I, Juliet thy love,

My conceal'd lady to our cancell'd love?

No nightingale: look, love, what envious streaks

That may convey my greetings, love, to thee.

And trust me, love, in my eye so do you:

Ah me! how sweet is love itself possess'd,

When but love's shadows are so rich in joy!

By heaven, I love thee better than myself;

Call this a lightning? O my love! my wife!

Here's to my love!

Hasonlóan megkaphatjuk Júlia 38 kiválogatott sorát is:

My only love sprung from my only hate!

Prodigious birth of love it is to me,

That I must love a loathed enemy.

Or, if thou wilt not, be but sworn my love,

Dost thou love me? I know thou wilt say 'Ay,'

Thou mayst prove false; at lovers' perjuries

If thou dost love, pronounce it faithfully:

My true love's passion: therefore pardon me,

And not impute this yielding to light love,

Lest that thy love prove likewise variable.

This bud of love, by summer's ripening breath,

My love as deep; the more I give to thee,

I hear some noise within; dear love, adieu!

If that thy bent of love be honourable,

Remembering how I love thy company.

O, she is lame! love's heralds should be thoughts,

Therefore do nimble-pinion'd doves draw love,

My words would bandy her to my sweet love,

Sweet, sweet, sweet nurse, tell me, what says my love?

'Your love says, like an honest gentleman,

But my true love is grown to such excess

Spread thy close curtain, love-performing night,

Lovers can see to do their amorous rites

By their own beauties; or, if love be blind,

With thy black mantle; till strange love, grown bold,

Think true love acted simple modesty.

That all the world will be in love with night

O, I have bought the mansion of a love,

My dear-loved cousin, and my dearer lord?

Believe me, love, it was the nightingale.

Art thou gone so? love, lord, ay, husband, friend!

To wreak the love I bore my cousin

But thankful even for hate, that is meant love.

I will confess to you that I love him.

To live an unstain'd wife to my sweet love.

Love give me strength! and strength shall help afford.

And gave him what becomed love I might,

What's here? a cup, closed in my true love's hand?

Próbáljunk válaszolni a fentiek alapján a feltett kérdésre! Következtethetünk arra, hogy Rómeó jobban szereti Júliát. Legalábbis többször említi. 53>38. Persze tudjuk, hogy mindez nem ilyen egyszerű. 🙂

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 21-24. óra: Objektumorientált programozás 2. rész, 25-28. óra: Objektumorientált programozás 3. rész, valamint a Java EE szoftverfejlesztő tanfolyam szakmai moduljának 9-12. óra: XML feldolgozás alkalmaihoz kötődik.

Nagyon különböző megoldásokat készíthetünk és szerteágazóan gyakorolhatunk, ha:

az XML fájlt kézzel mentjük a webről és utána a helyi fájlrendszerből dolgozzuk fel,
az XML fájlt közvetlenül a webről, dinamikusan olvassuk,
csak beépített XML-feldolgozást használunk,
külső XML API-t használunk,
DOM, SAX, XSL, van-e DTD,
XPath kifejezésekkel adunk választ a kérdésre,
a fenti didaktikusan egyszerű megoldás helyett haladóbb eszközöket (például: Stream API-t) használunk.