poniedziałek, 15 września 2008

Każdy ma takie dziecko, jakie sobie wychowa!

To niesamowite, jak aniołek będący pod opieką jednej osoby, potrafi nagle przeistoczyć się w diabełka w obecności innej. Wychowanie to również walka o władzę i hierarchię w stadzie. Dzieci doskonale wyczuwają, na co mogą sobie z kim pozwolić. Komu można wejść na głowę, a z kim żadne numery nie przejdą. Niekonsekwencja w przestrzeganiu zasad, ustępstwa przy próbach wymuszenia zabawek czy słodyczy, mogą nie wiadomo kiedy zmienić ukochaną mamusię w służącą przynoszącą kanapeczki latorośli przed tv czy komputerem. Kwestia ta jest jedną z pierwszych i oczywistych rzeczy, którą trzeba ustawić przy szkoleniu np. psa, rzadko zaś patrzymy pod tym kątem na ludzi, może jednak czasem warto :)?

poniedziałek, 8 września 2008

Rozwiązywanie Sudoku

Uwaga może odebrać przyjemność z gry!

W 2005 roku świat zwariował na punkcie Sudoku. Zasady łamigłówki są bardzo proste, wypełnij diagram 9x9 tak, aby w każdym wierszu, w każdej kolumnie i w każdym wyznaczonym kwadracie 3x3 znalazło się po jednej cyfrze od 1 do 9. Plansze do gry konstruowane są w taki sposób, by umożliwić znalezienie jedynego rozwiązania bez konieczności zgadywania żadnej z cyfr. Podstawy rozwiązywania, opisy rozszerzeń gry, rozgrywanych zawodów i inne ciekawostki dotyczące Sudoku znajdą Państwo na Wikipedii. W artykule chciałbym zaprezentować matematyczne podejście do problemu.

Jaką cyfrę należy wpisać w zaznaczone pole? Patrząc na diagram od razu widzimy łatwiejsze pola do uzupełnienia, ale można wypełnić i to na tym etapie gry.



Reguła 1. Do uzupełnienia tego pola skorzystamy z zasady, że cyfry nie mogą się powtarzać. Dla wiersza, kolumny i kwadratu w którym znajduje się nasze pole wypisujemy pozostałe do uzupełnienia cyfry, a następnie wyznaczamy cześć wspólną tych trzech zbiorów. Jeśli iloczyn zbiorów ma jeden element, to jest to poszukiwana cyfra. Tym sposobem udało nam się wyznaczyć dość groźnie wyglądające pole.



Reguła 2. Co jednak, gdy dla wszystkich jeszcze pustych pól mamy więcej niż jedną potencjalną odpowiedź wyznaczoną regułą 1. Wtedy korzystamy z zasady, że każda z cyfr musi się znaleźć w wierszu, kolumnie i kwadracie. Dlatego, pomimo że reguła 1 wskazuje na więcej niż jedną możliwość, możemy wyszukać pola, które jako jedyne w wierszu, kolumnie czy kwadracie mają w zbiorze możliwych rozwiązań daną cyfrę. Mówiąc bardziej precyzyjnie, dla każdego wiersza, kolumny, kwadratu i dla każdej z pozostałych w nich do uzupełnienia cyfr możemy wyznaczyć zbiór pól, które mogą zawierać daną cyfrę zgodnie z regułą 1. Jeśli ten zbiór zawiera jedno pole, to w to pole wpisujemy daną cyfrę.



Okazuje się, że korzystając tylko z tych dwóch prostych reguł, które wyprowadziliśmy z definicji gry, da się rozwiązać wszystkie łatwe i średnie diagramy, a nawet cześć trudnych. Metoda jest trochę pracochłonna, ale nie wymaga myślenia i doskonale nadaje się dla komputera. Żebyśmy nie popadli jednak za szybko w samozachwyt, pokażę przykład pola, którego w ten sposób nie wyznaczymy.



