Születésnap-paradoxon

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:

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ő:

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:

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ő:

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:

É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:

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

Fibonacci-sorozat

Fibonacci logó

Fibonacci logóMa van (november 23.) a Fibonacci nap (újra). 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.

Korábban is blogoltak a kollégáim a témában:

Következzen most az én öt különböző megoldásom Java forráskódja, rövid magyarázattal. Mindegyik a Fibonacci-sorozat első tíz elemét állítja elő.

1. megoldás

Az első megoldás generikus listát épít. Az első két elemet elhelyezi a lista elején ( list.add(1)). Ezek a lista nulladik és első elemei lesznek. Ezután a metódus a maradék 8 elemmel 2-től n-1-ig fiktív indexként hivatkozva az előző két elem összegeként ( list.get(i-1)+list.get(i-2)) index nélkül bővíti a listát.

2. megoldás

A második megoldás a tipikusan nem hatékony rekurzív módszert implementálja. A rekurzív fib() függvény a sorozat egyetlen elemét adja vissza, amit (a függvényt) a ciklus sokszor meghív ahelyett, hogy a ciklus vagy a rekurzió „emlékezne” az előző elemekre.

3. megoldás

A harmadik megoldás funkcionális nyelvi elemeket (Stream API) használ. A folyamba kétdimenziós tömbre történő hivatkozással ( f-> new int[] ), közvetlen hozzárendeléssel/leképezéssel ( map()), kerülnek be a sorozat elemei.

4. megoldás

A negyedik megoldás a Fibonacci-számok zárt alakját használja. Másképpen ez a Binet-formula:

Ezzel a képlettel a sorozat elemei közvetlenül megadhatók, azaz nem szükséges más elemekre való hivatkozás. A ciklus adja meg, hogy a sorozat 1-10-ig indexelt elemei szükségesek.

5. megoldás

Az ötödik megoldás szintén Stream API-t használ. Először előállít egy sorozatot 1-10-ig, amiket a leképezésnél ( map()) inputként használ és alkalmazza rájuk a Binet-formulát. Hagyományos ciklus utasítás nem szükséges.

Eredmény

Mindegyik megoldás a konzolra írja szövegesen az eredményt, azaz a Fibonacci-sorozat első tíz elemét: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Érdemes elemezni a hatékonyság klasszikus három szempontja (időigény/lépésszám, tárigény, bonyolultság) alapján a különböző megoldásokat. Ezek mérésével könnyen kiegészíthetők a fenti metódusok, vagy az azokat meghívó osztályban a vezérlés.

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

IT történet – decemberben történt

IT történet blog bejegyzés sorozatunkban válogatunk a decemberben történt események közül – bármikortól napjainkig. A főbb témakörök: IT általában, számítástudomány, hardver, szoftver, platform, szoftverfejlesztés, játékprogramok, híres informatikusok, kibernetikusok, feltalálók, IT hírek, technológiai mérföldkövek. Természetesen nem törekedhetünk a teljességre, pusztán érdekességeket említünk röviden, tömören, amit illik tudni a szakterület iránt érdeklődőknek.


2010. december 2-án, 11 éve történt:
Megjelent a Viber okostelefonokra készült ingyenes VOIP alkalmazás – a Skype vetélytársaként. Először csak iPhone-on működött.


1924. december 3-án, 97 éve történt:
Megszületett John Backus amerikai matematikus, informatikus. Megalkotta a BNF jelölésrendszert, amely programozási nyelvek nyelvtanának leírására használható.


2020. december 3-án, tavaly történt:
Kínában elérték a kvantumfölényt a Jiuzhang nevű kvantumszámítógéppel, amely percek alatt végezhet el olyan számításokat, amikhez a világ legerősebb szuperszámítógépének kétmilliárd évre lenne szüksége.


2020. december 4-én, tavaly történt:
Megtörtént a világ első célzott kibertámadása, postai csomagpont hálózat ellen. Egyszerre kinyitották a PickPoint cég Moszkvában lévő csomagautomatái közül 2732-nek az ajtajait.


2001. december 8-án, 20 éve történt:
Elhunyt Betty Holberton. Az ENIAC egyik programozója volt 1946-ban. Feltalálta a töréspontokat, amelyeket a számítógépes hibakeresés (debugging) során használunk.


1815. december 10-én, 206 éve történt:
Megszületett Ada Lovelace angol matematikus és írónő, akit az első számítógép-programozónak tekintünk.


2005. december 10-én, 16 éve történt:
Megjelent Európában az Xbox 360, a Microsoft által fejlesztett hetedik generációs otthoni videójáték-konzol, az Xbox utódja.


