Dobre i złe komputery

[dr.bo]

Na odległej stacji kosmicznej znajduje się N komputerów, na skutek wypadku
część z nich uległa uszkodzeniu. Wiemy, że liczba komputerów dobrych jest
większa niż złych, niestety nie znamy stanu żadnego konkretnego komputera.
Uszkodzenie jest dość subtelne, jedynym sposobem wykrycia go jest
przetestowanie komputera za pomocą innego komputera. Program testujący daje
odpowiedź "dobry" albo "zły". Dobry komputer zawsze prawidłowo określa stan
komputera badanego, odpowiedź złego komputera może być błędna.
Twoim zadaniem jest znalezienie jednego dobrego komputera, który umożliwi
sterowanie stacją, inaczej na zawsze oddali się ona w przestrzeń kosmiczną.
Trzeba to zrobić za pomocą jak najmniejszej liczby testów, gdyż są one
długotrwałe, a czas ucieka.
Do dzieła!

[Gość: Krzyś]

wydaje mi się, że od N=3 do N=8 wystarczą dwa testy. Potem dla N=9 i N=10 trzy itd.

[dr.bo]

Mam gorszą odpowiedź, ale może moje rozwiązanie nie jest optymalne, a może
niejasno przedstawiłem zasady...
Zgadzam się, że dla N<5 wystarczą dwa testy, ale jak to zrobić dla 5 albo tym
bardziej dla 8 komputerów - nie wiem.

Pamiętajmy, że nie jesteśmy w stanie przewidzieć, jak zachowa się zły komputer,
nie ma na to żadnej reguły. Może odpowiedzieć prawidłowo albo nie.

Bardzo proszę o szczegóły Twojego rozwiązania, wystarczy dla N=5. Albo przyznam
ci rację, albo doprecyzuję zadanie. Pozdrawiam.

[Gość: ala001]

Pewnie nie optymalne ale podam:
Biorę pierwszy badam wszystkimi (lub do momentu uzyskania min n/2
takich samych wyników). Jeśli wyników jest że dobry - tzn że dobry.
Inczej - zły - biorę do testów następny. Optymistycznie znajdę w N-
1, pesymistycznie najpierw wybiorę wszysztkie zepsute a w N/2-1
wyborze trafię na dobry
optymistycznie - N-1 - bardzo optymistycznie N/2
pesymistycznie SUMA (N-1, n-2, ...N/2-1)

[Gość: Tatabasi]

Hm. Zły komputer może podać błędny wynik.

Pozdrawiam,
Tatabasi

"Nawet zepsuty zegar dwa razy na dobę wskazuje dobrą godzinę"

[dr.bo]

Rozwiązanie Ali jest dobre, ale daleko mu do optymalnego. Jeżeli przetestujemy
dany komputer grupą komputerów, z których większość jest dobra, to większość
odpowiedzi będzie prawidłowa. Wyjątkowy pech może sprawić, że pierwsza seria
testów skończy się remisem, wtedy najlepiej zmienić testowany komputer. Trzeba
będzie wykonać dużo testów, ale to już coś, gratuluję i proszę próbować dalej.
Pozdrawiam.

[Gość: ala001]

czy zepsuty komp analizując jeden konkreteny np dobry zawsze daje
ten sam wynik czy może dać raz ok raz zły?

[dr.bo]

Gość portalu: ala001 napisał(a):

> czy zepsuty komp analizując jeden konkreteny np dobry zawsze daje
> ten sam wynik czy może dać raz ok raz zły?

Kto wie, może tak, a może nie... Może każdy zachowuje się inaczej? Może jeden
mówi zawsze prawdę a inny zawsze kłamie? Może skłamie za setnym razem albo
złośliwie daje takie odpowiedzi, żeby testy trwały jak najdłużej? Nie wiadomo.
Musimy to wszystko uwzględnić.

O zepsutym komputerze wiemy tylko dwie rzeczy:
1. Nie nadaje się do sterowania stacją.
2. Może dać nieprawidłowy wynik testu.

[smiechowiec]

