Michał R. Przybyłek

#SAT

Alternatywna wersja zadania zaliczeniowego

Napisać rozproszony program rozwiązujący problem #SAT - tj. na wejściu dostajemy formułę logiczną (można ograniczyć się do koniunkcji, alternatywy i negacji), a na wyjściu podajemy liczbę wartościowań spełniających tę formułę.

Blue and Yellow

W naszym świecie istnieją dwa podstawowe kolory - niebieski u i żółty y. Kolory można ze sobą mieszać: jeżeli A i B są kolorami, to operację domieszania do A koloru B zapisywać będziemy AB (przyjmiemy też konwencję ABC = (AB)C). Operacja mieszania kolorów nie jest łączna, ani przemienna - tj.: nie musi zachodzić (AB)C = A(BC), ani AB = BA. Ponadto zawsze spełnione są następujące równości na kolorach (dla dowolnych kolorów A, B, C):

uAB = A - tj. domieszanie do koloru niebieskiego koloru A, a później koloru B daje po prostu kolor A

yABC = (AC)(BC) - tj. domieszanie do koloru żółtego koloru A, później koloru B i na końcu koloru C, daje taki sam kolor jakby domieszać do A kolor C, a następnie domieszać domieszany do B kolor C

Powiemy, że kolory A, B są perspektywicznie równe, gdy istnieje taka liczba naturalna n, że dla każdego ciągu kolorów X_n zachodzi AX₁X₂...X_n = BX₁X₂...X_n.

Zdefiniujmy kolor przezroczysty i = yuu (do koloru żółtego dodajemy dwa razy kolor niebieski) i brunatny b = y(uy)u (do koloru żółtego dodajemy kolor, który powstał z domieszania do niebieskiego żółtego, i następnie dodajemy kolor niebieski). k-ty odcień naturalności k wprowadzamy rekurencyjnie:

0 = ui

k+1 = ybk

Przez natężenie koloru rozumieć będziemy minimalną liczbę podstawowych kolorów, które musimy zmieszać, aby otrzymać kolor perspektywicznie równy danemu.
Oczywiście natężenie kolorów podstawowych równe jest jeden. Łatwo sprawdzić, że natężenie 0-wego odcienia naturalności równe jest cztery. Wprost z definicji natężenie k-tego odcienia naturalności szacuje się przez 4 + 5*k. Jednak zazwyczaj jest o wiele niższe - np. 1XY = yb0XY = yb0XY = (bX)(0X)Y = (y(uy)uX)(uiX)Y = (uyX)(uX)iY = y(uX)iY = (uXY)(iY) = XY = iXY = yuuXY; stąd wynika, że 1 jest perspektywicznie równe yuu, a zatem natężenie 1-go koloru naturalności nie jest większe niż 3 (w rzeczywistości jest równe 3). Podobnie łatwo zauważyć, że 100 jest perspektywicznie równoważne b(10)(10), czyli szacuje się przez 112.

Zadanie zaliczeniowe

Napisać rozproszony program szacujący natężenia k-tych odcieni naturalności.

Gniazda UDP

Typowe sytuacje, gdzie protokół UDP ma zastosowanie to:

aplikacje generujące o wiele więcej danych niż jest się skłonnym przesłać, a wybór, które z generowanych danych akurat przesłać jest dość arbitralny (np. transmisje audio/wideo)
istnienie wielu odbiorców dla jednej wiadomości (np. broadcast, multicast), kiedy przesyłanie wielu kopii jest z jakichś względów niepraktyczne
ogólnie - konieczność sprawowania dokładnej kontroli nad transmisją danych (DHCP, DNS, serwery gier, ...)

W Javie gniazda UDP (zarówno unicastowe jak i broadcastowe; gniazdami multicastowymi nie będziemy zajmować się na zajęciach) reprezentowane są przez klasę DatagramSocket.

Możliwy scenariusz działania serwera wygląda następująco:

ustawienie gniazda datagramowego na znanym porcie; ewentualnie na pierwszym wolnym (konstruktor bezargumentowy) i przekazanie o tym informacji:
server = new DatagramSocket();

Przygotowanie datagramu do odbioru danych

buff = new byte[MAX_DATAGRAM_SIZE];
datagram = new DatagramPacket(buff, buff.length);

