Keresési feladatok

Olyan problémákkal foglalkozunk, amikor egy adathalmazban meg kell keresni a legnagyobb, legkisebb, második legnagyobb, stb. elemet. Fő célunk alsó becslések keresése. Egy tipikus eredmény a következő:

A minimális és maximális elem együttes megkereséséhez n elem közül legalább \frac{3n}{2} − 2 összehasonlítás kell,

Érintjük n elem rendezéséhez szükséges műveletek számára vonatkozó becslést, és

azt a meglepő eredményt is, hogy n elemet lehet O (\frac{n log n}{log log n}) művelettel is rendezni.

Ha marad idő, az alábbi feladatot is megoldjuk:

Egy matematikai kongresszuson 200 küldött vesz részt, ezek mindegyike vagy őrült vagy normális. A normális matematikusok mindig igazat mondanak, az őrültek megbízhatatlanok: válaszuk lehet igaz is és hamis is. A résztvevők többsége normális. Egy újságírónak meg kell tudnia, hogy kik a normálisok. E célból bárkihez odamehet és megkérdezheti rámutatva valaki másra: “Ő normális vagy őrült?” Választ mindig kap, és ennek igazsága attól függ, hogy a kérdezett normális-e vagy sem.

Hány kérdést kell feltennie ahhoz, hogy mindent megtudjon?

Mutassuk meg, hogy ha n résztvevő van, és a többség normális, akkor konstans ×n kérdés elegendő ehhez. Ha ugyanannyi a normális és az őrült résztvevők száma, akkor lehetetlen akárhány kérdés segítségével biztosan kideríteni az igazságot. Annak pontos meghatátozása, hogy hány kérdés kell legalább a helyzet tisztázásához, (ha több a normális mint az őrült), lényegesen nehezebb, de megoldható probléma.

Csirmaz László

Feladatok

1. Egy kieséses versenyben n résztvevő közül eldöntik, hogy ki a harmadik legjobb. Hány mérkőzésre kerül sor? És ha a k-adik legjobbra vagyunk kiváncsiak?

2. A következő algoritmus kiválasztja a legnagyobb és a második legnagyobb értéket L[1], …, L[n] közül. Hány összehasonlítást végez a legrosszabb esetben, illetve átlagosan?

max: = max{L[1], L[2]};

second: = min{L[1], L[2]};

for i := 3 to n do if L[i] > second then

if L[i] > max then second: = max; max: = L[i]; else second: = L[i];

3. Mutassuk meg, hogy 5 elem közül a középsőt 6 összehasonlítással mindig ki lehet választani.

4. n elem közül a 10 legkisebb bármelyike jó. Hány összehasonlítással tudunk egy ilyet találni?

5. Az M n × n mátrix minden sorában az elemek csökkennek, és minden oszlopában az elemek szintén csökkennek. Meg kell állapítanunk, hogy egy x szám szerepel-e a mátrixban. Egy lépésben x-et összevethetjük M tetszőleges elemével, és megkapjuk, hogy egyenlő, kisebb vagy nagyobb-e nála. Hány lépést kell tennünk?

6. Egy útkereszteződéshez érünk, ahol az egyik út a pokolba a másik pedig a paradicsomba vezet. Az úton három ikertestvér áll, akik minden igen vagy nemmel megválaszolható kérdésre válaszolnak. Egyikük mindig igazat mond, a második mindig hazudik. A harmadik testvér süket, de ezt titkolja, azaz mindig válaszol valahogy a kérdéstől teljesen függetlenül. Állapítsuk meg két kérdés segítségével azt, hogy melyik út vezet a paradicsomba.