dr.bo napisał:
>Wyjątkowy pech może sprawić, że pierwsza seria
> testów skończy się remisem,
>wtedy najlepiej zmienić testowany komputer.
Niby dlaczego ?
Wiedząc, że liczba dobrych komputerów jest większa niż złych mamy pewność co do każdego komputera.
W takim wypadku testowany komputer jest dobry,
te które wskazują, że jest dobry, również są dobre,
te które wskazują, że jest niedobry, są niedobre.
Liczba testów w tym przy przypadku to N - 1.
Jeżeli testujemy w ten sposób dobry komputer wtedy od razu uzyskujemy odpowiedź.
W przypadku testu dobrego komputera wystarczająca liczba poprawnych odpowiedzi to N/2, natomiast dla nieprawidłowego N/2 +1.
Jeżeli w czasie takiego testu uzyskamy kilka innych odpowiedzi to komputery, które je udzieliły zostają wyeliminowane gdyż na pewno są niedobre.
W związku z tym najmniej korzystny wariant to taki, w którym uzyskujemy N/2 + 1 odpowiedzi niepoprawnych i żadnej innej.
Wtedy eliminujemy tylko 1 komputer.
Maksymalna liczba sprawdzeń w tym przypadku wynosi
SUMA (N/2 + 1, n/2, ...N/4 + 1)

Chyba lepszą metodą byłoby zastosowanie testów parami i odrzucenie za każdym razem całych par, w których test wykazał, że komputer jest niesprawny.

[kornel-1]

smiechowiec napisał:
> Chyba lepszą metodą byłoby zastosowanie testów parami i odrzucenie za
każdym razem całych par, w których test wykazał, że komputer jest niesprawny.

Para (B,B) jest nieodróżnialna od (G,G). Podobnie para (B,G) jest nieodróżnialna od (G,B).
Przynajmniej dopóki nie masz komputera-próbnika. Ale gdy go masz - już nie musisz nic robić ;-)

Kornel

[smiechowiec]

kornel-1 napisał:
> Para (B,B) jest nieodróżnialna od (G,G).
>Podobnie para (B,G) jest nieodróżnialna od (G,B).
To nie ma znaczenia.
Wiemy, że komputerów dobrych jest więcej niż złych i to wystarczy.
Przy każdej eliminacji par, w których przynajmniej jeden komputer jest zły
zmniejszamy liczbę testowanych maszyn i cały czas zachowujemy większą liczbę
komputerów dobrych.

Można zrobić np tak
1. Łączymy komputery w pary testujący (A) i testowany (B) i testujemy
2. odrzucamy wszystkie pary, w których wynik jest zły
bo w przypadku 2 dobrych wynik będzie dobry, w każdym innym przypadku
przynajmniej jeden komputer jest zepsuty.
3. Jeżeli zostały pary, zamieniamy role komputerów A i B i ponownie testujemy
4. odrzucamy wszystkie pary, w których wynik jest zły
Nawet jeśli w wyniku tych 2 testów nie odpadnie żaden komputer to teraz już
wiemy, że zostały nam jedynie pary GG lub BB.
Zatem możemy odrzucić, z każdej pary po 1 komputerze, a w pozostałej części
liczba komputerów dobrych będzie nadal większa.
Czynność powtarzamy (2 testy A->B, B->A, i odrzucenie połowy komputerów) aż do
skutku.
W pesymistycznym wariancie mamy 2 * (N/2) * ln(N) testów
(logarytm przy podstawie 2)


Zostają nam teraz tylko pary

[dr.bo]

Bardzo mi się podoba to rozwiązanie, ale mam trochę lepsze. Moje rozwiązanie
również wykorzystuje regułę:

Jeśli wynik testu brzmi "zły" - wyrzuć obydwa komputery.

Niby jasne, ale nie oczywiste, nawet Kornelowi to umknęło. Duży punkt dla
Śmiechowca.

[dr.bo]

smiechowiec napisał:

> dr.bo napisał:
> >Wyjątkowy pech może sprawić, że pierwsza seria
> > testów skończy się remisem,
> >wtedy najlepiej zmienić testowany komputer.
> Niby dlaczego ? (...)

Masz rację, pomyliłem się. Remis to jedna z lepszych rzeczy, jaka może się
trafić. Testowany komputer jest wtedy dobry.

> Chyba lepszą metodą byłoby zastosowanie testów parami i odrzucenie za każdym ra
> zem całych par, w których test wykazał, że komputer jest niesprawny.

Myślę, że to jest słuszna koncepcja.

[hetman_sloniowy]

Dobra zagadka. Odpowiadam: potrzeba N testów (dla N>2).

Numerujemy (ustawiamy kolejno) komputery od 1 do N. Używamy pierwszego komputera
do przetestowania drugiego, drugiego do przetestowania trzeciego, trzeciego do
czwartego itd. aż, na koniec, ostatnim N-tym komputerem przetestujemy pierwszy.

