Budapesti Fazekas Mihály Gyakorló Általános Iskola és Gimnázium

FaceBook oldalunk

Látogatók

Mai717
Heti3438
Havi21195
Összes763785

IP: 54.80.219.236 Unknown - Unknown 2018. szeptember 19. szerda, 13:49

Ki van itt?

Guests : 69 guests online Members : No members online

Honlapok

SULINET Matematika

Oktatási Hivatal

Versenyvizsga portál
banvv

Matematika Portálok

Berzsenyi Dániel Gimnázium

berzsenyi

Óbudai Árpád Gimnázium
arpad

 

Szent István Gimnázium

sztistvan

A gondolkodás öröme
gondolkodasorome

Babai László: Számításelmélet

2005.március 20.

 

Babai László 2004. májusi előadása

Lejegyezte: Maga Péter.

 

Az elhangzott feladatokból:Babai László

Van n kövünk, különböző nehézségűek, a sorrendjüket szeretnénk minél kevesebb méréssel megállapítani, ahol egy mérés két kő nehézségének összehasonlítását jelenti. Bármely kettő összemérése nyílván jó, de ez n(n– 1)/2 mérés. Ennél jóval kevesebbel is meg lehet állapítani a sorrendet. Képzeljük el, hogy már néhány kő sorba van rakva, és egy újabbat szeretnénk a láncba beilleszteni. Ekkor felesleges minden eddigi kővel összemérni, hiszen a nehézség (mint reláció) tranzitív tulajdonsággal rendelkezik. Ha tehát például az új követ a középsővel (vagy „majdnem” középsővel) összemérjük, és annál nehezebbnek / könnyebbnek találjuk, akkor már a kövek felénél biztosan nehezebb / könnyebb...

 

  Megtekintés Letöltés
Feladatok versenyeken    

QR kód

Budapesti Fazekas Mihály Gyakorló Általános Iskola és Gimnázium

QR

 

 

 

Bejelentkezés cikkíróknak


Joomla template: szsnjm3-001
(c) Szoldatics József (www.szolda.hu), Eszesen KFt. 2011/2016