szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 lip 2011, o 00:02 
Użytkownik

Posty: 2
Lokalizacja: Warszawa
Witam, to mój pierwszy post na forum, szczerze mówiąc nie mam zbyt dużego pojęcia o matematyce, ale
męczy mnie ostatnio pewien problem teoretyczny - mam nadzieję, że z grubsza pasuje do tego działu :)

Problem wygląda tak:

Mamy zbiór n obiektów. Wśród tych obiektów jest jeden, który posiada jakąś unikalną właściwość - naszym zadaniem jest określenie który z obiektów posiada tą właściwość. Poszukiwany obiekt możemy wykryć poprzez przeprowadzenie dowolnej liczby tzw. testów. Jeden test możemy przeprowadzić na dowolnym podzbiorze obiektów. Wynikiem testu jest informacja, czy w testowanej grupie jest poszukiwany obiekt czy nie.

Czyli przykładowo jeśli przetestujemy cały zbiór na raz, to otrzymamy informację że poszukiwany obiekt jest wśród nich. Jeśli podzielimy zbiór na dwie części i dla każdej przeprowadzimy jeden test, to otrzymamy informację, w której z tych części jest obiekt etc.

Teraz pytanie: Jaka jest strategia pozwalająca wykryć poszukiwany obiekt w jak najmniejszej liczbie testów. I ewentualnie drugie pytanie - jak zmieni się strategia, jeśli w zbiorze będzie więcej niż jeden poszukiwany obiekt? Czy da się to opisać jakimś uniwersalnym wzorem?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 2 lip 2011, o 01:57 
Użytkownik

Posty: 693
Lokalizacja: Warszawa
dzieląc na połowy obszar poszukiwania chyba jest najefektywniej
Góra
Mężczyzna Offline
PostNapisane: 2 lip 2011, o 12:00 
Gość Specjalny

Posty: 4094
Lokalizacja: Łódź
Dodam tylko, że można to łatwo uzasadnić: przedstawiamy proces poszukiwania elementu wsród n- elementowego zbioru w postaci drzewa decyzyjnego. Będzie to oczywiście drzewo binarne (szczególny element jest albo w przetestowanej, albo w nieprzetestowanej części). Oczekujemy n możliwych wyników (pierwszy element, jest szczególny, drugi element jest szczególny, ...,n - ty element jest szczególny), które będą stanowić liście drzewa.

Niech h będzie wysokością tego drzewa. Z jednej strony, h \ge \lceil \log _{2}n\rceil (taką co najmniej wysokość musi mieć drzewo binarne o n liściach). Z drugiej strony, stosując właśnie strategię dzielenia na pół, otrzymamy (w najgorszym przypadku) pełne drzewo binarne o wysokości h = \lceil \log _{2}n\rceil.
Góra
Mężczyzna Offline
PostNapisane: 2 lip 2011, o 20:17 
Użytkownik

Posty: 2
Lokalizacja: Warszawa
Nieźle - dziękuję bardzo :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Suma elementów zbioru - zadanie 2  Rafsaf  2
 podzbiory zbioru n elementowego  Gogeta  7
 5 pytań ze zbioru 37  Bady  6
 5-elementowe podbioru zbioru 11-elementowego  elpopo  1
 Zliczanie liczb o określonych własnościach ze zbioru  Marthol  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl