Wstęp do programowania/Wstęp do algorytmów/Ćwiczenia

Zadanie 1

Podaj algorytm wyliczający część wspólną dwu zadanych prostokątów o bokach równoległych do osi układu współrzędnych.

Analiza specyfikacji

• Czy specyfikacja podana w zadaniu jest wystarczająca do zapisania

algorytmu ?

Odpowiedź

Nie, nie wiadomo co to znaczy zadane, nie wiadomo co zlecający wykonanie zadania rozumiał przez wyliczanie.

• Co może być częścią wspólną ?

Odpowiedź

Prostokąt o bokach równoległych do osi układu, odcinek pionowy lub poziomy, punkt, zbiór pusty; wszystkie te przypadki możemy traktować jako szczególne rodzaje pierwszego przypadku.

• Jaka może być postać danych

Odpowiedź

Odpowiedź

Można rozważać kilka różnych postaci:

1. współrzędne dwu przeciwległych wierzchołków,
2. współrzędne lewego-górnego wierzchołka i prawego-dolnego,
3. współrzędne lewego-górnego wierzchołka i długości boków,
4. współrzędne środka, długość przekątnych i kąt nachylenia przekątnej łączącej lewy-górny wierzchołek z prawym-dolnym,
5. współrzędne lewego-górnego wierzchołka, pole prostokąta i stosunek długości boków,
6. współrzędne wszystkich czterech wierzchołków (od lewego-górnego w kolejności zgodnej z ruchem wskazówek zegara).
7. obszar zaznaczony przez użytkownika myszką na ekranie.

Każda z tych reprezentacji danych spełnia swoje zadanie i w konkretnym zastosowaniu może być tą, którą należy wybrać (bo np. nasz algorytm jest częścią większego systemu, który jej właśnie używa). Naszym zadaniem jako projektantów/analityków jest przeanalizowanie różnych możliwości, zaproponowanie zlecającemu rozwiązań, które uważamy za najlepsze, ale ostateczna decyzja należy do zlecającego, to my musimy się dostosować.

Reprezentacja 7 i tak sprowadzi się do jednej z pozostałych. Reprezentacja 6 jest nadmiarowa. Taka sytuacja ma swoje wady (koszt pamięciowy) i zalety (można łatwiej się zorientować, że dane nie są poprawne i nie trzeba wyliczać danych które są już podane, co może być kosztowne czasowo). Reprezentacje 3,4,5 są poprawne, w zależności od tego co chcemy robić z wynikiem naszych obliczeń mogą się okazać warte wybrania.

Reprezentacje 2 i 1 wydają się równoważne, dopiero przy wyborze reprezentacji wyniku okaże się, że różnica między nimi w tym akurat zadaniu jest bardzo istotna.

   Postać wyniku
     Skoro możemy traktować każdy możliwy wynik jako (być może

zdegenerowany) prostokąt o

     bokach równoległych do osi układu,to byłoby dobrze użyć tu tej

samej reprezentacji co dla

     danych (nam jako piszącym będzie łatwiej, a przede wszystkim jest

to lepsze dla użytkownika,

     który będzie mógł zastosować nasz algorytm do wyników przez ten

algorytm policzonych).

     I tu okazuje się wyższość reprezentacji 2, która pozwala

reprezentować także pusty prostokąt,

     w przeciwieństwie do reprezentacji 1. (Reprezetacje 3-6 też są

dobre, moglibyśmy także np.

     rysować wynik na ekranie.)

b) Znajdowanie algorytmu

      Dla utrudnienia narysujmy kilka możliwych wzajemnych położeń

prosokątów na tablicy. Zapewne

      pojawi się pomysł na badanie różnych przypadków wzajemnego

położenia tych prostokątów, jeśli

      tak, to pozwólmy chwilę nad tym rozwiązaniem popracować

studentom, tak by wszyscy zobaczyli jak

      bardzo nieprzyjemne jest to rozwiazanie (klikanaście bądź więcej

przypadków), skomentujmy

      dlaczego należy unikać tego typu rozwiazań.
      O ile studenci sami nie wpadną na dobre rozwiązanie lekko je im

zasugerujmy (jaka może być

      współrzędna x-owa lewego-górnego rogu wynikowego prostokąta).

Załóżmy, że mamy operacje

      min i max. Przyjmijmy oznaczenia:
        A, B, W - prostokąty dane i wynikowy (odpowiednio)
 x1,x2,y1,y2 - współrzędne lewego-górnego, i prawego-dolnego

wierzchołka (odpowiednio)

 P.x1 - notacja kropkowa do odwoływania się do współrzędnych
      Cały algorytm to cztery linijki (nie używam jeszcze symbolu

przypisania)

        W.x1 = max(A.x1, B,x1)
 W.y1 = min(A.y1, B.y1)
 W.x2 = min(A.x2, B.x2)
 W.y2 = max(A.y2, B.y2)
      (współrzędne y-owe rosną w górę, tak jak w matematyce, a nie w

dól jak na ekranie komputera).

c) Testowanie
  Mając algorytm/program powinniśmy go przetestować, czyli sprawdzić

ajkie daje wyniki dla

  przykładowych danych. Jakie dane warto testować (typowe oraz

szczególnie przypadki graniczne).

  Koniecznie podkreślmy, że testowanie jest ważne i że trzeba je robić,

ale że (o ile nie wykryje błędów)

  nic nie daje - nawet nie mamy pewności, że dla przetestowanych danych

zawsze dostaniemy poprawny

  wynik (bo np. mamy niezainicjalizowane zmienne).
  Przeliczmy wyniki  dla paru zestawów danych (np. prostokąt a zawarty

w B i przypadek gdy część

  wspólna jest pusta).

d)  Dowód poprawności
         Skoro testowanie nie daje pewności, że mamy dobry program

potrzebujemy inego narzędzia, które

   pozwoli nam spać spokojnie - możemy (przynajmniej teoretycznie)

dowieść formalnie poprawność

   programu.
   Co jest formalną specyfikacja naszego zadania (W = A \cap B).
   Zróbmy formalny dowód (tzn. bieżemy punkt p i pokazujemy że p \in A

\cap B jest równoważne

   temu, że p \in W).. Teraz już możemy spać spokojnie - nasz algorytm

_jest_ poprawny (o ile nie

   pomylilismy się także w  dowodzie)!

Sądzę, że najważniejszy morał z tego zadania, to pochwała myślenia - trzeba wykonać dużo pracy (myślowej) zanim zacznie się pisać pierwszy wiersz programu/algorytmu.