czekanie na pojawienie się datagramu
server.recive(datagram);
utworzenie osobnego wątku obsługującego klienta (i powrót do przygotowania do odbioru kolejnego datagramu)
new Thread() { //... public void run() { // obsługa klienta //... } }.start();

w prologu obsługi klienta pobranie informacji o gnieździe nadawcy datagramu i utworzenie datagramu do wysłania:

clientAddress = datagram.getAddress();
clientPort = datagram.getPort();
// przygotownie danych
// ...
datagram =  DatagramPacket(buff, buff.length, clientAddress, clientPort);

Podobnie wygląda obsługa klienta.

Jak ustalić wielkość datagramu?

Oczywiście zgodnie ze specyfiką problemu, który się rozwiązuje. Lepszym pytaniem jest: jakiej maksymalnej wielkości datagramy powinniśmy przesyłać? Prosta odpowiedź to: takiej aby datagramy mieściły się w buforach urządzeń znajdujących się na ścieżkach, którymi owe datagramy się poruszają - choć warstwa IP potrafi dzielić datagramy na fragmenty, zazwyczaj takie podziały prowadzą do sporych nieefektywności w komunikacji. Niestety, nie istnieje dobry sposób na określenie tej wielkości. Standard gwarantuje tylko 576 bajtów na datagram w warstwie IP - odejmując od tego 60 bajtów maksymlnej wielkości nagłówka IP (tj. 4 * (2^4 - 1)) i 8 bajtów wielkości nagłówka UDP, zostajemy z gwarantowaną obsługą 508 bajtów danych.

Gniazda TCP

Wyróżniamy dwa rodzaje gniazd TCP:

nasłuchowe - wykorzystywane po stronie aplikacji serwera do nawiązywania połączeń z klientami; takie gniazda są unikalnie identyfikowane przez adres hosta i numer portu, na którym stoją
połączeniowe - wykorzystywane do wymiany danych; takie gniazda (po związaniu) są unikalnie identyfikowane przez czwórkę - host źródłowy, port źródłowy, host docelowy, port docelowy

W Javie gniazda nasłuchowe reprezentowane są przez klasę ServerSocket, a gniazda połączeniowe przez Socket.

Typowy scenariusz działania serwera wygląda następująco:

ustawienie gniazda nasłuchowego na znanym porcie; ewentualnie na pierwszym wolnym (wartość 0) i przekazanie o tym informacji:
server = new ServerSocket(0);
czekanie na akceptację połączenia z klientem
akceptacja połączenia, podczas której dokonywany jest standardowy handshake TCP i w wyniku której zwrócone zostaje gniazdo połączeniowe, ustawione na tym samym hoście i porcie co gniazdo nasłuchowe, związane z gniazdem połączeniowym klienta
client = server.accept();

utworzenie osobnego wątku obsługującego klienta (i powrót do nasłuchiwania)

new Thread() { 
    //...
    public void run() {
        // obsługa klienta
        //...
    }
}.start();

Natomiast typowy scenariusz działania klienta przedstawia się tak:

utworzenie gniazda komunikacyjnego i związanie go z gniazdem po stronie serwera; takie gniazdo zostanie utworzone na dowolnym wolnym porcie:
client = new Socket(serverAddress, serverPort);
komunikacja z serwerem i czynności porządkowe

Gra w liczby

Gra w liczby rozgrywa się pomiędzy dwoma graczami - rozgrywającym i zgadującym. Na początku gry zostaje ustalona liczba naturalna n. Rozgrywający przygotowuje ciąg n liczb całkowitych x_n i składa go z losową permutacją (tj. tasuje go) otrzymując ciąg y_n. Teraz rozgrywający przekazuje kolejno elementy y₀, y₁, ... graczowi zgadującemu. Zgadujący w dowolnym momencie odsłaniania i-tego elementu może powiedzieć ,,stop''. Jeżeli y_i jest maksymalnym elementem w ciągu x_n, wygrywa gracz zgadujący; w przeciwnym przypadku wygrywa rozgrywający.

Napisać serwer i klienta do przeprowadzania gry w liczby.

Protokół komunikacyjny (szkic - może być niespójny i zawierać błędy)

Serwer czeka na dwa połączenia od klientów
Do klienta, który zgłosił się jako pierwszy, wysyła zapytanie "get sequence length", po czym pobiera od niego liczbę naturalną n
Do drugiego klienta wysyła komunikat "set sequence length" i liczbę n
Faza licytacji. Serwer, poczynając od gracza pierwszego i wartości inicjalnej s = 1 wysyła kolejno do graczy komunikaty "current stake" z liczbą s, na które gracz musi odpowiedzieć wartością z przedziału <0, s>. Wartość odpowiedzi różna od s ustala nową stawkę licytacji; wartość równa s oznacza pas gracza. Serwer wysyła do przeciwnika pasującego gracza potwierdzenie stawki. Gracz, który spasował, jest graczem rozgrywającym, a pozostały z graczy - graczem zgadującym.
Faza rozgrywki - wykonywana m razy. Serwer do gracza rozgrywającego wysyła komunikat "get sequence", wczytuje od niego kolejno n liczb całkowitych i wysyła potwierdzenie "thanks for the sequence". Następnie do gracza pytającego wysyła komunikat "set sequence" i, w losowej kolejności, liczby z ciągu wczytanego od gracza rozgrywającego. Po każdej wysłanej liczbie czeka na odpowiedź "get next", albo "stop". Przy komunikacie "get next", kontynuuje wysyłanie liczb. Przy komunikacie "stop" - przerywa. Na koniec serwer sprawdza, czy ostatnio przesłana liczba była maksymalna w ciągu i wysyła informacje do obu graczy o wyniku - komunikat "score" opatrzony wartością wygranej.
Po przeprowadzeniu m rozgrywek, serwer podlicza punkty i wysyła do graczy komunikaty "you have won", lub "you have lost" w zależności od tego, czy dany gracz przegrał czy wygrał.