„Skatulyaelv” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
alkalmazások: számítástechnika |
→Alkalmazások: analízis: a bizonyítás eleje |
||
20. sor:
A kézrázások lehetséges száma nullától ''n''-1-ig terjed, ''n''-1 skatulyát alkotva. Ez azért van, mert vagy a nullaszor, vagy az ''n''-1-szer kezet fogók halmaza üres, mivel, ha van, aki mindenkivel kezet fogott, akkor nem lehet senki, aki nem fogott kezet senkivel, és fordítva. Az ''n'' embert elosztva az ''n''-1 skatulya között lesz skatulya, ahova több ember kerül.
==Alkalmazások==
===Számítástechnika===
A [[számítástechnika|számítástechnikában]] is előkerül a skatulyaelv.
Például, mivel egy tömbnek kevesebb eleme van, mint ahány lehetséges kulcs, ezért nincs hashelő algoritmus, amivel el lehetne kerülni az ütközéseket. Egy másik példát a veszteségmentes tömörítő algoritmusok adnak, amik egyes fájlokat tömörítenek, másokat meg épp hosszabbá tesznek.
===Analízis===
A matematikai analízis egy fontos tétele szerint az α irracionális szám egész számú többszörösei tetszőlegesen közel kerülnek egy egész számhoz, sőt, ezeknek a számoknak a törtrészei sűrűek [0,1]-ben.
Elsőre ez nem nyilvánvaló, mert hogyan találjunk adott ε > 0-hoz olyan ''n'', ''m'' egész számokat, amikre |nα − m| < ε? A feladat azonban megoldható egy ''M'' > 1/ε választásával. A skatulyaelv szerint van n<sub>1</sub>, n<sub>2</sub>∈ {1, 2, ..., M + 1}, hogy n<sub>1</sub>α és n<sub>2</sub>α ugyanabba az 1/''M'' hosszú részintervallumba esik.
==Élesítés==
A skatulyaelv így élesíthető:
| |||