2008. december 11-én, 13 éve történt:
A Google Inc. kiadta számítógépeken és mobil eszközökön is ingyenesen használható Chrome webböngészőjének első stabil verzióját.


2020. december 15-én, tavaly történt:
Átadásra került az a villaépület, amelyet a MEET (Middle East Eng. Technologies) két hét alatt 3D nyomtatott a Sharjah emírségben.


1990. december 20-án, 31 éve történt:
A CERN részecskefizikai kutatóközpontjában dolgozó Tim Berners-Lee létrehozta a világ első weboldalát, amivel megkönnyítette az intézményen belüli kommunikációt. Az oldalt kilenc hónap múlva publikálta.


1995. december 21-én, 26 éve történt:
Megjelenik a Ruby 0.95, interpreter alapú, általános célú, magasszintű programozási nyelv első változata. Tervezője és megalkotója a japán Yukihiro Matsumoto.


1834. december 23-án, 187 éve történt:
Charles Babbage angol matematikus és korai számítógép-tudós elkészítette az analitikai gép terveit. Ez volt az első mechanikus számítógépek egyike.


1957. december 25-én, 64 éve történt:
II. Erzsébet brit királynő elfogadta a BBC felkérését és élő adásban felolvasta televíziós karácsonyi üzenetét. Emberek milliói, akik a legszentebb családi ünnepeken otthonukban ülnek, először csatlakoztak a királynőhöz az otthonában.


1992. december 26-án, 29 éve történt:
Elhunyt Kemény János magyar-amerikai matematikus, számítástechnikus, a BASIC programozási nyelv megalkotója.


1903. december 28-án, 118 éve történt:
Megszületett Neumann János magyar születésű matematikus. Kvantummechanikai elméleti kutatásai mellett a digitális számítógép elvi alapjainak lefektetésével vált ismertté.


IT történet – novemberben történt

IT történet blog bejegyzés sorozatunkban válogatunk a novemberben történt események közül – bármikortól napjainkig. A főbb témakörök: IT általában, számítástudomány, hardver, szoftver, platform, szoftverfejlesztés, játékprogramok, híres informatikusok, kibernetikusok, feltalálók, IT hírek, technológiai mérföldkövek. Természetesen nem törekedhetünk a teljességre, pusztán érdekességeket említünk röviden, tömören, amit illik tudni a szakterület iránt érdeklődőknek.


1988. november 2-án, 33 éve történt:
A Cornell Egyetem diákja, Robert Tappan Morris útjára bocsátotta 99 sornyi kódból álló programját, a később róla elnevezett Morris worm-ot, amely az első internetes féregvírus.


2007. november 5-én, 14 éve történt:
Az Android mobil operációs rendszer „születésnapja”. Megjelent az Android béta változata.


1977. november 7-én, 44 éve történt:
Megszületett Paul Buchheit amerikai informatikus, vállalkozó, aki létrehozta a Gmail-t. A Google 23. felvett alkalmazottja.


1983. november 9-én, 38 éve történt:
Elhunyt Kozma László, Kossuth-díjas villamosmérnök. Nevéhez fűződik az első magyarországi digitális számítógép, a MESZ–1 megtervezése és üzembe állítása (1957).


2005. november 9-én, 16 éve történt:
A feltalálók napja, amelyet Ausztriában, Németországban és Svájcban tartanak 2005 óta, az osztrák származású Hedy Lamarr feltaláló születésének évfordulóján.


2020. november 12-én, tavaly történt:
A Sony Interactive Entertainment megjelentette a PlayStation 5 (PS5) otthoni videójáték-konzolt Japánban, amely már a 9. generációt képviselte.


1929. november 17-én, 92 éve történt:
Elhunyt Herman Hollerith német származású amerikai statisztikus, feltaláló, üzletember, aki lyukkártya-feldolgozó gépet fejlesztett és szabadalmaztatott.


2007. november 20-án, 14 éve történt:
Lemond Paul Gray, a brit királyi adó- és vámhivatal elnöke, miután kiderült, hogy eltűnt két számítógépes adathordozó, amelyeken a brit felnőtt lakosság felének minden adó- és bankszámla-adata rajta volt.


2013. november 22-én, 8 éve történt:
Megjelent az USA-ban az Xbox One, a Microsoft nyolcadik generációs videójáték-konzolja, az Xbox 360 utódja.


2014. november 25-én, 7 éve történt:
A NASA bejelentette, kinyomtatta az első tárgyat a Nemzetközi Űrállomáson lévő 3D nyomtató. Ez az első olyan használati eszköz, amelyet a Földön kívül gyártottak, súlytalanság állapotában.


1852. november 27-én, 169 éve történt:
Elhunyt Ada Lovelace angol matematikus és írónő, akit az első számítógép-programozónak tekintünk.