Podczas tych operacji zapisujemy kolejno wyniki testów.

Wiemy, że więcej jest sprawnych komputerów niż niesprawnych. Zatem odpowiedź
'DOBRY!' musi paść co najmniej jedna, bo dwa sprawne komputery muszą stać obok
siebie (załóżmy nawet, że ustawione są w przeplatankę: dobry, zły, dobry, zły...
- żeby warunek był spełniony, gdzieś przerwana być musi).


Wiedząc o tym i mając zapisany ciąg wyników testów, wystarczy znaleźć jedną taką
odpowiedź 'DOBRY!', która, jeśli założylibyśmy, że udzielił jej komputer
niesprawny, doprowadziłaby nas do wniosku, że układ komputerów był niemożliwy do
zrealizowania. Komputer, który udzielił takiej odpowiedzi 'DOBRY!' jest sprawny.

[hetman_sloniowy]

Spostrzegłem, że jednak powyższy sposób jest ułomny. Mianowicie: może zajść
sytuacja, gdzie kilka odpowiedzi 'DOBRY!' będzie 'podejrzanych'.

(D - odpowiedź sprawnego komputera 'DOBRY!', Z - odpowiedź sprawnego komputera
'ZŁY!', '_' - odpowiedź niesprawnego komputera).

Dajmy na to:

DZ_DZ_DZ_
Nie dowiemy się które 'D' jest 'sprawne', bo np. schemat _Z_DZ_DZ_ też spełnia
warunki zadania.

Natomiast po przeprowadzeniu drugiej serii testów w przeciwnym kierunku,
podejrzewam, że powinno już się udać (czyli: 2N). Być może wystarczyłoby
przyjrzeć się odpowiedziom w 'newralgicznych' punktach po pierwszej serii testów.

Zestawiam możliwości dla dwóch komputerów (pierwsza literka to odpowiedź
komputera x testującego x+1, a druga - odwrotnie)

DD - obydwa są sprawne albo obydwa nie są sprawne,
DZ - x jest niesprawny, a x+1 - nie wiadomo,
ZD - x+1 jest niesprawny, a x - nie wiadomo,
ZZ - minimum jeden nie jest sprawny.

Na podstawie tylu informacji, sądzę, że już powinno się dać wywnioskować, który
komputer jest dobry, ale na razie odkładam tą zagadkę 'na później', bo już się
dość nagłówkowałem. :-)

[dr.bo]

Odpowiedź 2N to by było coś, muszę przeanalizować twoje rozwiązanie, zwłaszcza,
że jest nieco podobne do mojego. Tymczasem mam coraz więcej wątpliwości, czy mój
sposób jest lepszy od rozwiązania Śmiechowca. O ile się nie mylę to u mnie w
najbardziej pesymistycznym wariancie trzeba będzie wykonać
((N/2)-1)*N/4
prób. Dla 100 komputerów jest to 1225 testów co prawda przy wyjątkowym pechu,
ale to nieistotne. Dla większych liczb jest to bliskie N^2/8, czyli sporo, chyba
więcej niż u Śmiechowca. Jeżeli znajdę trochę czasu to jutro to przeanalizuję.

[hetman_sloniowy]

Wypisuję garść spostrzeżeń dot. sytuacji gdy 'bohater' łamigłówki głowi się nad
ciągiem odpowiedzi (pierwszym: od 1 do N). A nuż się przyda.

(D - odpowiedź sprawnego komputera: 'DOBRY!'; Z - odpowiedź sprawnego komputera:
'ZŁY!'; '_' - odpowiedź niesprawnego komputera)

- po 'D' może być 'D' albo 'Z'
- przed 'D' nie może być 'Z'
- po 'Z' może być tylko '_'
- przed 'Z' nie może być 'Z'
- po '_' może być cokolwiek
- przed '_' nie może być 'D'

oraz

- skoro musi być jedno 'D' to, wyjąwszy przypadek z samymi odpowiedziami 'D',
musi paść też min. 1 odpowiedź 'Z' podana przez sprawny komputer.

Np. dla ciągu 'ZDZDD' wiadomo, że ostatnie 'D' to właśnie odpowiedź sprawnego
komputera.

[smiechowiec]