Ujęcie matematyczne kolejnej reguły i znalezienie następnych pozostawiam zainteresowanym jako pracę domową. W sieci nie brakuje gotowych aplikacji typu "sudoku solver", od prostych - podstawiających w kolejne pole losową "poprawną" cyfrę i wyocfujących się z błędnych strzałów, do bardzo zaawansowanych - pokazujących kolejne ruchy i reguły wnioskowania do nich użyte, pozwalających generować plansze do których rozwiązania trzeba użyć zadanych reguł, itp. Znajdywanie prostych i eleganckich reguł przenosi grę na wyższy poziom abstrakcji, ale zwykła gra może wtedy zacząć nudzić. Człowiek podczas rozwiązywania diagramu rozumuje inaczej, uproszczone reguły warto też stosować np. w zawodach na czas, z kolei takie metodyczne podejście może okazać się pomocne, gdy akurat utkniemy na łamigłówce.

sobota, 6 września 2008

Jaka pogoda będzie w wakacje?

Czyli krótko o teorii chaosu.

Dlaczego, pomimo ciągłego rozwoju nauk przyrodniczych i wzrostu mocy obliczeniowej komputerów, wciąż nie potrafimy przewidywać huraganów czy chociażby nie ma prognoz pogody na najbliższy rok, by optymalnie zaplanować sobie urlop lub plony w rolnictwie? Czemu synoptycy niechętnie podają prognozy długoterminowe, a ich trafność porównywalna jest z tymi od Bacy z reumatyzmem?

Wszystkiemu winien jest chaos deterministyczny, potocznie nazywany też efektem motyla, którego trzepot skrzydeł w Ohio po kilku dniach powoduje burzę piaskową w Teksasie. Czy zatem powinniśmy wytruć wszystkie motyle, by zapobiec przyszłym klęskom żywiołowym? W okół teorii chaosu narosło wiele mitów i legend, podsycanych przez hollywoodzkie produkcje z tajemniczymi geniuszami matematycznymi w rolach głównych. Na przykład w Parku Jurajskim Ian Malcolm dzięki teorii chaosu przewiduje mającą nastąpić katastrofę!?

Trudność w przewidywaniu pogody lub zmian klimatu nie leży wcale w złożoności obliczeniowej stosowanych algorytmów czy ogromnej ilości przetwarzanych danych, na to pomogłoby stosowanie rozwiązań przybliżonych lub poczekanie na szybsze komputery. Natura problemu jest bardziej złożona, istnieje pewna grupa układów, których zachowania nie jesteśmy w stanie przewidzieć w dłuższym czasie, znając poprawne równania je opisujące. Brzmi to dość tajemniczo, znamy teorię, ale nie jesteśmy w stanie jej praktycznie wykorzystać? Otóż to, do równań opisujących zachowanie układu w czasie trzeba wstawić wartości początkowe, te z kolei, jeśli pochodzą z otaczającej nas rzeczywistości, obarczone są błędem pomiaru (nie wspominam już nawet o zasadzie nieoznaczoności Heisenberga). Drobny błąd w danych początkowych z czasem wykładniczo rozrasta się do dowolnego zachowania układu, stąd porównanie do motyla i burzy. Daje to złudzenie losowego zachowania deterministycznego modelu, skąd z kolei nazwa teoria chaosu. Odkrycia tego dokonał Edward Lorenz, przypadkowo zaokrąglając pośrednie wyniki symulacji zjawisk pogodowych.

Może to lepiej, że pewnych rzeczy nie jesteśmy w stanie poznać z dużym wyprzedzeniem, życie stało by się wtedy takie nudne i trzeba by znaleźć inny dyżurny temat konwersacji niż pogoda.

Welcome!

I'm really happy that some of my foreign friends wanted to look at this blog with a little help of Google Translate. I know that the translation is not perfect, but my target audience for the personal stuff is Polish, sorry... Nevertheless I've put a Google Translare gadget on the blog to ease the translation.