TechBlog cikkei
2013-08
Az n-edik racionális
Közismert, hogy a racionális számok megszámlálhatóak. A következő algoritmussal ugyanis fel tudjuk őket mind sorolni (az egyszerűség kedvéért, most csak a 0 és 1 közöttieket, a többiek negálással és invertálással adódnak):
- Legyen q=1.
- Legyen p=1.
- Ha p/q nem eleme a készítendő listának, tegyük bele.
- Ha p=q, akkor legyen q=q+1 és folytasd a 2. lépéstől. Különben legyen p=p+1.
Így előáll egy lista, ami tartalmazza az összes racionális számot 0 és 1 között. A kérdés: hogyan lehet meghatározni ennek a listának az n-edik elemét?
Nyilvánvaló, a fenti algoritmus egyben meg is határozza a lista elemeit, de ez az algoritmus O(n) nagyságrendű. A kérdés tehát az, hogy létezik-e (létezhet-e) olyan algoritmus, ami a lista n-edik elemét ennél gyorsabban (mondjuk O(ln(n)), esetleg O(1) rendben) képes meghatározni? Ja, a "felírom a listát egy papírra és kikeresem az n-edik elemet. O(1), nyertem" típusú megoldás nem játszik...
Faites vos jeux!
IE=hate
Tudjátok, miért utálom az Internet Explorert?
Egyebek között, ezért. (Figyelmeztetés: a link erősen károsíthatja az ön és környezete intellektuális békéjét.)
(Kis háttér: A napokban találkoztam a következő Apache direktívával, ami arra szolgál hogy az Internet Explorer kevésbé legyen hülye:)
<IfModule mod_headers.c>
Header set X-UA-Compatible "IE=edge"
# `mod_headers` can't match based on the content-type, however, we only
# want to send this header for HTML pages and not for the other resources
<FilesMatch "\.(appcache|crx|css|eot|gif|htc|ico|jpe?g|js|m4a|m4v|manifest|mp4|oex|oga|ogg|ogv|otf|pdf|png|safariextz|svgz?|ttf|vcf|webapp|webm|webp|woff|xml|xpi)$">
Header unset X-UA-Compatible
</FilesMatch>
</IfModule>