Wydaje mi się, że rozwiązanie Hetmana ma największe szanse, aby być optymalnym,
trzeba je jedynie dobrze opisać.
Podam może rozwiązanie, które podał kiedyś Pan Fabiański (znalezione w internecie).
1. Łączymy komputery w pary.
2. W każdej parze oznaczamy jeden komputer A drugi B,
komputer A testuje komputer B
3. W przypadku wyniku błędny odrzucamy obie maszyny z puli testowej
W przypadku wyniku dobry odrzucamy z puli testowej komputer A.
4. Jeżeli jeden komputer nie brał udziału w teście w czasie danej kolejki to
zostawiamy go w przypadku parzystej liczby pozostałych komputerów tak, aby ich
całkowita liczba była nieparzysta.
5. Komputer 1 lub 2, które zostaną po wszystkich próbach można uznać za dobre.

Słyszałem, od kolegi, że w ogólnym przypadku możliwe jest znalezienie 1 dobrego
komputera z N jeśli przynajmniej 2 są sprawne, ale jeszcze nie wiem jak tego
dokonać.
Jeśli ktoś ma jakiś pomysł to zapraszam do dyskusji.

[republican]

smiechowiec napisał:

> Wydaje mi się, że rozwiązanie Hetmana ma największe
szanse, aby być optymalnym,
> trzeba je jedynie dobrze opisać.
> Podam może rozwiązanie, które podał kiedyś Pan
Fabiański (znalezione w internec
> ie).
> 1. Łączymy komputery w pary.
> 2. W każdej parze oznaczamy jeden komputer A drugi
B,
> komputer A testuje komputer B
> 3. W przypadku wyniku błędny odrzucamy obie maszyny
z puli testowej
> W przypadku wyniku dobry odrzucamy z puli testowej
komputer A.
> 4. Jeżeli jeden komputer nie brał udziału w teście
w czasie danej kolejki to
> zostawiamy go w przypadku parzystej liczby
pozostałych komputerów tak, aby ich
> całkowita liczba była nieparzysta.
> 5. Komputer 1 lub 2, które zostaną po wszystkich
próbach można uznać za dobre.
>
> Słyszałem, od kolegi, że w ogólnym przypadku
możliwe jest znalezienie 1 dobrego
> komputera z N jeśli przynajmniej 2 są sprawne, ale
jeszcze nie wiem jak tego
> dokonać.
> Jeśli ktoś ma jakiś pomysł to zapraszam do dyskusji.

Masz na mysli zly a nie bledny w:
3. W przypadku wyniku błędny odrzucamy obie maszyny z
puli testowej
Zgadzam sie z konceptem sita logicznego ktore
eliminuje niepewne osobniki.
Ja bym polaczyl ostatnia trojke a nawet piatke w
uklad Modular Redundancy.

[hetman_sloniowy]

Ponieważ nie potrafię udowodnić, że moje rozwiązanie jest poprawne (a właściwie:
pomysł na rozwiązanie), to napiszę je w formie pytania. Proszę zatem nie
wgłębiać się w to co pisałem wcześniej :-).

Przeprowadzono dwie serie testów komputerów.

W pierwszej użyto komputera nr 1 do testowania komputera nr 2, komputera nr 2 do
testowania komputera nr 3, nr 3 do nr 4, nr 4 do nr 5, itd., aż użyto N-tego do
przetestowania komputera nr 1.

W drugiej postępowano przeciwnie: komputer N-ty testował komputer o nr N-1,
komputer o nr N-1 ten z nr N-2, itd., aż komputer nr 2 testował nr 1, a nr 1
testował komputer N-ty.

Czy użytkownik komputerów ('bohater' zagadki) będący bezbłędnym logikiem
(nawiasem mówiąc: mającym mózg jak super-komputer) na podstawie otrzymanych
wyników testów zawsze będzie mógł wskazać jednoznacznie co najmniej jeden
sprawny komputer?

O zadaniu Śmiechowca pomyślę jutro w autobusie :-)

[hetman_sloniowy]

smiechowiec napisał:

> Słyszałem, od kolegi, że w ogólnym przypadku możliwe jest znalezienie 1 dobrego
> komputera z N jeśli przynajmniej 2 są sprawne, ale jeszcze nie wiem jak tego
> dokonać.
> Jeśli ktoś ma jakiś pomysł to zapraszam do dyskusji.

Moim zdaniem, nie jest to możliwe.

