Zad. 1. Kto zaprojektował pierwszy komputer do gry w szachy?
Zad. 2. Odpowiedz na pytania (matematyczne):
a) Czy istnieje drzewo bez liści?
b) Czy istnieje liść bez drzewa?
c) Czy drzewo może mieć same liście?
d) Czy drzewo może mieć dowolną liczbę liści?
Zad. 3. Komputer wykonuje następujący algorytm:
dopóki liczba jest większa niż 9,
zamieniaj ją na sumę jej cyfr.
Podaj największą liczbę 3-cyfrową, dla której ten algorytm wykona najwięcej zamian.
W tym miesiącu punkty zdobyli:
- 2,5 - Krystyna Lisiowska - redaktor z Warszawy, Michał Lorenz - manager IT z Mikołowa, Kasper Przenzak - analityk ryzyka z Krakowa,
- 2 - Oliwia Makuch - studentka PWr, Szymon Meyer - analityk danych z Dziewkowic, Marzena Wąsiewicz - nauczycielka matematyki z Kajetan.
Zad. 1. Pierwszy komputer grający w szachy zaprojektował polski matematyk Stanisław Ulam. Był to... MANIAC I, a Ulam kierował zespołem jego programistów. Komputer ten powstał w ramach projektu Manhattan i był wykorzystywany w ośrodku badań jądrowych w Los Alamos, głównie do pomocy przy projektowaniu bomby wodorowej, ale tam właśnie jako pierwszy rozegrał partię szachów z człowiekiem w 1956 roku.
Historia maszyn przeznaczonych do gry w szachy jest jednak znacznie starsza niż historia komputerów.
- Charles Babbage już w 1846 roku rozważał możliwości nauczenia gry w szachy jego niedokończonej nigdy mechanicznej maszyny liczącej "Analytical Engine".
- Pierwszą maszynę analogową, która potrafiła w ograniczonym stopniu grać w szachy (rozwiązywała proste końcówki szachowe), stworzył w roku 1890 roku hiszpański inżynier i matematyk Leonardo Torres y Quevedo.
- W 1951 roku Alan Turing napisał pierwszy program do gry w szachy, ale nie miał wówczas dostępu do odpowiedniej maszyny liczącej, aby go zaimplementować.
- Pierwszym programem szachowym uruchomionym na komputerze (Ferranti Mark 1) był napisany w 1952 roku przez niemieckiego pioniera komputerów Dietricha Prinza program do rozwiązywania końcówek szachowych.
- W 1957 roku amerykański matematyk i szachista Alex Bernstein stworzył pierwszy w pełni zautomatyzowany silnik szachowy dla komputera lampowego IBM 704.
Od tej pory komputery szybko pięły się w górę w rankingach szachowych.
- Pierwszy program szachowy, który pokonał człowieka (początkującego gracza), powstał w 1958 roku. Był to program NSS opracowany przez Allena Newella, Herberta Simona i Cliffa Shawa, działał na komputerze JOHNNIAC. Zastosowano w nim elementy heurystyki. Zamiast mechanicznego przeszukiwania wariantów, analizował on wybór najlepszej potencjalnej zagrywki.
- W 1967 roku komputer pierwszy raz wygrał z niezłym szachistą za sprawą programu Mac Hack VI napisanego przez amerykańskiego programistę Richarda Greenblatta.
- W 1977 roku Ken Thompson i Joe Condon z Bell Laboratories stworzyli maszynę Belle (podpiętą do minikomputera) dedykowaną grze w szachy. Osiągnęła ona poziom gry mistrza FIDE.
- W 1997 roku komputer Deep Blue po raz pierwszy wygrał z mistrzem świata Garrim Kasparowem.
- Współczesne silniki szachowe są o wiele mocniejsze od ludzi. Aktualny mistrz świata legitymuje się rankingiem 2830 punktów elo, a siła gry najlepszych silników szachowych szacowana jest powyżej 4000 elo.
Zad. 2. Matematyczne drzewo to graf spójny bez cykli, a liść to wierzchołek grafu, którzy ma rząd 1 (wychodzi z niego tylko jedna krawędź).
a) Nie. Drzewo ma zawsze liść (a właściwie ma zawsze dwa liście).
b) Tak, np. cykl z dodanym liściem. Jednak wg niektórych definicji liście występują tylko w drzewach, a w innych grafach w2ierzchołki rzędu 1 nazywają się końcami.
c) Tak, jeśli ma tylko 2 wierzchołki.
d) Nie. Nie może mieć jednego liścia. Poza tym może mieć każdą liczbą liści (np. gwiazdka o jednym wierzchołku rzędu n oraz n liściach).
Zad. 3. Największa liczba operacji dla liczb 3-cyfrowych wynosi 3, największa liczba wymagająca 3 operacji to 991.