1985. november 27-én, 36 éve történt:
A Microsoft Corporation kiadta első grafikus felhasználói felülettel rendelkező operációs rendszerét, a Windows 1.0-t.


1902. november 28-án, 119 éve történt:
Megszületett Kozma László, Kossuth-díjas villamosmérnök. Nevéhez fűződik az első magyarországi digitális számítógép, a MESZ–1 megtervezése és üzembe állítása (1957).


1915. november 29-én, 106 éve történt:
Megszületett Eugene Polley amerikai mérnök és mérnök menedzser, akit leginkább a televíziózás első vezeték nélküli távirányítójának feltalálójaként ismerünk.


1972. november 29-én, 49 éve történt:
A Nolan Bushnell és Al Alcorn által alapított Ataritól játéktermekbe került a világ első kereskedelmileg is sikeres videojátéka, a Pong.


IT történet – októberben történt

IT történet blog bejegyzés sorozatunkban válogatunk az októberben történt események közül – bármikortól napjainkig. A főbb témakörök: IT általában, számítástudomány, hardver, szoftver, platform, szoftverfejlesztés, játékprogramok, híres informatikusok, kibernetikusok, feltalálók, IT hírek, technológiai mérföldkövek. Természetesen nem törekedhetünk a teljességre, pusztán érdekességeket említünk röviden, tömören, amit illik tudni a szakterület iránt érdeklődőknek.


2014. október 1-jén, 7 éve történt:
Letölthetővé vált a Microsoft új operációs rendszerének a Windows 10-nek a próbaverziója.


2011. október 4-én, 10 éve történt:
Megjelent a Siri első változata. Az Apple iOS személyi asszisztens alkalmazása beszédfelismerés segítségével válaszol meg kérdéseket, tesz javaslatokat és végez műveleteket.


2010. október 6-án, 11 éve történt:
Elindult az Instagram okostelefonra kifejlesztett fénykép- és videómegosztásra szolgáló közösségi hálózat, alkalmazás.


1990. október 7-én, 31 éve történt:
Bejegyezték Magyarország internetes legfelső szintű tartomány kódját, a .hu domainvégződést.


1991. október 7-én, 30 éve történt:
Bejegyezték a Magyar Tudományos Akadémia Számítástechnikai és Automatizálási Kutatóintézet domainnevét. Ez volt az első magyar domain.


2008. október 7-én, 13 éve történt:
Elérhetővé vált Svédországban a Spotify ingyenesen is használható, kereskedelmi zene-streamelő szolgáltatás. Ma már minden népszerű platformon hozzáférhető.


2011. október 12-én, 10 éve történt:
Elhunyt Dennis M. Ritchie amerikai számítógéptudós. Legismertebb a C programozási nyelv kifejlesztéséről, és a UNIX operációs rendszer kifejlesztésében is komoly érdemei voltak.


1985. október 14-én, 36 éve történt:
Bjarne Stroustrup dán informatikus mérnök, a C++ programnyelv kidolgozója kiadta a nyelvhez írt első kézikönyvet (The C++ Programming Language), ami azóta 4 kiadást ért meg.


1956. október 15-én, 65 éve történt:
Megjelent az első magasszintű programozási nyelv első kézikönyve, ami rögzítette a szintaktikáját és működését. A Fortran nyelvet John Backus csapata fejlesztette ki az IBM 704 nagygép programozására.


2009. október 22-én, 12 éve történt:
A Microsoft Corporation kiadta a Windows 7 operációs rendszert, és elkötelezte magát amellett, hogy 10 évig terméktámogatást nyújt hozzá.


2008. október 23-án, 13 éve történt:
A Google elindította az Android Market (2012-től neve Google Play) digitális tartalomszolgáltatását, amely online alkalmazásboltot és felhőbeli médialejátszót jelent.


2001. október 25-én, 20 éve történt:
Két alapváltozatban is (Professional és Home Edition) megjelent a Microsoft Windows XP operációs rendszer, magyar nyelven is.


2009. október 27-én, 12 éve történt:
Ezen a napon jelent meg hivatalosan a League of Legends nevű ingyenesen elérhető valósidejű stratégiai játék, mely az egyik legsikeresebb a MOBA típusú videojátékok között.


1955. október 28-án, 66 éve történt:
Megszületett Bill Gates amerikai üzletember, szoftverfejlesztő, feltaláló, filantróp, a világ egyik leggazdagabb embere, a Microsoft Corporation alapítója.


1969. október 29-én, 52 éve történt:
Elküldték az ARPANET hálózaton, kísérleti jelleggel az első elektronikus levelet, az e-mailt. Ray Tomlinson vezette be a @ jelet, amellyel elválasztotta a felhasználó nevét és a gép nevét.