Otrzymamy maksimum możliwych informacji, jeśli przeprowadzimy testy na zasadzie
"każdy z każdym" (czyli (N^2-N) testów). Dla tych dwóch sprawnych komputerów
sytuacja będzie następująca: ocenią siebie wzajemnie jako 'DOBRE', a pozostałe
jako 'ZŁE'. Dokładnie taka sama sytuacja może mieć miejsce dla pary niesprawnych
komputerów. I jak teraz odróżnimy jedną parę od drugiej? Możemy liczyć tylko na
łut szczęścia, który sprawi, że takiej pary nie będzie, albo przeprowadzać
kolejne testy i czekać aż niesprawne komputery wykażą się 'niekonsekwencją'.

Problem ten nie istnieje dla N=3.

Podejrzewam, że gdy ilość sprawnych komputerów jest większa niż 2, to problem
przedstawia się analogicznie - nie dotyczy par, a 'trójek', 'czwórek' itd.

[Gość: Krzyś]

dla N=5 i wiedzy, że minimum 3 kompy są dobre, mam niestety aż 4 sprawdzenia
następującą metodą:

w górnym rzędzie układamy dwa kompy, w dolnym trzy. Komputer 1 u góry sprawdza
dolny lewy i środkowy , komputer 2 - środkowy i dolny prawy.

Przy różnych sekwencjach odpowiedzi górnych komuterów powinda się, że da się
jednoznacznie ustalić który z dolnych komputerów, czyli albo środkowy, albo
jeden z brzegowych jest na 100% dobry.

Być może ta metoda będzie mogła być wykorzystana przy większym N?

[republican]

Prosze o wyjasnienie
Prosze sprezyzowac:
"Dobry komputer zawsze prawidłowo określa stan
komputera badanego, odpowiedź złego komputera może
być błędna."
Czy mozemy polegac na prawidlowej interpretacji
odpowiedzi otrzymanej przez zlego komputera?

[Gość: grzesiek]

Przy pomocy K1 testuję K2. Jeśli wynik jest ZŁY, to odrzucam oba.
Jeśli DOBRY, to odrzucam K1. Zatem w każdym kroku odrzucam
co najmniej jeden komputer. Tak robię, aż zostaną tylko dwa.
Nie trzeba dalej testować bo wiadomo że oba są dobre.
Wykonałem więc co najwyżej N-2 testów.

[Gość: grzesiek]

Wycofuję się z tego co przed chwilą napisałem. To oczywiście jest zła
metoda, bo pozbywam się dobrych komputerów nie usuwając jednocześnie
złych.

[Gość: grzesiek]

W każdym i-tym kroku mam Ni komputerów. Jeśli Ni jest nieparzyste,
to jeden z nich odstawiam na bok i wiem że w pozostałych Ni-1 jest
co najmniej połowa dobrych. Oznaczam przez Pi połowę Ni, czyli Ni/2
lub (Ni-1)/2. Pierwsze Pi będą komputerami testującymi, następne Pi
testowanymi. Przeprowadzam Pi testów. Jeśli wynik jest ZŁY, to
odrzucam oba - testujący i testowany. Jeśli wynik jest DOBRY, to
odrzucam tylko komputer testujący. Mogę tak zrobić, bo wśród
komputerów nieodrzuconych pozostanie co najmniej połowa dobrych.

Dowód jest prosty: złe nieodrzucone musiały być testowane przez złe
komputery testujące, skoro wynik był DOBRY. Ponieważ całkowita
liczba złych to co najwyżej Pi, to w nieodrzuconych jest ich co
najwyżej Pi/2.

Na koniec kroku dołączam ew. nieparzysty z powrotem do zbioru
nieodrzuconych. Tak więc w jednym kroku, po wykonaniu Pi testów
odrzuciłem co najmniej Pi komputerów pozostawiając N[i+1] = Ni - Pi
do następnego kroku testowania.

W efekcie przeprowadzam maks. N-2 testów.

[republican]

Grzesiek,
Doszedles do tej samej odpowiedzi, ktora podal u gory
Smiechowiec, a ktora ja skromnie poparlem.
Panie Doktorze, czekam na opinie.
Pozdrawiam Was
R
PS
Co sadzicie o Modular Redundancy w tym wypadku?

[Gość: grzesiek]

> Grzesiek,
> Doszedles do tej samej odpowiedzi, ktora podal u gory
> Smiechowiec, a ktora ja skromnie poparlem.

Zgadza się, nie doczytałem dokładnie.