Laboratorium 1: Wprowadzenie do Linuksa

Pierwsze kroki z Linuksem

• logowanie następuje do środowiska zwanego KDE lub Gnome (jest jeszcze kilka, np. XFCE ... )
• przeglądarka (firefox, opera, konqueror, itp) -- Klikasz i masz,
  Otworzyć niniejsze materiały
• terminal (konsola),
  
  Okienko z powłoką (shell): służy do wykonywania poleceń użytkownika
  prompt$ polecenie [ENTER]
• mc Twoim przyjacielem
  (chodzenie po katalogach ENTER, wyświetlanie pliku F4, zaznaczanie plików INSERT, oraz [KP -], [KP +], [KP *],
  następnie F5 F6 F8 itp)
• / zamiast \
• Polecenia (niektóre):
  • ls - list - czyli wyświetl pliki w katalogu,

     
                ls /usr/
                ls -l
                ls -a
                ls -al /usr/
                ls -R
     

  • cd - change directory - zmień katalog
    Pojęcia katalogu bieżącego oraz ścieżek względnych i bezwzględnych.

     
                cd /usr/
                cd -
     

  • pwd - print working directory - pokaż bieżący katalog (gdybyśmy się zgubili :-)
  • cp co? gdzie? - copy - kopiuj

     
    	    cp ala ula
    	    cp ala ola ula archiwum
                cp -a
     

  • mv co? gdzie? - move - zmiana nazw bądź przeniesienie plików i katalogów do innego katalogu.

     
    	    mv ala ula
    	    mv ala ola ula archiwum
     

  • rm - remove - usuń plik/katalog

     
                rm -r
                rm -f
                rm -i
                rm -rf [OSTROŻNIE!!!!]
     

  • mkdir - make directory - utwórz katalog

     
                mkdir ~/podkatalog
                mkdir -p ~/glowny/podglowny/malutki
     

  • rmdir - remove directory - usuń katalog (tylko jeśli niepusty -- bezpieczniejsze od rm -r)

     
                rmdir ~/podkatalog
     

  • passwd -- zmień hasło [hasło powinno być łatwe do zapamiętania i trudne do zgadnięcia]

Edytory

• mcedit - prosty, wbudowany w mc,
  wyjście F10, lub kliknąć w 10
• joe - w stylu edytorów Borlanda,
  wyjście ^KX
• pico, nano - proste, tekstowe,
  wyjście ^X\
• gedit, kate - okienkowe
• vi - jest wszędzie, tekstowy, początkowo nieintuicyjny, skomplikowany, po dokładnym poznaniu efektywny,
  wyjście ESC :q! (to nie żart!)
• emacs - rozbudowany, początkowo skomplikowany, po bliższym poznaniu efektywny,
  bardzo elastyczny, konfigurowalny na bardzo wiele sposobów,
  wyjście ^X^C

System plików

• Nazwy katalogów:
  • / zamiast \
  • / (katalog głowny)
  • . (katalog bieżący)
  • .. (katalog nadrzędny)
  • ~ (nasz katalog domowy)
  • ~henio (katalog domowy użytkownika henio)
• W Linuxie/Unixie nie ma C:\, jest jedno drzewo plików.
  Urządzenia (fizyczne i logiczne: np. przez sieć) są montowane (mount) w systemie plików i
  tworzą jedną strukturę katalogów.
• Używanie * i ?
  ?b*a*.txt - oznacza wszystkie pliki, które mają w nazwie pierwszą literę dowolną, potem mają b,
  potem cokolwiek (w dowolnej liczbie), potem a, potem cokolwiek i kończą się na .txt.
  Inne znaczenie, niż w Windowsach:

   
  	ls
  	  ala.c ula.c ela.pas progs.pas
   
  	cp *.c *.pas  =  cp ala.c ula.c ela.pas  progs.pas
   

• ln dokąd? skąd? - link - dowiązanie i częściej używane dowiązanie symboliczne
  (składnia jak cp)

   
  	ln plik1.ocaml plik1.ml
          ln -s docs Dokumenty
   

• mount - pokazuje co gdzie jest zamontowane.
  Służy też do montowania, ale montować może (w zasadzie) tylko root (czyli administrator).
• df - pokazuje miejsce na dyskach.
• du - zajmowane miejsce (przez plik/katalog)

   
  	du ala.avi
  	du -s 
  	du -s *
   

• quota - moje limity na przestrzeń dyskową (twarde i miękkie limity).
• We wprowadzaniu nazw plików i katalogów mozemy sobie pomagac klawiszem [TAB], możemy też używać symboli .. ~

E-mail

• pine / mutt -- używanie poczty w konsoli
  UWAGA! Jak się spróbuje napisać wiadomość w mutt-cie odpali się edytor vi!
  Aby coś napisać trzeba nacisnąć "i", a jak sie skończy to ESC ZZ (dwa duze Z).
• Pliki .forward

Prawa dostępu

• Trzy poziomy:
  • właściciel (User),
  • grupa (Group),
  • pozostali (Others)

  Poziomy te będziemy dalej oznaczali literkami u, g, o oraz a (All).

• Każdy plik i katalog ma swojego właściciela i "grupę".
  Użytkownicy mogą należeć do wielu grup, ale pliki mają tylko jedną grupę.
• Prawa dostępu
  prawa dostępu pokazuje ls -l
  • r - read - prawo do odczytu ,
  • w - write - prawo do zapisu / modyfikacji,
  • x - execute - prawo do uruchamiania pliku (lub dostępu do katalogu).
• chmod - change mode - zmiana praw dostępu.
  Zmianę praw można określić kombinacją znaków postaci: poziom +/- prawa, np.:

   
  	chmod u+rwx *
  	chmod o-r *.c
  	chmod ug+rx Pliki
   

• chown - change owner - zmień właściciela
• chgrp - change group - zmień grupę
• Ćwiczenie: spróbować zapisać plik:
  • u kolegi, w / (powinno się nie dać!)
  • w /tmp (powinno się dać),
  • pozwolić NA CHWILĘ! kolegom na dostęp do jakiegoś swojego podkatalogu.

Przekierowania wejścia/wyjścia

• ls -l > plik - wyjście do pliku,
• ls -l / >> plik - wyjście doklejone na końcu pliku,
• ( echo "To jest katalog"; ls -l ) > plik - wyjscie z kilku komend do pliku - plik na początku wyzerowany,
• P1 | P2 | ... | Pn - przetwarzanie potokowe,
• P1 `P2` - wyjście P2 staje się częścią polecenia P1 (zwykle chodzi o listy plików).
• cat - wyświetla zawartość plików (wbrew pozorom nie katalogów!)

   
          cat .bashrc
          cat > ~/plik
          cat plik1 plik2 > plik
   

  Przydatny przy przetwarzaniu potokowym.

• less plik - lepszy do oglądania plików,
• sort - sortuje zadany plik lub standardowe wejście
  uniq - usuwa powtórzenia (serie),

   
  	sort plik > plik.posortowany
  	cat plik | sort | uniq > plik.bez.powtórzeń
   

• grep - wypisuje linie zawierajace zadany napis

   
  	grep main *.c
  	cat *.c | grep main
  	ls -l | grep drwx
  	cat *.c | grep main | sort | uniq > mains.txt
  	grep drwx `cat lista.plikow`
   

Procesy

• Lista procesów:

   
          ps
          ps u
  	ps aux
   

• top - najwięksi pożeracze zasobów,
• kill - zabicie (lub wysłanie sygnału do) procesu,

   
  	kill 1234
  	kill -9 1234
  	kill -HUP 1234
   

• killall - zabicie (lub wysłanie sygnału do) wszystkich procesów wykonujących dany program,

   
  	kill screen
  	kill -9 firefox-bin
   

• pstree - drzewo procesów
• Uruchamianie w tle
  Polecenie zakończone & - uruchamia się w tle, tzn. nie czekamy na jego zakończenie.
  Przydatne dla wszelkich programów "okienkowch".
  Jak się zapomni & - terminal jest zablokowany (czeka, aż program się skończy), ale można zrobić:
  • Ctrl-Z - zawiesi (suspend) proces,
  • bg - background - uruchomi w tle (odczepi do terminala) zawieszony proces,
  • fg - foreground - uruchomi na pierwszym planie (można też jednak zawiesić terminal jak się chce),
  • jobs - wypisze procesy przypięte do terminala,
  • kill %1 - poprzez % (procent) można łatwiej wybrać procesy przypięte do terminala,
  • Ctrl-C - przerywa działanie procesu pierwszoplanowego.

Zmienne i skrypty

• Zmienne i ich użycie w poleceniach:
  • zmienne to stringi
  • x="ala ma kota" - przypisanie
  • echo $x w paski - odwołanie się do wartości
  • x=$[y * 2 + z] - wyrażenia arytmetyczne
  • echo $HOME $USER $MAIL $PATH - różne ciekawe zmienne.
• Skrypt = plik tekstowy z poleceniami, któremu nadamy prawo do wykonywania.
  Dobry zwyczaj: pierwszy wiersz skryptu powinien wyglądać tak:

   
  	#!/bin/bash
   

  Określa on jaki program ma interpretować polecenia.
  Przydatne, jeśli chcemy napisać skrypt w języku dla jakiegoś innego interpretera:

   
  	#!/usr/bin/ocaml
  	#!/usr/bin/perl
   

Więcej na ten temat

• Dokumentacja systemowa:
  

   
          ls --help
          man ls
          info ls
   

  opcja --help działa dla wszystkich poleceń
  man polecenie - też!
  info polecenie - też (wyjście: ^X^C)
  .

• http://www.mimuw.edu.pl/~kubica/sop (pierwszych kilka ćwiczeń).
• http://wazniak.mimuw.edu.pl/index.php?title=Systemy_operacyjne
  (pierwszych kilka laboratoriów).
• http://www.itk.ntnu.no/ansatte/Hendseth_Sverre/bash/basics.html

Pierwszy kontakt z OCamlem

• Uruchomienie interpretera:
  

   
  	ocaml
  	2+3;;
  	^D
   

  (nie działają strzałki itp.)

   
  	ledit ocaml
   

  (działają strzałki!!!)

• Parę przykładów funkcji:

   
  	let f x = x*x;;
   
  	let ma co = "Ala ma "^co;;
  	ma "kota";;
   
  	f "kota";;
  	(error)
   
  	let g x = (f x)^(f x);;
  	(error)
   
  	let h x = f (f x);;
   
  	h 7;;
  	h (f 7);;
   
  	max_int;;
  	max_int+1;;
   
  	let rec silnia n = if n=0 then 1 else n*(silnia (n-1));;
   
  	let rec powtorz n s = if n=0 then "" else s^(powtorz (n-1) s);;
   
  	let powt3 = powtorz 3;;
   
  	let powt_ala n = powtorz n "ala";;
   

• Wczytanie kodu z pliku:

   
  	#use "plik.ml";;
   

Laboratorium 2: Pierwszy kontakt z Ocamlem

Uruchomienie interpretera Ocamla

W terminalu piszemy:

 
    ab123456@komputer:~$ ocaml
    2+3;;
    ^D
 

(nie działają strzałki itp :-( )

 
    ab123456@komputer:~$ ledit ocaml
 

(dzialaja strzalki! :-)

Parę przykładów funkcji

 
    let f x = x * x;;
 
    let ma co = "Ala ma " ^ co;;
    ma "kota";;
 
    f "kota";;
    (error)
 
    let g x = (f x)^(f x);;
    (error)
 
    let h x = f (f x);;
 
    h 7;;
    h (f 7);;
 
    max_int;;
    max_int+1;;
 
    let rec silnia n = 
      if n = 0 then 1 else n * (silnia (n-1));;
 
    let rec powtorz n s = 
      if n = 0 then "" else s ^ (powtorz (n-1) s);;
 
    let powt3 = powtorz 3;;
 
    let powt_ala n = powtorz n "ala";;
 

Jak pracować z Ocamlem?

Sposób dla malutkich kawałków kodu

W terminalu wpisujemy ocaml (lub lepiej ledit ocaml).
W drugim okienku uruchamiamy edytor i co chwilę kopiujemy kod myszką.

Sposób upierdliwy dla większych kawałków kodu

W terminalu wpisujemy ocaml (lub lepiej ledit ocaml).
W drugim okienku uruchamiamy edytor z plikiem "plik.ml", co chwilę zapisujemy plik w edytorze i wpisujemy #use "plik.ml";;
(albo lepiej wychodzimy z Ocamla, wchodzimy ponownie i wtedy robimy #use "plik.ml";;).
Uwaga: Pisząc #use należy samemu wpisać # (hash - kratkę).

Sposób lepszy dla większych kawałków kodu

Używamy edytora emacs ze wsparciem dla ocamla.

Są jeszcze inne sposoby, ale o nich powiemy jak zaczniemy pracować z
z programami podzielonymi na wiele plików.

Konfiguracja i używanie Ocamla pod emacsem

Konfiguracja

Na końcu pliku ~/.emacs należy dopisać:

 
        ;; Konfiguracja ocaml-mode
        (setq auto-mode-alist (cons '("\.ml[iylp]?$" . caml-mode) auto-mode-alist))
        (require 'caml)
        (require 'camldebug)
        (require 'caml-font)
 

A jeżeli w ogóle nie ma pliku ~/.emacs, to kopiujemy go stąd.

Dodatkowe informacje o instalacji ocaml emacs, np. w domu:
http://www.cs.jhu. edu/~scott/pl/caml/emacs.html

Używanie Ocamla pod emacsem

• uruchomić: emacs
• otworzyć plik z rozszerzeniem .ml (np. plik.ml), za pomocą menu, guziczka, Ctrl-X, Ctrl-F lub od razu uruchomić emacs poleceniem emacs plik.ml,
• napisać kawałek kodu,
• wykonać (Caml -> Start subshell),
• na pytanie "Caml toplevel to run: ocaml" odpowiadamy ENTER
  (czyli zgadzamy się na "ocaml" -- tutaj mamy szansę podać np. jakieś opcje
  wywołania polecenia ocaml, ale na razie nie potrzebujemy)
• wrócić do ramki z naszym plikiem,
• ustawić kursor _przed_ średnikami ;;
• wcisnąć Ctrl-c Ctrl-e (polecenie caml-eval-phrase),
• definicja przed średnikami zostanie automatycznie "przerzucona" do interpretera Ocamla,
  chyba że jest błędna -- wtedy zaznaczony zostanie fragment, w którym kompilator wykrył błąd,
  (uwaga: oczywiście prawdziwy błąd może być zupełnie gdzie indziej ;-)
• żeby "przerzucić" na raz większy kawałek kodu, zaznaczamy ten kawałek myszką
  (lub zaznaczamy początek Ctrl-Space i ustawiamy kursor na końcu),
• następnie Alt-x caml-eval-region,
• "toplevel" ocamla można też normalnie używać np. po to, by testować funkcje,
  nie zaśmiecając przy tym pliku z definicjami.

W przypadku gdy chcemy rozpocząć pracę w ocamlu od nowa:

• zabijamy interpreter Ocamla (wchodzimy do niego kursorem i robimy C-x C-k, lub File->Close),
• otwieramy go ponownie (Start subshell),

Pierwsze wprawki w Ocamlu

1. Zapisać funkcje omawiane na pierwszych ćwiczeniach (np. część wspólna prostokątów, przecinanie się odcinków) lub w tym tygodniu.
2. Zapisać procedury obliczające liczby Fibonacciego, liniowo i wykładniczo, porównać ich działanie,
3. Zapisać ogonowo i nieogono silnię czy inne zadania z ćwiczeń -- sprawdzić różnicę w działaniu dla większych argumentów,
4. Zaimplementuj kodowanie par liczb naturalnych jako liczby naturalne.
   To znaczy, napisz procedurę dwuargumentową, która koduje dwie liczby dane jako argumenty w jednej liczbie naturalnej.
   Dodatkowo napisz dwie procedury, które wydobywają z zakodowanej pary odpowiednio pierwszą i drugą liczbę.

Laboratorium 3: Wprowadzenie do modułów w Ocamlu

Specyfikacje i implementacje w Ocamlu

Ocaml bardzo silnie wspiera programowanie oparte o kontrakty (ang. Design by contract).
Rzeczywiście, każdy większy program w Ocamlu podzielony jest na moduły, z których każdy składa się ze specyfikacji
(czyli kontraktu, umieszczonego w pliku *.mli) i implementacji (w pliku *.ml).
Przykładowo, plik.mli może wyglądać tak:

 
    type typ
    val wartosc : typ
    val operacja : typ -> typ
    val string_of_typ : typ -> string
 

Odpowiadający mu plik.ml
może wyglądać tak:

 
    let wartosc = 7
 
    let operacyjka x = x + 1
    let operacja x = operacyjka (operacyjka x)
 
    type typ = int
    let string_of_typ = string_of_int
 

Aby sprawdzić, że implementacja spełnia swoją specyfikację, należy najpierw skompilować plik.mli:

 
    ocamlc -c plik.mli
 

O ile nie ma błędu, wyprodukowany zostanie plik.cmi.
Teraz można skompilować plik.ml:

 
    ocamlc -c plik.ml
 

Ta komenda zakończy się powodzeniem, czyli wyprodukowaniem pliku plik.cmo, tylko jeśli wcześniej został
skompilowany plik.mli i implementacja rzeczywiście odpowiada specyfikacji.
Teraz w drugi_plik.ml
można skorzystać z poprzedniego modułu w następujący sposób:

 
    let x = Plik.wartosc
    let y = Plik.operacja x
 
    open Plik
 
    let z = operacja y
    let _ = print_endline (string_of_typ z)
 

Zauważmy, że drugi_plik.ml nie ma pojęcia, że typ i int to to samo, ani że
istnieje coś takiego, jak operacyjka.
Istotnie, nie ma tego w specyfikacji modułu "Plik".


Aby skompilować drugi_plik.ml należy wykonać:

 
    ocamlc -c drugi_plik.ml
 

Otrzymamy plik drugi_plik.cmo.
Aby uzyskać gotowy program wykonywalny (to tzw. linkowanie) należy wykonać:

 
    ocamlc -o test plik.cmo drugi_plik.cmo
 

Teraz można sprawdzić, że działa:

 
    ./test
 

Co zostanie wypisane?

Wszystkie powyższe pliki można pobrać w postaci archiwum zip.

Warto w tym miejscu zapamiętać, że nazwy modułów piszemy w Ocamlu zawsze wielką literą, a nazwy
odpowiadających im plików zwyczajowo pisane są małymi literami.

Interaktywne środowisko i pliki kompilowane

Skompilowanych modułów można także używać wewnątrz interaktywnego środowiska Ocamla (tego
uruchamianego poleceniem ocaml, lub pod emacsem).
Przy pierwszym użyciu nazwy modułu Plik, ładowany jest automatycznie odpowiadający mu plik.cmi,
zawierający informacje o typach komponentów modułu.
Nie jest jednak ładowany kod samego modułu (plik.cmo), dlatego każda próba użycia komponentów
kończy się komunikatem o błędzie:

 
      # Plik.wartosc;;
      Reference to undefined global `Plik'
 

Plik.cmo ładowany jest tylko na wyraźne życzenie użytkownika.
Można do tego celu użyć komendy #load:

 
      # #load "plik.cmo";;
 

Uwaga: pierwszy # (krzyżyk/hash) jest znakiem zachęty środowiska, drugi musimy wprowadzić samemu, podobnie
jak w przypadku komendy #use czy #quit.

Powyższa komenda dołącza skompilowany moduł Plik do środowiska.
Po tej komendzie komponentów modułu Plik można używać za pomocą prefiksu, np.:

 
      Plik.string_of_typ Plik.wartosc;;
 

albo bez prefiksu, po uprzednim wykonaniu komendy open Plik:

 
      open Plik;;
      string_of_typ wartosc;;
 

Można również wydać polecenie załadowania skompilowanego modułu przy starcie środowiska:

 
      ocaml plik.cmo
 

Można też stworzyć własną wersję środowiska z załadowanym plikiem:

 
      ocamlmktop plik.cmo -o moj_toplevel
 

I potem używać jej zamiast standardowego środowiska:

 
      ./moj_toplevel
 

lub

 
      ledit ./moj_toplevel
 

Oczywiście w przypadku jednego modułu, z tworzenia własnej wersji środowiska nie mamy wielkiego zysku.

Laboratorium 4: Listy na przykładzie wielomianów

Listy na przykładzie wielomianów

Celem tego laboratorium jest przećwiczenie operacji na listach.
Środkiem do tego celu będą operacje na wielomianach symbolicznych.

Wielomiany zwykłe

Wielomiany reprezentujemy jako listę współczynników (typu float) od końca,
np. lista [3.; 5.; 7.] oznacza wielomian \(7x^2 + 5x + 3\).

Zanim przystąpimy do dalszego ciągu należy zdecydować, czy lista może być pusta, czy może kończyć się zerem itp.
Po podjęciu decyzji należy ją zapisać w komentarzu do definicji typu oraz się jej trzymać, tzn.:

• jeśli na coś pozwalamy, wszystkie funkcje powinny na to pozwalać (czyli muszą dobrze działać dla danych mających to coś);
• jeśli na coś nie pozwalamy, na wyjściu ze wszystkich funkcji nie mogą pojawić się dane mające to coś.

Należy zaimplementować następujące rzeczy:

 
      type wielomian = ... 
 
      val oblicz : wielomian -> float -> float 
      (** [oblicz w x] oblicza wartość wielomianu [w] w punkcie [x] *) 
 
      val suma : wielomian -> wielomian -> wielomian 
      (** Suma wielomianów *) 
 
      val iloczyn : wielomian -> wielomian -> wielomian 
      (** Iloczyn wielomianów *) 
 
      val pochodna : wielomian -> wielomian 
      (** Pochodna wielomianu *) 
 
      val stopien : wielomian -> int 
      (** Zwraca stopień wielomianu (czyli najwyższą potęgę argumentu, przy której wykładnik jest różny od 0.) *) 
 
      val calka : wielomian -> wielomian 
      (** Calka wielomianu. [calka w] ma wyraz wolny równy 0. *) 
 

Dobrze by było napisać też kilka generatorów większych wielomianów, np. jed n zwraca
\(x^n + x^{n-1} + \dots + 1\), jed_zer n zwraca \(x^{2n} + x^{2n-2} + \dots + x^2 + 1\) itp.

Należy zwrócić uwagę na złożoność operacji oraz czy implementacja jest ogonowa, czy nie
(o ile ma to wpływ na złożoność pamięciową) i zapisać te spostrzeżenia w komentarzu.

Wielomiany rzadkie

Wielomiany rzadkie, jak sama nazwa wskazuje, mają tylko niektóre współczynniki różne od zera, np. \(x^{1000} + 5x^{50} + 2x^{10} + 1\).
Ponieważ szkoda byłoby miejsca na przechowywanie takich wielomianów w sposób przedstawiony powyżej, będziemy reprezentować
je jako listę par (wykładnik,współczynnik) posortowaną wg rosnących wykładników.
Nasz przykładowy wielomian reprezentowany będzie przez [(0,1.); (10,2.); (50,5.); (1000;1.)].
Dla tej reprezentacji należy zaimplementować osobny zestaw narzędzi, składający się z definicji typu:

 
      type rzadki = ...
 

i tych samych funkcji co powyżej, przy czym do wszystkich nazw należy dołączyć sufiks _rz (np. oblicz_rz),
a we wszystkich typach należy zastąpić wielomian przez rzadki.
W tym zadaniu również należy najpierw zastanowić się, czy (niektóre) współczynniki mogą być równe 0., jak
reprezentowany jest wielomian stale równy zero itp.

Konwersje

Należy zaimplementować funkcje konwertujące wielomiany zwykłe na rzadkie i z powrotem:

 
      val rozrzedz : wielomian -> rzadki 
      (** Konwertuje wielomian do postaci rzadkiej usuwając wszystkie współczynniki równe 0. *) 
 
      val zagesc : rzadki -> wielomian 
      (** Kowertuje wielomian do postaci zwyklej dodajac (o ile trzeba) wyrazy o współczynnikach równych 0. *) 
 

Dla ambitnych/znudzonych: Obliczanie miejsc zerowych

Do powyższych zestawów funkcji operujących na wielomianach dopisać funkcję przybliżającą miejsca zerowe wielomianu
(funkcja ta powinna zwracać listę wartości typu float).
Wskazówka: jak mają się miejsca zerowe wielomianu do miejsc zerowych jego pochodnej?

Laboratorium 5: Ocamlbuild

Kompilacja projektów w Ocamlu

ocamlc i ocamlopt

Kompilator ocamla możemy wywołać jako program o nazwie ocamlc lub ocamlopt.
Ocamlc generuje kod bytecode'u (pliki *.byte), który nie jest bezpośrednio wykonywany, ale interpretowany. Taki kod jest niezależny od maszyny, na której jest wykonywany, a więc jest przenośny. Jego interpretacją zajumuje się program ocamlrun, dla użytkownika nie jest to jednak widoczne. Po prostu uruchamiamy plik skompilowany.
Ocamlopt generuje kod dla konkretnej architektury i systemu (kod natywny, pliki *.native). Nie jest on przenośny, ale działa szybciej.

Obu kompilatorom przekazujemy podobne zestawy argumentów:

• nazwy plików źródłowych które chcemy razem skompilować razem,
• opcję -o nazwa_pliku_wykonywalnego; jeżeli nie podamy tej opcji, to zostanie stworzony plik a.out.

Przykład: ocamlc leftist.mli leftist.ml test.ml -o test

Kompilująć program w ten sposób, zawsze kompilujemy wszystkie pliki źródłowe. W przypadku bardzo małych projektów, może to być akceptowalne.
Jednak już w przypadku projektów średniej wielkości właściwe jest kompilowanie osobno wszystkich modułów (które tego wymagają) i łączenie ich kodu w jeden plik wykonywalny.
Skompilowane interfejsy modułów (pliki *.mli) to pliki o rozszerzeniu *.cmi.
Implementacje modułów skompilowane do kodu natywnego mają postać plików z rozszerzeniem *.o (standardowy format object-code) oraz *.cmx (pliki typowe dla Ocamla).
Implementacje modułów skompilowane do bytecode'u maję postać plików z rozszerzeniem *.cmo.

Chcąc skompilować tylko jeden plik, interfejsu lub implementacji modułu, wystarczy podać odpowiedniemu kompilatorowi opcję -c.

Ocamlbuild

Typowym narzędziem uniksowym do kompilowania projektów jest program make wraz z plikiem Makefile opisującym
zależności między plikami. Jednak do kompilacji małych lub średnich projektów w Ocamlu lepiej użyć programu ocamlbuild.

Założenia: wszystkie potrzebne pliki źródłowe są w bieżącym katalogu.
Wystarczy wykonać ocamlbuild program.native lub ocamlbuild program.byte. Ocamlbuild sam zbada zależności między modułami i skompiluje dokładnie to co jest niezbędne. Wszystkie pliki generowane automatycznie będą umieszczone w katalogu _build,
a w bieżącym katalodu pojawi się dowiązanie do skompilowanego programu.

Więcej o programie ocamlbuild: https://ocaml.org/learn/tutorials/ocamlbuild/

Warsztat programisty

Laboratorium 2: Warsztat programisty

Programowanie to sport zespołowy.  Duże programy są tworzone przez zespoły, lub wiele współpracujących zespołów.  Bywa i tak, że nikt nie ma wiedzy o całym systemie, a każdy zna tylko jego fragmenty.  Jak sensownie funkcjonować w takich realiach?  Oto kilka zasad dobrego warsztatu programisty.

Kwestia stylu

Dla kogo piszemy kod? Dla komputera? Ależ skąd! Piszemy dla siebie i swoich współpracowników. Inaczej, po skompilowaniu pierwszej wersji programu, możnaby kod źródłowy wyrzucić. Tymczasem program, który jest używany, będzie wielokrotnie modyfikowany, przez nas i naszych kolegów. Modyfikacje same są zwykle niewielkie, ale wymagają przeczytania większego fragmentu kodu. Wniosek: kod źródłowy jest więcej razy czytany, niż pisany. Powinniśmy więc go tak pisać, żeby się łatwo czytało i modyfikowało, a nie żeby jak najszybciej stworzyć pierwszą wersję. 

Wcięcia

Wcięcia muszą być! Kod bez wcięć nie będzie oceniany.  Wszytkie szczegóły dotyczące wcięć wynikają z tego po co one są: wcięcia mają ułatwić szybkie dopasowanie początku i końca konstrukcji składniowej.  
Wielkość wcięć: od 2 do 4, w zależności od smaku, ale konsekwentnie stała. Minimalna wielkość wcięcia to 2, bo inaczej "schodki" nie są widoczne.  Maksymalna to 4, bo inaczej kod robi się strasznie szeroki.  
W pozostałych szczegółach, możecie dobrać Państwo styl, który najbardziej Wam odpowiada, byle konsekwentnie.  Tutaj można znaleć przykładowy dobry styl. 

Odstępy

Robimy odstępy wokół operatorów binarnych i po znakach interpunkcyjnych.  Nie robimy odstępów po wewnętrznej stronie nawiasów.  Na przykład: 2 + 2 * 4, [2; 3; 4], (2, 3 - 4). 
Odstępy w pionie (puste wiersze) też są ważne.  Między definicjami procedur robimy wiersz lub dwa odstępu.  Wewnątrz dłuższych procedur możemy też robić pojedyncze wiersze odstępu dla podkreślenia struktury kodu. 

Komentarze

W podejściu do komentarzy można spotkać dwie skrajności:

• Kod sam się tłumaczy i komentarze są zbędne, oraz
• Wszystko należy komentować. 

Oba podejścia są złe. Owszem, kod ma być przejrzysty i ma być widać co się w nim dzieje, ale zawsze są pewne aspekty, które z niego nie wynikają, np. co jest celem? po co coś się dzieje? co zakładamy? Z drugiej strony, umieszczanie w komentarzach "relacji na żywo" z obliczeń mija się z celem i tylko utrudnia czytanie kodu. Podstawowa zasada brzmi: Komentarze mają ułatwić czytanie i zrozumienie kodu. Odnosi się to tak samo do innych programistów, z którymi współpracujemy, jak i do nas samych tylko za jakiś czas. Oto kilka typowych miejsc, w których warto umieszczać komentarze:

• deklaracje typów danych (lub ogólniej struktur danych) -- co reprezentują? jakie są założenia co do dopuszczalnych wartości (tzw. niezmienniki typów danych),
• definicje procedur -- co zakładamy o argumentach, czego można oczekiwać jako wyniku, za co procedura "odpowiada",
• interfejs modułu (o mudułach dokładniej będzie za tydzień) -- to co powinien wiedzieć użytkownik modułu.

Identyfikatory

Identyfikatory powinny być znaczące. Jeśli z nazwy identyfikatora wynika czym jest argument, to często nie trzeba nic więcej o nim pisać w komentarzach. 
Identyfikatory (nazwy stałych i procedur) powinny zaczynać się z małej litery.  Wieloczłonowe nazwy proponuję łączyć podkreśleniem: taki_sobie_identyfikator.  

Testy

Program, który jest rozwijany podlega ciągłym zmianom.  Jak sprawdzić, czy kolejne zmiany nie wprowadzają nowych błędów do programu?  Testować!  Warto utrzymywać bogaty zestaw testów, które po każdej zmianie w programie możemy łatwo uruchomić. Testy nie zagwarantują nam poprawności kodu, ale odpowiedni zestaw testów potreafi wykryć większość błędów.
Pisząc kod, powinniśmy odrazu tworzyć dla niego testy.  Dla każdej funkcjonalności / procedury piszemy testy.  Mamy jakąś elementarną procedurę wykorzystywaną w naszym kodzie -- piszemy dla niej testy. Mamy procedurę integrującą kilka procedur pomocniczych w coś większego -- piszemy dla niej testy.  Tak jak procedury tworzą hierarchię, tak testy tworzą swoistą piramidę.  Powiniśmy mieć wiele prostych testów dla elementarnych procedur (unit testy), oraz mniejszą liczbę testów-scenariuszy symulujących sposób użycia całego systemu. 
Jak pisać testy w Ocamlu?  Najlepiej wykorzystać operację assert <warunek>;. (Uwaga na ";". Narazie nie wnikamy w imperatywność.) Sprawdza ona, czy warunek jest spełniony i jeśli nie, przerywa obliczenia.  Gdy uruchamiamy kod "dla użytkownika", możemy wyłączyć sprawdzanie asercji opcją -noassert.  Testy mogą być po prostu asercjami na poziomie definicji (tj. nie zagnieżdżonymi wewnątrz definicji).  Umieszczanie asercji wewnątrz definicji procedur też ma sens, ale to już coś innego niż testowanie.

Code review

Dwie najpopularniejsze techniki pisania kodu, mające na celu wyeliminowanie błędów, to code reviews i pair-coding.  Pair-coding polega na pisaniu razem w parach.  Jedna osoba pisze kod, a druga śledzi i komentuje ten proces.  Obie muszą rozumieć co się dzieje i być przekonane, że powstający kod jest poprawny.  Code review polega na tym, że kod, lub zmiana w kodzie, napisana przez jednego programistę jest przeglądana przez innego programistę.  Przeglądający może zgłaszać zastrzeżenia i wskazywać co należy poprawić.  Zasadniczo reviewer nie wprowadza poprawek sam, z wyjątkiem drobiazgów.  Tę właśnie technikę zastosujemy na Laboratorium. 

Systemy kontroli wersji

Jeśli pracujemy w zespole wieloosobowym nad programem składającym się z wielu plików, to jak synchroizować wyniki swojej pracy?  Do tego właśnie służą systemy kontroli wersji.  System kontroli wersji pamięta:

• aktualną wersję programu, 
• aktualną "oficjalną" wersję programu (release), 
• poszczególne zmiany wprowadzone przez programistów, 
• kto wprowadził dany fragment kodu.

Starsze systemy kontroli wersji (RCS) wymagały blokowania plików w celu wprowadzania zmian w nich.  Nowsze systemy kontroli wersji (Subversion, Git) pozwalają na równoczesne wprowadzanie zmian w tych samych plikach przez wielu programistów.  W praktyce dobrze się to sprawdza.  Jednak zmiany takie nie zawsze można automatycznie scalić.  Czasami konieczna jest interwencja człowieka. 

Git

Git jest aktualnie chyba najpopularniejszym systemem kontroli wersji.  Git jest systemem rozproszonym.  Na każdym komputerze biorącym udział w tworzeniu programu znajduje się repozytorium zawierające kompletną (choć niekoniecznie aktualną) informację o historii wersji programu.  Repozytoria mogą wymieniać między sobą informacje o wprowadzanych zmianach.  Zwykle każdy programista ma jedno repozytorium lokalne na swoim komputerze, oraz istnieje jedno zdalne repozytorium, służące synchronizowaniu zmian. 
W Git'ie konkretna wersja programu to commit. Commit ma poprzedni commit i wiadomo jakie zmiany względem niego wprowadza.  Jeden poprzedni commit może mieć wiele następnych commitów (fork).  Możliwy jest też commit o dwóch poprzednich commitach (merge), scalający zmiany wprowadzone od ich wspólnego poprzednika. 
Zwykle myślimy w kategoriach gałęzi (branch), a nie commit'ów.  Branch to wskaźnik na konkretny commit.  W miarę wprowadzania zmian do kodu, wskaźnik ten jest przesuwany na kolejne commity. Zwykle mamy główną gałąź (trunk/master) oraz wiele gałęzi pobocznych, tworzonych na potrzeby opracowania poszczególnych zmian i łączonych potem z główną gałęzią. 
Git bardzo dobrze wspiera przeglądy kodu.  Typowy cykl opracowania zmiany w kodzie wygląda następująco:

• Autor:
• utworzenie feature branch'a: git branch xxxx; git checkout xxxx
• dodanie kodu / zmiany w kodzie, 
• potwierdzenie zmian w repozytorium: git commit ....
• przesłanie zmian: git push
• Reviewer:
• pobranie zmian: git pull; git checkout xxxx; git merge 
• wprowadzone zmiany: git diff master..xxxx
• przegląd kodu, testy, itp. 
• włączenie zmian do głównej gałęzi: git checkout master; git merge xxxx

Istnieje wiele serwisów oferujących przechowywanie zdalnego repozytorium, np. GitHub, BitBucket. Można też do tego wykorzystać współdzielony system plików, choć właściwa kontrola praw dostępu wymaga pewnie utworzenia mnóstwa grup.  Jeżeli będziecie Państwo przechowywać swoje programy zaliczeniowe w repozytoriach, to proszę zadbać, żeby nie były one publicznie dostępne (przynajmniej dopóki nie minie ostateczny termin oddawania programów). 

Zadanie 0: Arytmetyka przybliżonych wartości

Arytmetyka przybliżonych wartości

Tam gdzie dokonujemy pomiarów wielkości fizycznych, wyniki są obarczone pewnym błędem, np. 5m ± 10%.
Każdą taką przybliżoną wartość traktujemy jak zbiór możliwych wartości.
Zaimplementuj pakiet operacji arytmetycznych na takich przybliżonych wartościach zawierający:

• konstruktory:
  • wartosc_dokladnosc x p = x ± p% (dla p > 0),
  • wartosc_od_do x y = (x+y)/2 ± (y-x)/2 (dla x < y),
• selektory:
  • in_wartosc x y ⇔ wartość x może być równa y,
  • min_wartosc x = kres dolny możliwych wartości x (lub -∞ jeśli możliwe wartości x nie są ograniczone od dołu),
  • max_wartosc x = kres górny możliwych wartości x (lub ∞ jeśli możliwe wartości x nie są ograniczone od góry),
  • sr_wartosc x = średnia (arytmetyczna) wartości min_wartosc x i max_wartosc x
    (lub nan jeśli, min_wartosc x lub max_wartosc x nie są skończone),
• modyfikatory:
  • plus a b = { x + y : in_wartosc a x ∧ in_wartosc b y },
  • minus a b = { x - y : in_wartosc a x ∧ in_wartosc b y },
  • razy a b = { x · y : in_wartosc a x ∧ in_wartosc b y },
  • podzielic a b = {x/y: in_wartosc a x ∧ in_wartosc b y }.

Zakładamy przy tym implicite, że wszystkie argumenty typu float są liczbami rzeczywistymi
(tzn. są różne od infinity, neg_infinity i nan).
Natomiast w przypadku, gdy wynik nie jest liczbą rzeczywistą, powinien być odpowiednią z wartości: infinity, neg_infinity lub nan).

Przyjmij, że modyfikatory domykają wynikowe zbiory wartości, tzn. jeżeli, na przykład, wynikiem jest
przedział otwarty, to przyjmij, że zostaje on zamieniony na przedział domknięty.

Twoje rozwiązanie ma być umieszczone w pliku o nazwie arytmetyka.ml i pasować do specyfikacji
interfejsu arytmetyka.mli.

Uwaga:

• zaimplementować ściśle podany interfejs,
• przysłać plik arytmetyka.ml,
• zadania nie pasujące do interfejsu lub w pliku o innej nazwie nie będą oceniane,
• termin: 1 tydzień.

Zadanie 1: Drzewa lewicowe

Drzewa lewicowe to ciekawa implementacja złączalnych kolejek priorytetowych.
Kolejki priorytetowe to struktury przechowujące dane obdarzone priorytetami, umożliwiające łatwy dostęp do elementu o najwyższym priorytecie.
(Tradycyjnie, im mniejsza liczba reprezentująca priorytet, tym wyższy priorytet. ;-)
Struktury te dostarczają następujących operacji:

• utwórz pustą strukturę,
• wstaw nowy element,
• usuń element o najwyższym priorytecie.

Oczywiście po usunięciu elementu o najwyższym priorytecie, drugi w kolejności staje się tym najwyższym itd.
Kolejki złączalne umożliwiają dodatkowo łączenie dwóch kolejek w jedną.

Kolejki priorytetowe implementuje się zwykle za pomocą tzw. kopców, czyli struktur drzewiastych, które
spełniają tzw. warunek kopca, mówiący, że priorytet elementu zawartego w korzeniu każdego poddrzewa
jest mniejszy lub równy niż każdego innego elementu w tym poddrzewie.

Drzewa lewicowe to kopce binarne (czyli każdy węzeł może mieć 0, 1 lub dwóch potomków)
spełniające, oprócz warunku kopca, tzw. warunek lewicowości.
Warunek lewicowości mówi, że dla każdego węzła skrajnie prawa ścieżka zaczynająca się w danym
węźle jest najkrótszą ścieżką od tego węzła do liścia.
Dzięki temu w każdym drzewie lewicowym, tzw. prawa wysokość, czyli długość skrajnej prawej
ścieżki od korzenia do liścia, jest co najwyżej logarytmicznej wielkości, w porównaniu z liczbą elementów drzewa.
Dodatkowo, aby umożliwić efektywne wykonywanie operacji na drzewie, w każdym węźle przechowywana
jest prawa wysokość poddrzewa zaczepionego w tym węźle.

Najważniejszą operacją na drzewach lewicowych jest ich łączenie.
Pozostałe operacje wykonuje się bardzo prosto:

• wstawianie elementu do istniejącego drzewa polega na utworzeniu jednoelementowego drzewa i połączeniu go z danym drzewem,
• usuwanie najmniejszego to usunięcie korzenia drzewa i połączenie poddrzew.

Łączenie drzew lewicowych też nie jest trudne.
Aby połączyć dwa niepuste drzewa lewicowe, ustawiamy jako pierwsze (\(d_1\)) to, które ma mniejszy
element w korzeniu, a jako drugie (\(d_2\)) to, które ma większy.
W korzeniu wynikowego drzewa na pewno będzie więc korzeń \(d_1\).
Teraz rekurencyjnie łączymy prawe poddrzewo \(d_1\) oraz całe drzewo \(d_2\), w wyniku dostając drzewo \(d_3\).
Jako wynik całej operacji łączenia \(d_1\) i \(d_2\) zwracamy drzewo \(d_4\), które wygląda następująco:
Korzeń \(d_4\) jest taki sam, jak korzeń \(d_1\).
Jedno z poddrzew \(d_4\) to lewe poddrzewo \(d_1\), a drugie to drzewo \(d_3\).
Przy tym prawym poddrzewem \(d_4\) zostaje to z nich, które ma mniejszą prawą wysokość.
Dzięki temu \(d_4\) pozostaje drzewem lewicowym.
Oczywiście przy konstrukcji drzewa \(d_4\) należy pamiętać o odpowiednim ustawieniu prawej wysokości.

Rysunkową wersję łączenia drzew lewicowych można zobaczyć np. tu:
http://www.cise.ufl.edu/~sahni/cop5536/sliddes/lec114.pdf.

W naszym zadaniu dla uproszczenia zakładamy, że dane składają się z samych priorytetów.

Zadanie

Używając drzew lewicowych zaimplementuj złączalną kolejkę priorytetową z następującymi operacjami:

 
      type 'a queue 
      (** Typ złączalnej kolejki priorytetowej *) 
 
      val empty : 'a queue 
      (** Pusta kolejka priorytetowa *) 
 
      val add : 'a -> 'a queue -> 'a queue 
      (** [add e q] zwraca kolejkę powstałą z dołączenia elementu [e] do kolejki [q] *) 
 
      exception Empty 
      (** Wyjątek podnoszony przez [delete_min] gdy kolejka jest pusta *) 
 
      val delete_min : 'a queue -> 'a * 'a queue 
      (** Dla niepustej kolejki [q], [delete_min q] zwraca parę [(e,q')] gdzie [e] 
          jest elementem minimalnym kolejki [q] a [q'] to [q] bez elementu [e]. 
          Jeśli [q] jest puste podnosi wyjątek [Empty]. *) 
 
      val join : 'a queue -> 'a queue -> 'a queue 
      (** [join q1 q2] zwraca złączenie kolejek [q1] i [q2] *) 
 
      val is_empty : 'a queue -> bool 
      (** Zwraca [true] jeśli dana kolejka jest pusta. W przeciwnym razie [false] *) 
 

(specyfikacja ta znajduje się również w pliku leftist.mli)

Termin oddania zadania ustala prowadzący — 2 tygodnie od ogłoszenia.

Zadanie 2: Origami

Origami

Zaimplementuj bibliotekę dla fanów origami do badania ile warstw ma w danym punkcie sprytnie poskładana kartka papieru.
Biblioteka powinna implementować interfejs origami.mli, podany poniżej

 
    type point = float * float
    (** Punkt na płaszczyźnie *)
 
    type kartka = point -> int
    (** Poskładana kartka: ile razy kartkę przebije szpilka wbita w danym punkcie *)
 
    val prostokat : point -> point -> kartka
    (** [prostokat p1 p2] zwraca kartkę, reprezentującą domknięty prostokąt
        o bokach równoległych do osi układu współrzędnych i lewym dolnym rogu [p1]
        a prawym górnym [p2]. Punkt [p1] musi więc być nieostro na lewo i w dół
        od punktu [p2]. Gdy w kartkę tę wbije się szpilkę wewnątrz
        (lub na krawędziach) prostokąta, kartka zostanie przebita 1 raz,
        w pozostałych przypadkach 0 razy *)
 
    val kolko : point -> float -> kartka
    (** [kolko p r] zwraca kartkę, reprezentującą kółko domknięte o środku w punkcie [p] i promieniu [r] *)
 
    val zloz : point -> point -> kartka -> kartka
    (** [zloz p1 p2 k] składa kartkę [k] wzdłuż prostej przechodzącej przez
        punkty [p1] i [p2] (muszą to być różne punkty). Papier jest składany
	w ten sposób, że z prawej strony prostej (patrząc w kierunku od [p1] do [p2])
	jest przekładany na lewą. Wynikiem funkcji jest złożona kartka. Jej
	przebicie po prawej stronie prostej powinno więc zwrócić 0.
	Przebicie dokładnie na prostej powinno zwrócić tyle samo,
	co przebicie kartki przed złożeniem. Po stronie lewej -
	tyle co przed złożeniem plus przebicie rozłożonej kartki w punkcie,
	który nałożył się na punkt przebicia. *)
 
    val skladaj : (point * point) list -> kartka -> kartka
    (** [skladaj [(p1_1,p2_1);...;(p1_n,p2_n)] k = zloz p1_n p2_n (zloz ... (zloz p1_1 p2_1 k)...)]
        czyli wynikiem jest złożenie kartki [k] kolejno wzdłuż wszystkich prostych
	z listy *) 
 

Rozwiązując to zadanie powinieneś skorzystać ze standardowych procedur wyższych rzędów przetwarzających listy.
W przeciwnym przypadku Twoje rozwiązanie zostanie ocenione trochę niżej.
Termin wykonania zadania ustala prowadzący -- 2 tygodnie po ogłoszeniu

Zadanie 3: Modyfikacja drzew

Zadanie polega na zmodyfikowaniu biblioteki zbiorów pojedynczych elementów zaimplementowanych jako drzewa AVL (drzewa BST z wyważaniem).
Dzięki wyważaniu wysokość drzewa jest zawsze rzędu logarytm z liczby wierzchołków i dlatego wszystkie operacje wykonywane są w czasie
logarytmicznym (nawet operacja split, ale to jest trochę mniej oczywiste: wynika z tego, że koszt join jest w istocie
proporcjonalny do różnicy wysokości drzew, które łączymy.
A ponieważ na split składa się ciąg operacji join na coraz wyższych drzewach, ich koszty sumują się do wysokości drzewa razy pewna stała).

Wynikiem modyfikacji ma być biblioteka zbiorów liczb całkowitych oparta o przedziały.
Czyli elementami występującymi w drzewie muszą być przedziały, a nie pojedyncze liczby.
Przedziały muszą być rozłączne i w dodatku, aby uniknąć niejednoznaczności reprezentacji, przedziały w drzewie nie mogą być "sąsiednie",
czyli np. dwa przedziały [1..3] i [4..6] powinny być zastąpione przez jeden przedział [1..6].
W naszej bibliotece dopuszczamy przedziały jednoelementowe, np. [3..3].

Wszystkie operacje (poza fold, iter, elements oraz is_empty) mają wykonywać się w czasie \(O(\log n)\), gdzie \(n\) jest liczbą wierzchołków w drzewie.

Do zadania dołączona jest oryginalna specyfikacja i implementacja zbiorów oraz specyfikacja zbiorów przedziałów, której implementację należy przesłać jako plik o nazwie iSet.ml.
Komplet plików można też pobrać jako archiwum zip.

Termin oddania zadania ustala prowadzący — 2 tygodnie od ogłoszenia.

Zadanie 4: Sortowanie topologiczne

Sortowanie topologiczne polega na rozszerzeniu skończonego częściowego porządku do porządku liniowego.
Mówiąc prościej, mając dany DAG (czyli graf skierowany bez cykli) należy przypisać wierzchołkom takie różne liczby naturalne (nadające kolejność tym wierzchołkom), żeby dla każdej krawędzi grafu jej źródło miało niższy numer niż jej cel.
Mówiąc jeszcze prościej, mając daną częściową informację o zależności, powiedzmy, czynności od siebie (np. buty wkładamy po skarpetkach, krawat po koszuli itp. ale kolejność wkładania skarpetek i koszuli może być dowolna) mamy wygenerować ścisłą kolejność wykonywania czynności (np. koszula, skarpetki, buty, krawat).
Konkretnie, należy zaprogramować implementację topol.ml załączonej specyfikacji topol.mli.

W implementacji można korzystać z modułu pMap (bardzo podobnego do pSet z poprzedniego zadania), którego specyfikacja i implementacja również są załączone. Wszystkie potrzebne pliki można także pobrać w postaci archiwum zip.

Termin oddania zadania ustala prowadzący — 2 tygodnie od ogłoszenia.

Ćwiczenia 1: Wstęp

W poniższych zadaniach zdefiniuj opisane funkcje matematyczne.
Możesz, a nawet powinieneś, zdefiniować przydatne funkcje pomocnicze.
Opisz też sposób reprezentacji danych (np.\ punkt możemy reprezentować jako parę współrzędnych).

1. Wyznacz przecięcie dwóch prostokątów o bokach równoległych do osi współrzędnych i całkowitych współrzędnych wierzchołków.
   Rozwiązania
2. Zdefiniuj funkcję określającą, czy dwa odcinki o końcach o współrzędnych całkowitych przecinają się.
   (Dostępna jest tylko dziedzina algorytmiczna liczb całkowitych i wartości logicznych.)
3. Napisz funkcję określającą, czy dwa równoległoboki mają niepuste przecięcie.
4. Czy punkt leży wewnątrz wielokąta (niekoniecznie wypukłego, ale bez samoprzecięć).
   Wielokąt jest dany w postaci ciągu kolejnych wierzchołków na obwodzie (w kolejności przeciwnej do ruchu wskazówek).

Ćwiczenia 2: Procedury operujące na liczbach

Rozwiązania poniższych zadań to proste procedury operujące na liczbach całkowitych.
Dla każdej procedury rekurencyjnej podaj jej specyfikację, tj. warunek wstępny i końcowy,
oraz uzasadnij jej poprawność.
Poprawność procedur rekurencyjnych można pokazać przez indukcję.

1. Stopień parzystości liczby całkowitej \(x\), to największa taka liczba naturalna \(i\), że \(x\) dzieli się przez \(2^i\).
   Liczby nieparzyste mają stopień parzystości 0, liczby 2 i -6 mają stopień parzystości 1,
   a liczby 4 i 12 mają stopień parzystości 2.
   Przyjmujemy, że 0 ma stopień parzystości -1.

   Napisz procedurę parzystość wyznaczającą stopień parzystości danej liczby całkowitej.
   
   Rozwiązania

2. Napisz procedurę, która przekształca daną liczbę naturalną w taką, w której cyfry występują w odwrotnej kolejności,
   np. 1234 jest przekształcane na 4321.
   
   Rozwiązania
3. Sumy kolejnych liczb nieparzystych dają kwadraty kolejnych liczb naturalnych, zgodnie ze wzorem:
   \(\sum_{i=1}^k (2 i - 1) = k^2\).
   Wykorzystaj ten fakt do napisania procedury sqrt obliczającej sqrt x \( = \lfloor\sqrt{x}\rfloor\)
   i nie korzystającej z mnożenia, ani dzielenia.
   
   Rozwiązania
4. Liczbę naturalną nazwiemy rzadką, jeżeli w jej zapisie binarnym żadne dwie jedynki nie stoją obok siebie.
   Napisz procedurę rzadkie : int → int, która dla danej liczby naturalnej \(n\) zwróci najmniejszą rzadką liczbę naturalną większą od \(n\). Na przykład, dla \(n = 42 = 101010_2\) mamy \(\mathtt{rzadkie}\ 42 = 1000000_2 = 64\).
   
   Rozwiązania
5. Liczbę naturalną nazwiemy rzadką, jeżeli w jej zapisie binarnym żadne dwie jedynki nie stoją obok siebie.
   Napisz procedurę rzadkie : int → int, która dla danej liczby naturalnej \(n\) wyznaczy liczbę dodatnich liczb rzadkich, które nie przekraczają \(n\).
   Na przykład, dla \(n = 42 = 101010_2\) mamy rzadkie 42 = 20.
   
   Rozwiązania
6. Napisz procedurę, która sprawdza, czy dana liczba jest pierwsza.
   
   Rozwiązania
7. Zaimplementuj kodowanie par liczb naturalnych jako liczby naturalne.
   To znaczy, napisz procedurę dwuargumentową, która koduje dwie liczby dane jako argumenty w jednej liczbie naturalnej.
   Dodatkowo napisz dwie procedury, które wydobywają z zakodowanej pary odpowiednio pierwszą i drugą liczbę.
   
   Rozwiązania
8. Napisz procedurę, która dla danej liczby \(n\) sprawdzi czy pierścień reszt modulo \(n\) zawiera nietrywialne pierwiastki
   z 1 (tj. takie liczby \(k\), \(k \neq 1\), \(k \neq n-1\), że \(k^2 \equiv 1\ \mod\ n\)).
   Nota bene, jeśli takie pierwiastki istnieją, to liczba \(n\) nie jest pierwsza.
   Odwrotna implikacja jednak nie zachodzi --- np. dla \(n=4\) nie ma nietrywialnych pierwiastków z 1.
   
   Rozwiązania

Ćwiczenia 3: Rekurencja ogonowa

Rozwiązania poniższych zadań to proste procedury operujące na liczbach całkowitych.
Ich rozwiązanie wymaga zastosowania rekurencji ogonowej.
Dla każdej procedury rekurencyjnej podaj jej specyfikację, tj. warunek wstępny i końcowy,
oraz uzasadnij jej poprawność.
Poprawność procedur rekurencyjnych można pokazać przez indukcję.
Nie zapomnij o uzasadnieniu własności stopu.

1. Potęgowanie liczb całkowitych (z akumulatorem).
   
   Rozwiązania
2. [Bentley]
   Dana jest funkcja \(f: \{1, 2, \dots, n\} \to {\cal Z}\).
   Należy znaleźć takie \(1 \le a \le b \le n\), że suma \(\sum_{i=a}^b f(i)\) jest największa.
   Napisz taką procedurę p, że \(\mathtt{p}\ f\ n = b - a + 1\) (dla \(a\) i \(b\) jak wyżej).
   
   Rozwiązania
3. Napisz procedurę \(\mathtt{zera\_silni} : \mathtt{int} \to \mathtt{int}\), która dla danej dodatniej liczby całkowitej \(n\) obliczy ile zer znajduje się na końcu zapisu dziesiętnego liczby \(n!\).
   
   Rozwiązania
4. Dana jest funkcja nierosnąca \(f: \mathtt{int} \to \mathtt{int}\), taka, że \(f(x+1) \ge f(x) - 1\).
   Napisz procedurę, która znajduje punkt stały tej funkcji, tzn. taką liczbę \(x\), że \(f(x) = x\)
   (lub jeśli punkt stały nie istnieje, to taką liczbę \(x\), że \(f(x-1) \ge x\) oraz \(f(x) \le x\)).
   
   Rozwiązania
5. Dana jest różnowartościowa funkcja \(f: \mathtt{int} \to \mathtt{int}\).
   Napisz procedurę maksima, która dla danych liczb \(l\) i \(p\) (\(l \le p\)) obliczy ile lokalnych maksimów ma funkcja \(f\) w przedziale \([l, p]\).
6. Przypomnij sobie rozwiązania zadań z poprzednich ćwiczeń.
   Jeśli rozwiązałeś je nie stosując rekurencji ogonowej, to czy potrafisz je rozwiązać (lepiej) stosując ją?

Ćwiczenia 4 i 5: Listy

Ćwiczenie programistyczne na listy:

1. Lista \(n\) pierwszych liczb naturalnych.
2. Zdublować elementy listy.
3. Napisz procedurę last, której wynikiem jest ostatni element listy.
4. Napisz procedury head i tail, które dla zadanej listy \(l\) i liczby całkowitej \(n\)
   zwracają pierwsze/ostatnie \(n\) elementów listy \(l\).
   Jeśli lista \(l\) ma mniej elementów niż \(n\), to wynikiem powinna być cała lista \(l\).
   (Nazwy pochodzą od programów head i tail w Uniksie.)
   Co jest wynikiem tail (head l n) 1?
5. Napisz procedurę, która listę par postaci \([(n_1, x_1); (n_2, x_2); \dots; (n_k, x_k)]\) przekształca w listę postaci
   \([\underbrace{x_1; \dots; x_1}_{n_1 \mathrm{\ razy}}; \underbrace{x_2; \dots; x_2}_{n_2 \mathrm{\ razy}}; \dots; \underbrace{x_k; \dots; x_k}_{n_k \mathrm{\ razy}}]\).
6. Napisz procedurę shuffle: α list → α list → α list, która dla danych dwóch list postaci \([x_1; x_2; \dots; x_n]\) oraz \([y_1; y_2; \dots; y_m]\) wyznaczy listę postaci \([x_1; y_1; x_2; y_2; \dots]\). Jeżeli jedna z list jest dłuższa, to jej końcowe elementy trafiają na koniec listy wyikowej.
   Na przykład: shuffle [3; 2; 8; 1; 9; 3; 6] [5; 7; 0] = [3; 5; 2; 7; 8; 0; 1; 9; 3; 6].
   
   Rozwiązania
7. Załóżmy, że dana jest lista \([x_1; x_2; \dots; x_n]\).
   Sufiksem tej listy nazwiemy każdą listę, którą można uzyskać przez usunięcie pewnej liczby (od 0 do \(n\)) jej początkowych elementów.
   Tak więc, sufiksami danej listy będzie n.p. ona sama, pusta lista, a także \([x_3; x_4; \dots; x_n]\).

   Napisz procedurę tails : α list → α list list,
   która dla danej listy tworzy listę wszystkich jej sufiksów, uporządkowaną wg ich długości (wybrać, czy rosnąco, czy malejąco).

   Rozwiązania

8. Napisz funkcję wysun : int list -> int list, która dla danej listy posortowanej niemalejąco wybierze wszystkie jej elementy występujące
   więcej niż raz i umieści w liście wynikowej przed elementami występującymi tylko raz. Kolejność oraz liczba poszczególnych elementów występujących wiele razy ma pozostać taka sama jak w liście wejściowej. Podobnie dla elementów występujących raz.
   Na przykład: wysun [1;2;2;3;4;5;5;6;6;6;7] = [2;2;5;5;6;6;6;1;3;4;7]

   Rozwiązania

9. Ciąg liczb naturalnych \(x_0, x_1, \dots\) nazwiemy ciągiem Bonifacego wyznaczonym przez skończony niepusty ciąg zerojedynkowy \([b_0; \dots; b_{k−1}]\), jeśli \(x_0 = 0\), \(x_1 = 1\), \(x_2 = 1\), a dla \(i \ge 3\) zachodzi \(x_i = x_{i−1} + x_{i−2}\) jeśli \(b_i \mod k = 0\) oraz \(x_i = x_{i−1} + x_{i−3}\) dla \(b_i \mod k = 1\) (albo inaczej \(x_i = x_{i−1} + x_{i−2−b_{i \mod k}}\)).
   Na przykład ciąg \([1; 1; 0; 1]\) wyznacza ciąg Bonifacego: 0, 1, 1, 1, 2, 3, 5, 7, 10, 15, 25, 35, 50, ...
   Napisz funkcję bonifacy : int -> int list -> int, która dla liczby naturalnej n (n ≥ 0) oraz co najmniej trzyelementowej zerojedynkowej listy \([b_0; \dots; b_{k−1}]\) obliczy n-tą liczbę wyznaczonego przez tę listę ciągu Bonifacego.

   Rozwiązania

10. Dane są dwie listy liczb całkowitych uporządkowane niemalejąco.
    Oblicz ile różnych liczb występuje na tych listach.
11. Napisz procedurę zsumuj, która dla danej niemalejącej listy dodatnich liczb całkowitych
    \((a_1 \dots a_n)\) obliczy listę \((b_1 \dots b_n)\), gdzie \(b_i = \sum_{k=a_i}^n a_k\).
    (Pamiętaj o tym, że jeśli \(m>n\), \(\sum_{k=m}^n a_k = 0\).)
12. Napisz program wybierający \(\max\) i \(\min\) z listy i dokonujący (w miarę) jak najmniejszej liczby porównań.
13. Napisz program wybierający element dominujący z listy większościowej; uzasadnij jego poprawność.
14. Napisz procedurę podziel : int list → int list list, która dla danej listy postaci
    \([a_1; a_2; \dots; a_n]\), zawierającej permutację zbioru \(\{1, 2, \dots, n\}\) znajdzie jej podział na jak najliczniejszą listę list postaci:
    \[
    [[a_1; a_2; \dots; a_{k_1}];
    [a_{{k_1}+1}; a_{{k_1}+2}; \dots; a_{k_2}]; \dots;
    [a_{{k_{m-1}}+1}; a_{{k_{m-1}}+2}; \dots; a_{k_m}]]
    \]
    taką że:
    \begin{eqnarray*}
    \{a_1, a_2, \dots, a_{k_1}\} &=&
    \{1, 2, \dots, k_1\} \quad\mbox{(równość zbiorów)},\\
    \{a_{{k_1}+1}, a_{{k_1}+2}, \dots, a_{k_2}\} &=&
    \{k_1+1, k_1+2, \dots, k_2\},\\
    &\vdots& \\
    \{a_{{k_{m-1}}+1}, a_{{k_{m-1}}+2}, \dots, a_{k_m}\} &=&
    \{k_{m-1}+1, k_{m-1}+2, \dots, k_m\}.
    \end{eqnarray*}
    Przyjmujemy, że wynikiem dla listy pustej jest lista pusta.

    Przykład: \(\mathtt{podziel}\, [2; 3; 1; 6; 5; 4; 7; 9; 10; 11; 8] = [[2; 3; 1]; [6; 5; 4]; [7]; [9; 10; 11; 8]]\).

15. Napisz procedurę mieszaj, która wywołana dla danej listy, obliczy listę powstałą przez
    następujące przestawienie elementów: na pozycjach nieparzystych mają kolejno znajdować się \(\lceil \frac{n}{2} \rceil\)
    początkowe elementy danej listy, a na pozycjach parzystych mają znajdować się pozostałe elementy danej listy, w odwrotnej kolejności.
    Na przykład: \(\mathtt{mieszaj}\ [1;2;3;4;5] = [1;5;2;4;3]\).
16. Napisz procedurę trojki : int list → (int} * int * int) list,
    która dla zadanej listy dodatnich liczb całkowitych, uporządkowanej rosnąco, stworzy listę takich trójek \((a, b, c)\) liczb z danej listy, że:
    • \(a < b < c\),
    • liczby \(a\), \(b\) i \(c\) spełniają nierówność trójkąta, czyli \(c < a + b\).
17. Dana jest lista liczb całkowitych \(l = [x_1; \dots ; x_n]\) uporządkowana niemalejąco.
    Napisz procedurę: \(\mathtt{malo} : \mathtt{int~list} \to \mathtt{int}\), która dla danej listy \(l\) oblicza:
    \[ \min \left\{|x_i + x_j| : 1 \le i < j \le n \right\} \]
    Na przykład, malo [-42, -12, -8, -1, -1, 5, 15, 60] = 2.

    Możesz założyć, że dana lista \(l\) zawiera przynajmniej dwa elementy.

18. Dana jest niepusta, rosnąca lista liczb całkowitych \(l = [x_1; \dots ; x_n]\).
    Napisz procedurę: \(\mathtt{fit} : \mathtt{int} \to \mathtt{int~list} \to \mathtt{int}\), która dla danej liczby \(c\) i listy \(l\) obliczy:
    \[\min \left\{|c + x_i + x_j| : 1 \le i, j \le n \right\}\]
    Na przykład, fit 42 [-28, -25, -15, -1, 4, 8, 15, 60] = 1, ponieważ \(|42 - 28 - 15| = 1\).
19. Prostokątną tabelę wypełnioną liczbami całkowitymi reprezentujemy jako listę list liczb całkowitych -- każdy wiersz
    to lista liczb, a tabela to lista wierszy.
    Oczywiście wszystkie listy reprezentujące wiersze są równej długości.

    Rozpatrujemy tabele, których wiersze są uporządkowane ściśle rosnąco, a kolumny ściśle malejąco.
    Napisz procedurę znajdz : int list list → int → (int * int) list, która znajduje wszystkie pozycje, na
    jakich w takiej tabeli znajduje się podana liczba.

20. Rozważmy następującą metodę kompresji ciągów liczb całkowitych:
    Jeżeli w oryginalnym ciągu ta sama liczba powtarza się kilka razy z rzędu, to jej kolejne wystąpienia reprezentujemy za pomocą jednej tylko liczby.
    Konkretnie, \(i\) powtórzeń liczby \(k\) reprezentujemy w ciągu skompresowanym jako \(2^{i-1} \cdot (2 \cdot k - 1)\).

    Napisz procedurę dekompresuj : int list → int list dekompresującą zadaną listę.
    Możesz założyć, że lista skompresowana nie zawiera zer.

    Podaj specyfikację (warunek początkowy i końcowy) wszystkich definiowanych procedur i uzasadnij zwięźle ich pełną poprawność.
    W przypadku rekurencyjnych procedur iteracyjnych warunek początkowy musi zawierać niezmiennik iteracji.

     
          dekompresuj [1; 3; 3; 9; 42; 3];;
          - : int list = [1; 2; 2; 5; 11; 11; 2]
     

    Rozwiązania

21. Palindrom, to taka lista \(p\), że \(p = \mathtt{rev}\ p\).
    Napisz procedurę palindrom : α list → int,
    która dla danej listy obliczy długość jej najdłuższego spójnego fragmentu, który jest palindromem.
22. Napisz procedurę podziel : int → α list → α list list,
    która dla \(k > 0\) i listy \([x_1; \dots; x_n]\) podzieli ją na listę list postaci:
    \[ [
    [x_1; x_{k+1}; x_{2k+1}; \dots];
    [x_2; x_{k+2}; x_{2k+2}; \dots]; \dots;
    [x_k; x_{2k}; x_{3k}; \dots]
    ]\]

    Przykład: \(\mathtt{podziel}\ 3\ [1;2;3;4;5;6;7] = [[1; 4; 7]; [2; 5]; [3; 6]] \).

23. [XIII OI]
    Mały Jaś dostał od rodziców na urodziny nową zabawkę, w której skład wchodzą rurka i krążki.
    Rurka ma nietypowy kształt -- mianowicie jest to połączenie pewnej liczby walców (o takiej samej grubości)
    z wyciętymi w środku (współosiowo) okrągłymi otworami różnej średnicy.
    Rurka jest zamknięta od dołu, a otwarta od góry.
    Krążki w zabawce Jasia są walcami o różnych średnicach i takiej samej grubości co walce tworzące rurkę.

    Jaś wymyślił sobie następującą zabawę.
    Mając do dyspozycji pewien zestaw krążków zastanawia się, na jakiej głębokości zatrzymałby się ostatni z nich,
    gdyby wrzucać je kolejno do rurki centralnie (czyli dokładnie w jej środek).
    Każdy kolejny krążek po wrzuceniu spada dopóki się nie zaklinuje (czyli nie oprze się o walec, w którym wycięty jest
    otwór o mniejszej średnicy niż średnica krążka), albo nie natrafi na przeszkodę w postaci innego krążka lub dna rurki.

    Napisz procedurę krążki : int list → int list → int, która na podstawie listy średnic
    otworów w kolejnych walcach tworzących rurkę, oraz listy średnic kolejno wrzucanych krążków obliczy głębokość, na której zatrzyma się
    ostatni wrzucony krążek (lub 0 jeśli nie wszystkie krążki zmieszczą się w rurce).
    
    Rozwiązania

24. System \(-2\)-kowy jest podobny do systemu binarnego, ale podstawą tego systemu jest liczba \(-2\).
    Są dwie możliwe cyfry: 0 i 1.
    Ciąg cyfr postaci \(c_k c_{k-1} \dots c_1 c_0\) reprezentuje liczbę \(\sum_{i=0}^k c_i(-2)^i\).
    Na przykład, liczbę 42 reprezentujemy jako \(1111110_{-2}\).
    Kolejne cyfry, od mniej do bardziej znaczących, tworzą listę.
    Przyjmujemy, że lista pusta reprezentuje 0.
    1. [V OI, zadanie Bankomaty]
       Napisz procedurę \(\mathtt{neg2\_of\_int} : \mathtt{int} \to \mathtt{int~list}\), która przekształca daną liczbę całkowitą
       w jej reprezentację w systemie \(-2\)-kowym.
    2. Napisz procedurę \(\mathtt{int\_of\_neg2} : \mathtt{int} \to \mathtt{int~list}\), która przekształca reprezentację
       w systemie \(-2\)-kowym w liczbę całkowitą.
    3. Napisz procedurę \(\mathtt{inc} : \mathtt{int~list} \to \mathtt{int~list}\), która dla
       danej listy będącej reprezentacją liczby \(x\), wyznaczy reprezentację liczby \(x+1\).
    4. Napisz procedurę \(\mathtt{inv} : \mathtt{int~list} \to \mathtt{int~list}\), która dla
       danej listy będącej reprezentacją liczby \(x\), wyznaczy reprezentację liczby \(-x\).
    5. Napisz procedurę \(\mathtt{dodawanie} : \mathtt{int~list} \to \mathtt{int~list} \to \mathtt{int~list}\), która dla
       danych dwóch reprezentacji liczb całkowitych w systemie \(-2\)-ym obliczy reprezentację ich sumy.
       Na przykład: dodawanie [1;0;1;0;0;1;1] [1;0;1] = [0;1;1;1;1;1;1].
25. Wielomian postaci \(a_0 \cdot x^0 + a_1 \cdot x^1 + \cdots + a_n \cdot x^n\) reprezentujemy w postaci listy \([a_0; a_1; \dots; a_n]\).
    Napisz procedurę mnóż : float list → float list → float list mnożącą wielomiany.

    Uwaga: Pusta lista reprezentuje zerowy wielomian.

Ćwiczenia 6: Struktury danych

Ćwiczenie programistyczne na drzewa i inne struktury danych:

1. Zdefiniuj typ reprezentujący drzewa o wierzchołkach dowolnego (skończonego) stopnia.
   Zdefiniuj garść procedur operujących na takich drzewach (np. głębokość, liczbę elementów, lista elementów w porządku prefiksowym/postfiksowym).
2. Dana jest deklaracja typu drzew binarnych:

    
        type α tree = 
          Node of α tree * α  * α tree | 
          Null;;
    

   Drzewo nazywamy ultralewicowym jeśli głębokości kolejnych liści (Null), od lewej do prawej, tworzą ciąg nierosnący.
   Napisz procedurę ultraleft : α tree → bool, która sprawdza czy dane drzewo jest ultralewicowe.

3. [II OI, zadanie Obchodzenie drzewa skokami]
   Jak obejść wszystkie wierzchołki drzewa (ogólnego) tak, aby odległość między kolejnymi
   wierzchołkami nie przekraczała 3.
4. Dana jest deklaracja typu drzew binarnych:

    
         type α tree = 
           Node of α tree * α * α tree | 
           Nil;;
    

   Napisz procedurę liscie : α tree → α list, która tworzy listę wartości znajdujących się w liściach (Node) drzewa.

5. Napisz procedurę, która dla dowolnego drzewa binarnego poprawia je tak, że spełnia ono słabszą wersję warunku BST:
   dla dowolnego węzła, lewy syn nie jest większy, a prawy nie jest mniejszy, niż węzeł.
6. Napisz funkcję potnij, która dla danego predykatu \(p\) typu \(\alpha \to \mathtt{bool}\), oraz drzewa \(t\) typu \(\mathtt{\alpha\ tree}\), zwróci następujący wynik.
   Wybierzmy wszystkie węzły drzewa \(t\) zawierające wartości, które spełniają predykat \(p\) i usuńmy z drzewa krawędzie łączące te węzły z ich rodzicami (w przypadku korzenia, nie usuwamy żadnej krawędzi).
   W rezultacie drzewo \(t\) może się rozpaść na pewną liczbę mniejszych drzew.
   potnij p t powinno zwrócić listę tych drzew (w dowolnej kolejności).
7. Napisz procedurę rozcięcie, która znajduje taką krawędź w danym drzewie binarnym, że po jej usunięciu drzewo
   rozpada się na dwa drzewa o minimalnej różnicy liczb węzłów.
   (Wynikiem procedury powinien być dolny koniec szukanej krawędzi.)
   
   Rozwiązania
8. [PCh]
   Dana jest deklaracja typu drzew binarnych:
   type tree = Node of tree * int * tree | Null;;
   Napisz procedurę \(\mathtt{symetryczne} : \mathtt{tree} \to \mathtt{bool}\), która sprawdza, czy drzewo jest symetryczne (ze względu na odbicie lewo-prawo).
9. Dana jest deklaracja typu reprezentującego wyrażenia logiczne:

    
         type expr = 
           And of expr * expr |
           Or of expr * expr |
           Not of expr | 
           Value of bool;;
    

   Warianty And, Or i Not reprezentują odpowiednie operacje logiczne,
   natomiast wariant Value reprezentuje wartość logiczną true lub false.

   Napisz funkcję wartościowania : expr → int,
   która dla danego wyrażenia policzy na ile różnych sposobów można przypisać wszystkim
   wariantom Value wartości logiczne, tak aby wartość całego wyrażenia wyliczała się do true.

   Przykład: wartościowania Or(Value true, Value false) = 3,
   gdyż wyrażenie wyliczy się do true, w trzech przypadkach:
   Or(Value true, Value true), Or(Value true, Value false), Or(Value false, Value true).

10. Dana jest deklaracja typu drzew binarnych:

     
          type 'a tree = 
            Node of 'a * 'a tree * 'a tree | 
    	Null;;
     

    Skosokość drzewa jest zdefiniowana w następujący sposób:

    • skosokość Null wynosi 0,
    • skosokość \(\mathtt{Node}(x, t_1, t_2)\) jest równa \(\max(2 \cdot s_1, 2 \cdot s_2 + 1)\), gdzie \(s_1\) i \(s_2\) to skosokości, odpowiednio, \(t_1\) i \(t_2\).

    Dla danego drzewa wolno nam w dowolnych jego węzłach zamieniać miejscami lewe i prawe poddrzewa.
    Napisz procedurę \(\mathtt{skosokosc}: \alpha\ \mathtt{tree} \to \alpha\ \mathtt{tree}\), która przekształca dane drzewo tak, aby zminimalizować jego skosokość.
    Na przykład, dla:

     
          t = Node(5,
                Node(4, Null, Node(2, Null, Null)), 
                Node(6, 
                  Node(1, Null, Null), 
                  Node(3, Null, Null)
                )
              )
     
          skosokosc t = Node(5,
                          Node(6, 
                            Node(1, Null, Null), 
                            Node(3, Null, Null)
                          ),
                          Node(4, Node(2, Null, Null), Null) 
                        )
     

    Skosokość tak uzyskanego drzewa wynosi 6.

11. [CLR, ćw. 16-4]
    Firma planuje zorganizować przyjęcie. Hierarchia stanowisk w firmie ma strukturę drzewa (ogólnego):

     
          type tree = Node of (int * tree list);;
     

    Każdy pracownik charakteryzuje się pewną "towarzyskością" wyrażoną liczbą dodatnią.
    Napisz program, który dobierze gości tak, aby:

    • na przyjęciu nie był obecny bezpośredni przełożony żadnego z gości,
    • suma współczynników towarzyskości gości była maksymalna.

    Jak zapewnić, aby szef firmy był na przyjęciu?

12. Dane jest definicja typu:

     
          type tree = 
            Node of tree * tree | 
    	Null
     

    .
    Odległością między dwoma wierzchołkami (Node) w drzewie nazywamy minimalną
    liczbę krawędzi jakie trzeba przejść z jednego wierzchołka do drugiego.
    Średnicą drzewa nazwiemy maksymalną odległość między dwoma węzłami (Node) w drzewie.
    Przyjmujemy, że średnica pustego drzewa (Null) jest równa 0.

    Napisz procedurę średnica : tree → int, która oblicza średnicę danego drzewa.
    
    Rozwiązania

13. Dana jest deklaracja typu:

            type 'a drzewo = Node of 'a * 'a drzewo * 'a drzewo | Null
     

    Napisz procedurę polowa:'a drzewo -> 'a drzewo, która znajduje w zadanym drzewie taki węzeł (Node), który jest przodkiem jak najmniejszej liczby liści, ale przynajmniej połowy wszystkich liści drzewa.

14. Dana jest deklaracja typu drzew:

          type tree = 
            Node of int * tree * tree |
            Leaf;;
     

    Napisz procedurę \(\mathtt{odchudzanie}: \mathtt{tree} \to \mathtt{tree}\), która mając dane drzewo binarne, zwraca drzewo powstałe przez usunięcie z niego takich poddrzew
    (zastępując Node(...) przez Leaf) aby suma elementów w powstałym drzewie była jak największa.

15. Dana jest deklaracja typu:

     
          type  drzewo =
            Node of α * α drzewo * α drzewo |
            Null 
     

    Napisz procedurę środek : α drzewo → α drzewo, która znajduje w zadanym drzewie taki
    węzeł (Node), dla którego maksymalna spośród jego odległości od liści jest jak najmniejsza.
    Wynikiem tej procedury powinno być poddrzewo zakorzenione w wyznaczonym węźle.

    Co się zmieni, jeżeli będziemy chcieli znaleźć wierzchołek, dla którego
    minimalna spośród jego odległości do liścii jest jak największa?

16. Dana jest deklaracja typu drzew binarnych, w których węzłach znajdują się liczby całkowite:

     
          type tree = 
            Node of int * tree * tree |
            Null 
     

    Przekrojem drzewa nazwiemy dowolny taki zbiór jego wierzchołków (Node), że na każdej ścieżce
    od korzenia do liścia (Null) znajduje się dokładnie jeden wierzchołek należący do przekroju.

    Napisz procedurę cut : tree → int, która dla danego drzewa wyznaczy najmniejszą możliwą sumę liczb
    znajdujących się w wierzchołkach tworzących przekrój danego drzewa.

17. Rozważmy drzewo binarne, w którego wierzchołkach pamiętane są różne dodatnie liczby całkowite.
    Dane są dwie listy: wyniki obejścia drzewa w porządku infiksowym i prefiksowym.
    Napisz procedurę, która odtwarza drzewo na podstawie takich dwóch list.
18. Napisz procedurę, która przekształca dane drzewo binarne w wyważone drzewo binarne, zachowując kolejność elementów w porządku infiksowym.
19. Dana jest definicja typu drzew dowolnego stopnia:

              type α tree = Node of α * α tree list;;
     

    Napisz procedurę \(\mathtt{liscie} : \alpha\ \mathtt{tree} \to \mathtt{int~list}\), która dla danego drzewa liczy ile w tym drzewie jest liści na poszczególnych głębokościach i zwraca listę liczb postaci \([g_0; g_1; \dots; g_h]\), gdzie \(g_i\) to liczba liści znajdujących się na głębokości \(i\), a \(h\) to wysokość drzewa.

20. Dana jest deklaracja typu drzew:

            type α tree = Node of α  * α tree list;;
     

    Ścieżkę w drzewie nazwiemy rosnącą, jeżeli wartości w węzłach na tej ścieżce, w kierunku od korzenia w dół, są rosnące.
    Napisz procedurę rosnaca: int tree → int list, która znajdzie w danym drzewie najdłuższą ścieżkę rosnącą i zwróci wartości znajdujące się na niej (w kolejności od korzenia w dół). (Uwaga: szukana ścieżka nie musi zaczynać się w korzeniu i nie musi kończyć się w liściu.)
    
    Rozwiązania

21. Dana jest deklaracja typu drzew:

            type α tree = Node of α  * α tree list;;
     

    Napisz procedurę nieparzyste: α tree → int, która dla danego drzewa policzy ile jest w nim poddrzew zawierających nieparzystą liczbę wierzchołków.

22. Dana jest deklaracja typu drzew binarnych:

     
          type tree = Node of tree * int * tree | Null;;
     

    Napisz procedurę czapeczka : tree → tree → int, która obliczy na ilu poziomach, idąc od góry,
    dane drzewa są identyczne, tzn. na tych poziomach drzewa mają ten sam kształt, a w odpowiadających sobie wierzchołkach są takie same liczby.

Ćwiczenia 7: Moduły

[D.L.Parnas, On the Criteria To Be Used in Decomposing Systems into Modules, CACM 12 (15), 1972]
Rozważmy następujący problem. Należy napisać program, który:

• wczyta plik tekstowy,
• dany plik składa się z wierszy, a każdy wiersz ze słów oddzielonych białymi znakami,
• rozważamy rotacje cykliczne wierszy, powstałe przez przestawienie pewnej liczby słów z początku wiersza na koniec,
• program ma wypisać wszystkie możliwe rotacje cykliczne wierszy z wejścia, bez powtórzeń,
  w porządku leksykograficznym, oddzielając słowa w wierszach pojedynczymi odstępami.

Podaj jak byś podzielił program na moduły.
Wymyśl zestaw realistycznych modyfikacji, jakie należy wprowadzić (a jeszcze lepiej poproś o to kolegę) i sprawdź, jak sprawuje się wymyślony przez Ciebie podział na moduły.

Zdefiniuj sygnatury/struktury odpowiadające podanym poniżej pojęciom.
Staraj się wykorzystać zdefiniowane wcześniej pojęcia.

1. Sygnatura półgrupy (typ elementów i operacja łączna).
2. Sygnatura monoidu (półgrupa z elementem neutralnym).
   Struktura monoidu:
   • liczby całkowite z dodawaniem,
   • funkcje (na liczbach całkowitych) z operacją składania,
   • listy (liczb całkowitych) z operacją sklejania,
   • macierzy \(2 \times 2\) z operacją mnożenia.
3. Sygnatura grupy (monoid z elementami odwrotnymi).
4. Sygnatura pierścienia (dodawanie, mnożenie, jedynka, zero, elementy przeciwne).
5. Struktura pierścienia liczb całkowitych.
6. Sygnatura ciała (pierścień z elementami odwrotnymi).
7. Struktura ciała liczb rzeczywistych.
8. Sygnatura porządku częściowego z operacjami sup i inf.
9. Struktura implementująca porządek częściowy par liczb całkowitych z operacjami sup i inf.
   Przyjmujemy, że \((x_1, y_1) \le (x_2, y_2)\) gdy \(x_1 \le x_2\) oraz \(y_1 \le y_2\).
10. Zdefiniuj moduł implementujący przechadzkę -- "kursor" do przechadzania się po drzewach i oglądania go:

     
          sig 
            type α tree = 
              Node of α tree * α  *  α tree |
              Null
            type α walk
            make     : α tree  → α walk
            goleft   : α walk → α walk
            goright  : α walk → α walk
            goup     : α walk → α walk
            lookup   : α walk → α tree
            exception OutsideTree
          end
     

    Wywołanie make d powinno konstruować przechadzkę, w której znajdujemy się w korzeniu drzewa d.
    Wywołanie goleft p powinno konstruować przechadzkę powstałą przez przejście do lewego poddrzewa.
    Analogicznie powinny działać procedury goright i goup.
    Procedura lookup powinna zwrócić poddrzewo zaczepione w wierzchołku drzewa, w którym aktualnie jesteśmy.

    Podczas przechadzki po drzewie możemy przebywać jedynie w wierzchołkach Node _.
    Jeśli nastąpi próba wejścia do Null'a lub wyjścia ,,ponad'' korzeń, należy podnieść wyjątek OutsideTree.

Ćwiczenia 8: Procedury wyższych rzędów

Ćwiczenia na procedury wyższych rzędów, ale bez standardowych procedur wyższych rzędów przetwarzających listy:

1. Potęgowanie funkcji.
   Zasymuluj działanie na prostych przykładach:

    
         iterate 2 (function x -> x * (x+1)) 2
         iterate 3 (function x -> x * (x+1)) 1
    

   rozrysowując ramki.
   W przypadku szybszego potęgowania funkcji co tak na prawdę jest obliczane szybciej: funkcja wynikowa, czy jej wartość?
   
   Rozwiązania

2. Wygładzenie funkcji z odstępem \(dx\) polega na uśrednieniu \(f(x - dx)\), \(f(x)\) i \(f(x + dx)\).
   Napisz procedurę wygładzającą daną funkcję z zadanym odstępem.
   Zwróć uwagę na kolejność argumentów.
3. Niech \(f : {\cal R} \to {\cal R}\) będzie funkcją:
   • wzajemnie jednoznaczną, czyli 1-1 i ,,na'',
   • ciągłą,
   • rosnącą i to tak, że \(\forall_{d>0} f(x+d) - f(x) \ge d\),
   • oraz taką, że \(f(0)=0\).

   Zaimplementuj procedurę odwrotnosc, której wynikiem dla parametru \(f\) będzie przybliżenie \(f^{-1}\) z dokładnością
   zadaną przez stałą epsilon (czyli jeśli \(g = (\mathtt{odwrotnosc}\ f)\), to \(\forall x\ |g(x) - f^{-1}(x)| \le \mathtt{epsilon}\)).

4. Zaimplementuj aproksymację funkcji za pomocą szeregu Taylora.
   Twoja procedura powinna mieć następujące parametry: liczbę sumowanych wyrazów szeregu punkt, w którym
   badana jest przybliżana funkcja, oraz daną funkcję.
   Wynikiem powinno być przybliżenie funkcji.
   Zastosuj przybliżenie pochodnej oraz sumy częściowe szeregów, przedstawione na wykładzie.

Ćwiczenia 9 i 10: Procedury wyższych rzędów i listy

Ćwiczenia na listy z elementami procedur wyższych rzędów:

1. Napisz procedurę exists, która dla danego predykatu i listy sprawdzi, czy na liście jest element spełniający predykat.
   Wykorzystaj wyjątki tak, aby nie przeglądać listy, gdy to już nie jest potrzebne.
2. Napisz procedurę negującą predykat non: (α → bool) → (α → bool).
   Za pomocą tej procedury oraz procedury exists zdefiniuj procedurę forall,
   która sprawdza, czy dany predykat jest spełniony przez wszystkie elementy danej listy.
   Czy zastosowanie wyjątków w implementacji procedury exists nadal powoduje, że przeglądane są tylko niezbędne elementy listy?
3. Zapisz procedurę append za pomocą fold_right/fold_left.
4. Napisz procedurę obliczającą funkcję będącą złożeniem listy funkcji.
5. Zapisz za pomocą map i flatten procedurę heads,
   której wynikiem dla danej listy list, jest lista pierwszych elementów niepustych list składowych.
   Puste listy składowe nie powinny wpływać na wynik.
   
   Rozwiązania
6. Dana jest lista list elementów. Napisz procedurę \(\mathtt{ostatki}: \alpha\ \mathtt{list~list} \to \alpha\ \mathtt{list}\), która zwraca listę ostatnich elementów list składowych.
   Kolejność elementów w wyniku powinna być taka jak kolejność list składowych, z których pochodzą.
   Puste listy składowe nie wpływają na wynik.
7. Napisz procedurę sumy : int list → int list, która dla danej listy \([x_1;\dots; x_n]\)
   oblicza listę postaci: \([x_1; x_1 + x_2; x_1+x_2+x_3; \dots; x_1+x_2+\cdots+x_n]\).
   
   Przykład: sumy [1; 5; 2; 7; 12; 10; 5] = [1; 6; 8; 15; 27; 37; 42].
   
   Rozwiązania
8. Napisz procedurę codrugi : α list → α list, która z danej listy wybiera co drugi element (zaczynając od drugiego).
   Na przykład codrugi [1; 2; 3; 4; 5] = [2; 4].
9. Jaś pracuje wykonując zlecenia, które dostaje od swojego szefa. Wykonuje je w kolejności ich otrzymania. Wykonanie każdego zlecenia zajmuje mu określony czas. Masz daną tablicę par: moment otrzymania zlecenia, czas potrzebny na jego wykonanie, posortowaną ściśle rosnąco po momentach otrzymania zleceń.
   Napisz procedurę \(\mathtt{zlecenia}: (\mathtt{int} * \mathtt{int})\ \mathtt{list} \to \mathtt{int~list}\), która dla każdego zlecenia wyznaczy ile czasu upłynie od momentu otrzymania zlecenia do momentu jego wykonania.
   Na przykład: zlecenia [(-1, 1); (2, 2); (3, 3); (4, 2); (10, 2)] = [1; 2; 4; 5; 2]}.
   
   Rozwiązania
10. Dany jest ciąg liczb całkowitych (niekoniecznie dodatnich). Element takiego ciągu nazwiemy widocznym, jeśli suma poprzedzających go elementów jest taka sama, jak suma elementów występujących po nim.
    Napisz procedurę \(\mathtt{widoczne}:\mathtt{int~list} \to \mathtt{int~list}\), która z danej listy liczb całkowitych wybierze te, które są widoczne.
    
    Rozwiązania
11. Listę nazwiemy ciekawą jeśli żadne dwa kolejne jej elementy nie są sobie równe.
    Napisz procedurę podzial : α list → α list list, która daną listę podzieli na
    minimalną liczbę spójnych fragmentów (zachowując ich kolejność), z których każdy jest ciekawy.
    Na przykład, podzial [3;2;2;5;7;5;4;4;3;1] = [[3;2];[2;5;7;5;4];[4;3;1]].
    
    Rozwiązania
12. Napisz procedurę \(\mathtt{wybory}: \mathtt{int~list} \to \mathtt{int}\), która mając daną posortowaną niemalejąco listę liczb całkowitych, znajdzie liczbę która pojawia się na niej najwięcej razy (w przypadku takiej samej liczby wystąpień, wybierz największą taką liczbę).
    
    Rozwiązania
13. Dana jest lista liczb całkowitych. Element tej listy nazwiemy prextremum jeśli jest ostro większy lub ostro mniejszy od wszystkich elementów poprzedzających go na danej liście.
    Napisz procedurę \(\mathtt{prextrema}: \mathtt{int~list} \to \mathtt{int~list}\), która dla danej listy zwraca listę wszystkich jej prextremów.
    Elementy na liście wynikowej powinny być w takiej samej kolejności, w jakiej występowały na danej liście.
    Na przykład:
    prextrema [-2; 1; 0; 1; 3; 2; -1; 5; 4; -3; 2; 1; 7] = [-2; 1; 3; 5; -3; 7]
    
    Rozwiązania
14. Napisz procedurę \(\mathtt{wzrost}: \mathtt{int~list} \to \mathtt{int~list}\), która dla danej listy liczb całkowitych
    znajduje w niej najdłuższy spójny fragment ściśle rosnący i zwraca go.
    Na przykład:

     
          wzrost [3; 4; 0; -1; 2; 3; 7; 6; 7; 8] = [-1; 2; 3; 7]
          wzrost [] = []
     

    Rozwiązania

15. Dany jest ciąg \(n\) kulek ułożonych w rządku. Każda kulka jest czerwona lub zielona. Maciek chciałby ułożyć kulki naprzemiennie: zielona, czerwona, zielona itd. Niestety liczby kulek zielonych i czerwonych nie muszą być równe. Maćkowi wystarczy jeśli ciąg kulek będzie (od lewej) zaczynał się naprzemiennie od zielonej kulki. Natomiast pewien fragment ciągu kulek od prawej strony może być jednokolorowy. (W szczególności, jeśli w danym ciągu są kulki tylko jednego koloru, to wynikowy ciąg też musi być jednokolorowy.)
    Maciek w jednym ruchu może zamienić miejscami dowolnie dwie wybrane kulki w ciągu.
    Dana jest deklaracja typu: type kolor = Czerwona | Zielona.
    Napisz procedurę \(\mathtt{kulki}: \mathtt{kolor~list} \to \mathtt{int}\), która mając daną liste opisującą ciąg kulek (od lewej do prawej) wyznaczy minimalną liczbę ruchów, w jakich Maciek może ułożyć ciąg kulek tak jak to opisano.
    Na przykład: kulki [Czerwona, Zielona, Zielona, Zielona, Zielona, Czerwona, Czerwona, Zielona] = 2.
16. Dana jest lista \([x_1; x_2; \dots; x_n]\) reprezentująca kolejne chwile w czasie -- tzn. $x_i\) reprezentuje chwilę \(i\).
    Dane są też dwa predykaty \(p\) i \(q\).
    Powiemy, że w chwili \(i\) zachodzi ,,\(p\) dopóki \(q\)'', jeżeli istnieje takie \(0 \le k \le n-i\), że
    zachodzi \(p\ x_i, p\ x_{i+1}, \dots, p\ x_{i+k-1}\), oraz \(q\ x_{i+k}\).
    Inaczej mówiąc, począwszy od chwili \(i\) musi zachodzić \(p\), dopóki nie zajdzie \(q\).
    W szczególności, jeżeli zachodzi \(q\ x_i\), to \(p\) nie musi w ogóle zachodzić.

    Napisz taką procedurę dopoki : α list → (α → bool) → (α → bool) → int list, że wynikiem
    \(\mathtt{dopoki}\ [x_1; x_2; \dots; x_n]\ p\ q\) jest lista tych chwil w czasie, w których zachodzi \(p\) dopóki \(q\).

    Na przykład, dla następujących \(p\) i \(q\):
    

    \(i\)	1	2	3	4	5	6	7	8	9	10	11	12
    \(p\ x_i\)	false	true	true	true	false	false	true	true	true	false	false	false
    \(q\ x_i\)	false	false	true	false	true	false	false	true	false	false	true	false

    
    poprawnym wynikiem jest: \([2; 3; 4; 5; 7; 8; 11]\).
17. Dla danej listy liczb całkowitych \(l = [x_1; x_2; \dots; x_n]\), minimum (maksimum) nazwiemy
    taki fragment listy \(x_i = x_{i+1} = \dots = x_j\), że:
    • \(1 \le i \le j \le n\),
    • jeśli \(i > 1\), to \(x_{i-1} > x_i\) (\(x_{i-1} < x_i\)),
    • jeśli \(j < n\), to \(x_j < x_{j+1}\) (\(x_j > x_{j+1}\)).

    Ekstremum oznacza minimum lub maksimum.
    Napisz procedurę ekstrema :int list → int, która dla danej listy policzy ile jest na niej ekstremów.
    
    Rozwiązania

18. System -2-kowy jest podobny do systemu binarnego, ale podstawą tego systemu jest liczba -2. Są dwie możliwe cyfry: 0 i 1.
    Ciąg cyfr postaci \(c_k c_{k-1} \dots c_1 c_0\) reprezentuje liczbę \(\sum_{i=0}^k c_i(-2)^i\).
    Na przykład, liczbę 42 reprezentujemy jako \(1111110_{-2}\).

    Napisz procedurę inc : int list → int list, która dla danej listy będącej reprezentacją liczby \(x\),
    wyznaczy reprezentację liczby \(x+1\).
    Przyjmujemy, że lista pusta reprezentuje 0.

19. Maksymalne plateau w liście (bez rekurencji).
    Napisz procedurę plateau : α list → int, która oblicza długość najdłuższego stałego (spójnego) fragmentu danej listy.
20. Zdefiniuj, za pomocą @ i filter uproszczoną wersję algorytmu quick-sort.
    W algorytmie tym elementy sortowanej listy dzielimy na nie większe i większe od pierwszego elementu listy,
    po czym obie listy wynikłe z podziału rekurencyjnie sortujemy.
    
    Rozwiązania
21. Ciąg różnicowy ciągu \([x_1; x_2; \dots; x_n]\), to ciąg postaci \([x_2-x_1; x_3-x_2; \dots; x_n-x_{n-1}]\).
    Oblicz ciąg różnicowy zadanej listy liczb całkowitych.
22. Oblicz listę złożoną z pierwszych elementów kolejnych ciągów różnicowych danej listy,
    tzn.: głowy danej listy, gowy jej ciągu różnicowego, głowy ciągu różnicowego jej ciągu różnicowego itd.
23. Dana jest lista liczb zmiennopozycyjnych \([x_1; x_2; \dots; x_n]\).
    Jej uśrednienie, to lista postaci: \([\frac{x_1 +. x_2}{2.0}; \dots; \frac{x_{n-1} +. x_n}{2.0}]\).
    Uśrednieniem listy jednoelementowej oraz pustej jest lista pusta.

    Napisz procedurę usrednienie : float list → float list, która dla danej listy obliczy jej uśrednienie.

24. Napisz funkcję od_końca_do_końca : int list → int, która dla danej niepustej
    listy \([a_1;...;a_n]\) obliczy \(\min_{i=1,2,\dots,n} |a_i - a_{n+1-i}|\).
25. Załóżmy, że dana jest lista \([x_1; x_2; \dots; x_n]\).
    Sufiksem tej listy nazwiemy każdą listę, którą można uzyskać przez usunięcie pewnej liczby (od 0 do \(n\)) jej początkowych elementów.
    Tak więc sufiksami danej listy będzie n.p. ona sama, pusta lista, a także \([x_3; x_4; \dots; x_n]\).
    
    Napisz (za pomocą fold_left/fold_right) procedurę tails : α list → α list list,
    która dla danej listy tworzy listę wszystkich jej sufiksów, uporządkowaną wg malejących ich długości.
26. Rozważmy listę liczb całkowitych \([x_1; x_2; \dots; x_n]\).
    Dołkiem na tej liście nazwiemy taki indeks \(1 < i < n\), że \(x_i < \max(x_1, \dots, x_{i-1})\) oraz \(x_i < \max(x_{i+1}, \dots, x_n)\).
    Głębokość takiego dołka to \(\min(\max(x_1, \dots, x_{i-1}) - x_i, \max(x_{i+1}, \dots, x_n) - x_i)\).
    Napisz procedurę \(\mathtt{dolek}: \mathtt{int~list} \to \mathtt{int}\), która dla danej listy liczb całkowitych wyznaczy maksymalną głębokość dołka na tej liście.
    Jeśli na danej liście nie ma żadnego dołka, to poprawnym wynikiem jest 0.
27. Lista trójek \([(l_1,s_1,r_1); \dots; (l_k,s_k,r_k)]\) : (α list * int * int) list} reprezentuję listę
    elementów typu α w następujący sposób.
    Trójka \((l,s,r)\), gdzie \(l = [x_1; x_2; \dots; x_s]\) jest \(s\)-elementową listą elementów typu α,
    reprezentuje ciąg \(r\)-elementowy, poprzez cykliczne powtarzanie elementów ciągu \(l\):
    \[\underbrace{x_1, x_2, \dots, x_s, x_1, x_2, \dots, x_s, x_1, \dots}_{r \mbox{ elementów}}\]
    Z kolei lista trójek reprezentuje listę powstała w wyniku konkatenacji list odpowiadających poszczególnym trójkom.
    
    Napisz procedurę dekompresja : (α list * int * int) list → int → α, która
    dla danej listy trójek i indeksu \(i\) wyznacza \(i\)-ty element listy wynikowej.
28. Rozważmy następującą metodę kompresji ciągów liczb całkowitych:
    Jeżeli w oryginalnym ciągu ta sama liczba powtarza się kilka razy z rzędu, to jej kolejne wystąpienia reprezentujemy za pomocą jednej tylko liczby.
    Konkretnie, \(i\) powtórzeń liczby \(k\) reprezentujemy w ciągu skompresowanym jako \(2^{i-1} \cdot (2 \cdot k - 1)\).
    
    Napisz procedurę kompresuj : int list → int list kompresującą zadaną listę.
    Lista wynikowa powinna być oczywiście jak najkrótsza.

     
          kompresuj [1; 2; 2; 5; 11; 11; 2];;
          - : int list = [1; 6; 9; 42; 3]
     

29. Listę nazwiemy dobrą, jeśli zawiera elementy o naprzemiennych znakach (dodatnie i ujemne).
    Listę nazwiemy prawie dobrą, jeśli jest dobra lub zawiera co najwyżej jedno zero, a po obu jego stronach jest dobra.
    Szukamy najdłuższego spójnego fragmentu danej listy liczb całkowitych, który jest prawie dobry.
    Napisz procedurę \(\mathtt{prawie}: \mathtt{int~list} \to \mathtt{int}\), która zwraca długość takiego fragmentu.
    Na przykład: prawie [3; 2; -2; 0; 42; 22; -12; 15; -4] = 4.
    Są dwa takie fragmenty: [2; -2; 0; 42] i [22; -12; 15; -4].
30. Przy windzie (na parterze) ustawiła się kolejka ludzi, którzy chcą wjechać windą (wszyscy do góry). Jednorazowo windą mogą jechać osoby o łącznym ciężarze nie większym niż \(w\).
    Do windy zawsze wsiada maksymalnie dużo osób z początku kolejki, których łączny ciężar nie przekracza \(w\).
    Napisz procedurę winda: int → int list → int, która mając dane \(w\) oraz listę ciężarów kolejnych osób czekających na windę policzy minimalną liczbę kursów windy potrzebnych do obsłużenia czekających.
    Możesz założyć, że ciężary osób czekających na windę są liczbami dodatnimi, nie większymi od \(w\).
    Rozwiązując to zadanie, nie możesz tworzyć żadnych własnych procedur rekurencyjnych.
    Zamiast tego należy wykorzystać standardowe procedury wyższych rzędów przetwarzające listy.
    
    Rozwiązania
31. Napisz procedurę buduj_permutacje : α list list → α → α,
    która przyjmuje permutację w postaci rozkładu na cykle i zwraca ją w postaci procedury.
    
    Lista składowa postaci \([a_1; \dots; a_n]\), gdzie \(a_i \neq a_j\) dla \(1 \leq i < j \leq n\),
    reprezentuje cykl, czyli permutację przeprowadzającą \(a_i\) na \(a_{(i \bmod n) + 1}\) dla \(1 \leq i \leq n\).
    Możesz założyć, że listy składowe są niepuste.
    
    Lista list \([c_1; \dots; c_k]\), gdzie listy \(c_i\) dla \(1 \leq i \leq k\) reprezentują cykle, reprezentuje permutację złożoną z tych cykli.
    Możesz założyć, że wszystkie cykle są rozłączne.
    
    Przyjmujemy, że dla wartości \(x\) nie występujących na żadnej z list \(c_i\) mamy: buduj_permutacje \([c_0; \dots; c_k]\ x = x\).
    W szczególności, przyjmujemy, że pusta lista reprezentuje permutację identycznościową.

     
          let p = buduj_permutacje [[2; 1]; [8; 3; 4]; [5; 7; 6; 10]; [11]];;
          map p [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12];;
          -: int list = [2; 1; 4; 8; 7; 10; 6; 3; 9; 5; 11; 12]
     

32. Napisz procedurę podzial : int list → int list list, która dla danej listy liczb całkowitych
    \(l=[x_1; x_2; \dots; x_n]\) podzieli ją na listę list \([l_1; \dots; l_k]\), przy czym:
    • \(l = l_1 @ \dots @ l_k\),
    • dla każdej listy \(l_i\) wszystkie elementy na takiej liście są tego samego znaku,
    • \(k\) jest najmniejsze możliwe.

    Przykład:

     
          podzial [1;3;0;-2;-2;-4;9] = [[1; 3]; [0]; [-2;-2;-4]; [9]]
     

    Rozwiązania

33. Lista jest monotoniczna jeśli jest niemalejąca lub nierosnąca.
    Napisz procedurę \(\mathtt{monotons}: \mathtt{int~list} \to \mathtt{int}\), która dla danej listy wyznaczy minimalną liczbę spójnych fragmentów, na które trzeba ją podzielić, tak żeby każdy fragment był monotoniczny. (Dla pustej listy poprawnym wynikiem jest zero.)
    Na przykład, monotons [2; 3; 3; 5; 0; -1; -7; 1; 3; 5; 5; 2; 4; 6] = 4.
    Daną listę można podzielić tak: [2; 3; 3], [5; 0; -1; -7], [1; 3; 5; 5], [2; 4; 6].
34. Napisz procedurę \(\mathtt{prefiksy}: \mathtt{int~list} \to \mathtt{int~list~list}\), która dla danej listy liczb całkowitych
    zwróci listę wszystkich jej prefiksów zakończonych zerem, w kolejności rosnącej ich długości.
    Na przykład:

     
          prefiksy [0;1;2;3;0;5;6;0;1] = [[0]; [0;1;2;3;0]; [0;1;2;3;0;5;6;0]]
     

    Rozwiązania

35. Prostokątną macierz reprezentujemy jako listę wierszy, a każdy wiersz jest listą elementów. Należy zaimplementować operację transpozycji macierzy:
    \[
    \mathtt{transpose}: \alpha\ \mathtt{list~list} \to \alpha\ \mathtt{list~list}
    \]
    Dla przypomnienia, \(k\)-ty wiersz macierzy jest \(k\)-tą kolumną macierzy transponowanej i odwrotnie.
    Możesz założyć, że:
    • dana lista jest niepusta,
    • listy składowe są niepuste i są wszystkie tej samej długości.

    Na przykład: transpose [[1; 2]; [5; 3]; [0; 1]] = [[1; 5; 0]; [2; 3; 1]]
    
    Rozwiązania

36. Dany jest typ reprezentujący symbole tworzące wyrażenia arytmetyczne:

            type symbol = 
              | Liczba of int
              | Plus | Minus | Razy | Podziel
              | Nawias_Otw | Nawias_Zam
     

    Masz daną listę symboli tworzących poprawne wyrażenie arytmetyczne. Napisz procedurę \(\mathtt{kalkulator}: \mathtt{symbol~list} \to \mathtt{int}\), która obliczy wartość wyrażenia.
    Przyjmij, że, o ile nawiasy nie wymuszają innej kolejności, operacje arytmetyczne wykonujemy od lewej do prawej.
    Przykład:

            kalkulator [Nawias_Otw; Liczba 5; Plus; Liczba 4; Razy; 
                        Liczba 2; Plus; Liczba 3; Nawias_Zam; Razy; Liczba 2] = 42
     

Ćwiczenia 11: Procedury wyższych rzędów i drzewa

Ćwiczenia na drzewa z elementami procedur wyższych rzędów:

1. Dane są: definicja typu tree i procedura fold_tree:

    
         type 'a tree =  Node of 'a * 'a tree list;;
    
         let rec fold_tree f (Node (x, l)) = 
           f x (map (fold_tree f) l);;
    

   Użyj procedury fold_tree do zaimplementowania:

   1. policzenia liczby węzłów w drzewie,
   2. sprawdzić czy drzewo jest zrównoważone, tzn. wszystkie jego liście są na tej samej głębokości,
   3. sprawdzić czy drzewo regularne, tzn. wszystkie jego wierzchołki, z wyjątkiem liści, są tego samego stopnia,
   4. procedury preorder/postorder : 'a tree -> 'a list, która przekształca dane drzewo w listę jego elementów w porządku pre-order/post-order (zwróć uwagę na efektywność).
2. Dane są: definicja typu bin_tree i procedura fold_bin_tree:

    
           type 'a bin_tree = Node of 'a bin_tree * 'a * 'a bin_tree | Null;;
           let rec fold_bin_tree f a t = 
             match t with
               Null -> a |
               Node (l, x, r) -> f x (fold_bin_tree f a l) (fold_bin_tree f a r);;
    

   Użyj procedury fold_bin_tree do zaimplementowania:

   1. policzenia liczby węzłów w drzewie,
   2. policzenia wysokości drzewa,
   3. policzenia średnicy drzewa,
   4. sprawdzenia czy drzewo jest drzewem BST (dla drzewa liczb zmiennopozycyjnych, tzn. typu float tree),
   5. sprawdzenia, czy drzewo ma kształ drzewa AVL (tzn., czy dla każdego węzła drzewa wysokości jego obu poddrzew różnią się o co najwyżej 1),
   6. zaimplementowania procedury map_bin_tree -- odpowiednika procedury map_tree dla drzew binarnych,
   7. skonstruowania listy elementów znajdujących się w wierzchołkach drzewa, w kolejności infiksowej,
   8. procedury \(\mathtt{path}: \alpha\ \mathtt{tree} \to \alpha\ \mathtt{list}\), która znajduje najdłuższą ścieżkę (jedną z) od korzenia do liścia i zwraca listę wartości znajdujących się w węzłach tworzących tę ścieżkę, w kolejności od korzenia do liścia.
   9. zaimplementowania procedury \(\mathtt{levels} : \alpha\ \mathtt{tree} \to \alpha\ \mathtt{list~list}\),
      która dla danego drzewa zwraca listę list węzłów drzewa znajdujących się na kolejnych poziomach głębokości.
      Listy składowe powinny być podane w kolejności od korzenia w głąb drzewa.
      Wartości z węzłów znajdujących się na tej samej głębokości powinny być uporządkowane od lewej do prawej.
3. Zadeklaruj typ danych reprezentujący abstrakcyjną składnię wyrażeń arytmetycznych.
   Napisz procedurę obliczającą wartość wyrażenia.
   
   Rozszerz składnię wyrażeń o zmienne.
   Procedura obliczająca wartość wyrażenia będzie wymagać dodatkowego parametru --- wartościowania
   zmiennych, czyli funkcji, która nazwie zmiennej przyporządkowuje jej wartość.

Ćwiczenia 12: Złożoność czasowa i pamięciowa

1. Piramida to ostrosłup, którego podstawa jest kwadratem, a boczne ściany to tójkąty równoboczne.
   Zlecono Ci pomalowanie bocznych ścian piramidy.
   Malując piramidę, możesz wziąć ze sobą wiaderko farby, które starcza na pomalowanie 1m² powierzchni, co trwa 1 minutę.
   Zarówno wejście na wysokość \(h\) metrów, jak i zejście na dół, trwają po \(\frac{h}{2}\) minut.
   Podstawa piramidy ma długość \(n\) metrów.
   Podaj, jakiego rzędu jest czas potrzebny do pomalowania całej piramidy.
2. Jaka jest asymptotycznie energia potencjalna (wypełnionej) piramidy?
3. Jedziesz w ciemności samochodem. W odległości \(n\) metrów przed samochodem idzie pieszy.
   Jak ilość światła, która dociera do oczu kierowcy zależy od \(n\)?
   • Jeżeli pieszy nie ma odblasków, nie jest ciałem doskonale czarnym i równomiernie rozprasza padające na niego światło.
   • Jeżeli pieszy ma (idealny) odblask, który padające na niego światło odbija dokładnie tam skąd ono pada
     (a kierowca ma reflektory w oczach).
4. Zastanówmy się, jaka energia jest potrzebna do napompowania koła rowerowego.
   Dla ustalonej objętości dętki, jakiego rzędu jest ta energia w zależności od ciśnienia?
5. Ciśnienie powietrza jest takie, jak ciężar słupa powietrza naciskającego z góry.
   Chcemy się wznieść na taką wysokość, na której ciśnienie powietrza nie przekracza p.
   Jakiego rzędu jest to wysokość?
6. Sformułuj warunek określający, czy element wstawiany do drzewa ma być wstawiony do lewego, czy prawego
   poddrzewa, tak aby kolejne elementy były wstawiane na kolejnych poziomach od lewej do prawej.
7. Dana jest implementacja funkcji sprawdz o treści:

    
         let sprawdz (a:int) =
           let n = ???
           in if a < n then -1 else if a = n then 0 else 1;;
    

   W tej implementacji pod ??? została ukryta pewna liczba całkowita.
   Napisz funkcje znajdz, która odwołując się do funkcji sprawdz, znajdzie tę liczbę całkowitą.
   Podaj złożoność czasową i pamięciową rozwiązania.

   Uwaga: Zakładamy, że typ int reprezentuje dowolne liczby całkowite.
   W szczególności nie można zakładać, że typ int jest skończony i tym samym używać stałych takich jak max_int.

8. [CEOI 2003, uproszczone zadanie Hanoi]
   Wiadomo (z EMD), że żeby przełożyć \(n\) krążków w łamigłówce ,,wieże Hanoi'' trzeba wykonać \(2^n-1\) ruchów.
   Napisz procedurę hanoi: int list → int → int, która dla zadanej konfiguracji krążków oraz słupka, na
   którym początkowo znajdują się wszystkie krążki wyznaczy minimalną liczbę ruchów potrzebnych do uzyskania danej konfiguracji.

   Słupki są reprezentowane jako liczby całkowite od 1 do 3.
   Konfiguracja to lista numerów słupków, na których mają się znaleźć krążki, w kolejności od największych krążków do najmniejszych.

9. [VIII OI, zadanie Łańcuch]
   (Przynieść i pokazać chiński łańcuch.)
   W jednym ruchu można zawsze zdjąć lub założyć pierwsze ogniwo łańcucha.
   Ponadto, jeżeli zdjęte są ogniwa o numerach \(1, 2, \dots, k-2\), a ogniwo nr \(k-1\)
   jest założone, to w jednym ruchu można zdjąć lub założyć ogniwo nr \(k\).
   Początkowo wszystkie ogniwa łańcucha są założone.
   Napisz procedurę, której wynikiem jest lista ruchów prowadzących do zdjęcia \(n\) ogniw łańcucha.
   Oblicz złożoność czasową i pamięciową rozwiązania.

Ćwiczenia 13: Zastosowanie sortowania

W poniższych zadaniach istotne jest posortowanie odpowiednich list:

1. Tomek ma zabawkę, z której wystają drewniane słupki różnej wysokości.
   Jednym uderzeniem młotka może wbić lub wysunąć wybrany słupek o 1.

   Napisz procedurę słupki : int list → int, która dla danej listy początkowych wysokości słupków
   obliczy minimalną liczbę uderzeń młotka potrzebnych do wyrównania wysokości słupków.

2. Napisz funkcję elementy : α list → int list → α list, która dla list \([x_1; x_2; \ldots, x_n]\) i
   \([y_1; y_2; \ldots; y_m]\) zwraca listę \([x_{y_1}; x_{y_2}; \ldots; x_{y_m}]\).
   Możesz założyć, że liczby całkowite \(y_i\) w drugiej liście są z przedziału \([1, n]\), gdzie \(n\) oznacza długość pierwszej listy.
3. [II OI]
   Napisz procedurę trójkąt : int list → bool, która dla danej listy \([x_1; x_2; \dots; x_n]\) dodatnich liczb
   całkowitych sprawdzi, czy taka lista zawiera trójkę elementów \(x_i, x_j, x_k\) (dla \(i \neq j\), \(j \neq k\), \(i \neq k\))
   spełniających nierówność trójkąta, tzn.:
   \[2 \cdot \max(x_i, x_j, x_k) \le x_i + x_j + x_k\]

   Podaj złożoność czasową i pamięciową swojego rozwiązania.
   (Uwaga: Jeżeli liczby całkowite mają ograniczony zakres, to można to zadanie rozwiązać w stałym czasie.)

4. Napisz procedurę przedział : int list → int → int, która dla danej listy \([x_1;\dots; x_n]\), oraz dla liczby całkowitej
   \(r \ge 0\) obliczy taką liczbę całkowitą \(c\), że \(\left| \left\{i : |x_i - c| \le r \right\}\right|\) jest maksymalne.

   Przykład: przedział [2; -2; 5; -1; 11; 8; 4; 5; 8; 7] 2 = 6.
   
   Rozwiązania

5. Dana jest lista liczb rzeczywistych \([x_1; x_2; \dots; x_n]\).
   Napisz procedurę przekładaniec, której wynikiem jest taka permutacja \([x_{p_1}; x_{p_2}; \dots; x_{p_n}]\) danej listy,
   dla której suma
   \[\sum_{i=1}^{n-1} |x_{p_{i+1}} - x_{p_i}|\]
   jest największa.
   
   Rozwiązania
6. [*]
   Dana jest lista liczb całkowitych \([x_1; \dots; x_n]\).
   Napisz procedurę pierwsze : int list → int list, która zwróci taką jej spójną podlistę, że:
   • każde dwa elementy podlisty są względnie pierwsze,
   • zawiera ona maksymalną możliwą liczbę elementów.

Ćwiczenia 14: Koszt zamortyzowany

Rozwiązując poniższe zadania zwróć uwagę na efektywność algorytmów.
W większości zadań należy użyć techniki kosztu zamortyzowanego.

1. Napisz funkcję, która przekształci zadane drzewo w stóg, zachowując jego kształt (w rozwiązaniu można wykorzystać
   zmodyfikowaną procedurę rotate z wykładu).
   Jaka jest złożoność tej procedury? W jaki sposób zależy ona od kształtu drzewa?
2. Rozszerzyć implementację kolejek FIFO o wkładanie i wyjmowanie elementów z obydwu stron (w koszcie zamortyzowanym stałym).
3. Mamy \(n\) kubeczków z wodą, ponumerowanych od 1 do \(n\) (\(n > 0\)).
   W kubeczku nr \(i\) znajduje się \(x_i\) wody, przy czym \(0 < x_1 \le x_2 \le \dots \le x_n\).
   Powtarzamy \(k\) razy (dla \(k < n\)) nastepującą czynność:
   wybieramy dwa (niepuste) kubeczki zawierające jak najmniej wody i wodę z jednego kubeczka dolewamy do drugiego.

   Napisz procedurę \(\mathtt{zlewki}:\mathtt{float~list} \to \mathtt{int} \to \mathtt{float}\),
   która dla danej listy zawierającej liczby \([|x_1; \dots; x_n|]\) oraz liczby \(k\) określa
   określa ile jest wody w najmniej wypełnionym niepustym kubeczku po wykonaniu \(k\) operacji przelewania.

4. Dana jest definicja typu reprezentującego pory roku: type pora = Wiosna | Lato | Jesień | Zima.
   Napisz procedurę \(\mathtt{pory} : \mathtt{pora~array} \to \mathtt{int}\), która dla danego ciągu pór roku wyznaczy długość najkrótszego jej spójnego fragmentu, który zawiera podciąg złożony ze wszystkich czterech pór roku i to we właściwej kolejności.
   Jeżeli taki fragment nie istnieje, poprawnym wynikiem jest -1.
   Na przykład: pory [|Lato; Wiosna; Zima; Jesień; Lato; Zima; Wiosna; Jesień; Lato|] = 6.
   Fragment złożony z 6 ostatnich elementów danej tablicy zawiera podciąg: Jesień, Zima, Wiosna, Lato.
5. Zosia codziennie idąc do szkoły mija sadzawkę w parku i lubi ją obserwować. Zbliża się zima. W tej chwili na sadzawce nie ma lodu, ale wkrótce może się to zmienić. Jeżeli danego dnia temperatura jest ujemna i wynosi \(-X^\circ\)C, to górne \(X\) mm wody na sadzawce zamarza. Jeżeli danego dnia temperatura jest dodatnia i wynosi \(+X^\circ\)C, to górne \(X\) mm lodu topi się, o ile na sadzawce jest tyle lodu. Jeśli temperatura wynosi \(0^\circ\)C, to sadzawka się nie zmienia. Możesz założyć, że sadzawka nigdy nie zamarza do dna.

   Przykład: Poniżej podane są temperatury i czym będzie pokryta sadzawka (od góry) w kolejne dni:

   • \(+2^\circ\)C: nic,
   • \(-12^\circ\)C: 12 mm lodu,
   • \(+8^\circ\)C: 8 mm wody, 4 mm lodu,
   • \(-4^\circ\)C: 4 mm lodu, 4 mm wody, 4 mm lodu,
   • \(+2^\circ\)C: 2 mm wody, 2 mm lodu, 4 mm wody, 4 mm lodu,
   • \(+4^\circ\)C: 10 mm wody, 2 mm lodu – roztopiła się górna warstwa lodu i 2 mm dolnej warstwy,
   • \(-4^\circ\)C: 4 mm lodu, 6 mm wody, 2 mm lodu,
   • \(+1^\circ\)C: 1 mm wody, 3 mm lodu, 6 mm wody, 2 mm lodu,
   • \(-3^\circ\)C: 6 mm lodu, 4 mm wody, 2 mm lodu – zamarza górna warstwa lodu i 2 mm kolejnej warstwy wody.

   Napisz procedurę \(\mathtt{sadzawka}: \mathtt{int~list} \to \mathtt{int~list}\), która dla danej listy temperatur zwróci listę reprezentującą kolejne warstwy pokrywające sadzawkę po tym okresie – liczby ujemne reprezentują lód, dodatnie wodę, a ich wartość bezwzględna grubość warstwy.
   Dla powyższego przykładu, poprawnym wynikiem jest \([-6, 4, -2]\).

6. Zadanie o katastrofach lotniczych:
   Dana jest lista liczb całkowitych\([x_1; \dots; x_n]\).
   Dla każdego \(i\) trzeba policzyć największe takie \(k_i\), że \(x_i = \max (x_{i-k_i+1}, \dots x_i)\).
   Przyjmujemy, że \(x_0 = \infty\).
7. Zaimplementuj \(k\)-max-kolejkę, czyli kolejkę, do której można wkładać elementy i dowiadywać się jakie jest maksimum
   z \(k\) ostatnio włożonych elementów.
   Dokładniej, powinny być dostępne następujące operacje na \(k\)-max-kolejkach:
   • init : int → α max_queue -- tworzy nową pustą kolejkę z określonym parametrem \(k\),
   • put : α max_queue → α → α max_queue -- wkłada element do kolejki,
   • get_max : α max_queue → α -- zwraca maksimum z \(k\) ostatnich elementów włożonych do kolejki.

   Wszystkie operacje na kolejce powinny działać w stałym czasie zamortyzowanym.

8. Dana jest lista \([x_1; \dots; x_n]\) i stała \(0 \le k < n\).
   Oblicz listę \([y_1; \dots; y_n]\), gdzie \(y_i = \max(x_{\max(i-k,1)}, \dots, x_i)\).
9. Mamy daną listę liczb całkowitych \(l = [a_1, \dots, a_n]\).
   Liczbę \(a_i\) nazywamy \(k\)-maksimum, jeżeli jest ona większa od \(a_{\max(i-k,1)}, \dots, a_{i-1}, a_{i+1}, a_{\min(i+k,n)}\).
   Napisz funkcję kmax : int → int list → int list, dla której wynikiem kmax \(k\) \(l\) jest podlista
   listy \(l\) złożona z samych \(k\)-maksimów.
10. Dana jest lista \([x_1; \dots; x_n]\).
    Dla \(1 \le i < j \le n\) powiemy, że elementy \(x_i\) i \(x_j\) widzą się nawzajem, jeżeli \(\min(x_i, x_j) \ge \max(x_{i+1}, \dots, x_{j-1})\).
    Napisz procedurę widoczne, która obliczy ile elementów ciągu jest widocznych z kolejnych jego elementów.
    Np. widoczne [1; 8; 5; 6; 4] = [1; 3; 2; 3; 1].
11. Dana jest tablica \(n\) dodatnich liczb całkowitych.
    Tablica ta opisuje figurę złożoną z \(n\) stykających się bokami prostokątów-słupków, których dolne boki leżą na jednej prostej (tzw.~Manhattan skyline).
    Kolejne liczby w tej tablicy reprezentują wysokości kolejnych słupków jednostkowej szerokości(od lewej do prawej).

    Napisz procedurę \texttt{prostokat: int list → int}, która dla danej tablicy wyznaczy maksymalną powierzchnię prostokąta (o bokach równoległych do boków figury), który można wpisać w figurę opisaną przez tablicę.

12. [PCh]
    Dana jest lista liczb całkowitych \([x_1;\dots;x_n]\).
    Napisz procedurę różnica : int list → (int * int), która dla danej listy wyznaczy taką parę liczb \((i,j)\), że:
    • \(0 < i < j \le n\),
    • \(x_i \le x_j\), oraz
    • \(j-i\) jest jak największe.

    Jeżeli takie \(i\) i \(j\) nie istnieją, to poprawnym wynikiem jest (0,0).

13. [SICP, Ćw 2.29]
    Mobil, to ruchoma konstrukcja o budowie rekurencyjnej.
    Mobil ma ruchome ramiona, jak w wadze szalkowej, określonej długości.
    Na końcu każdego z ramion zawieszony jest ciężarek o określonej masie, lub mniejszy mobil.
    • Zaimplementuj strukturę danych reprezentującą mobile.
    • Napisz procedurę obliczającą wagę mobila.
    • Napisz procedurę sprawdzającą, czy mobil jest wyważony.
    • [*] [BOI 1999 --- uproszczone]
      Napisz procedurę, która zrównoważy dany mobil tak, aby jego odważniki miały dodatnie wagi całkowite, a jego całkowita masa była minimalna.
14. [*][XII OI, zadanie Sumy Fibonacciego]
    System Zeckendorfa, to taki system, w którym liczba jest reprezentowana jako ciąg zer i jedynek, a kolejne cyfry mają
    takie znaczenie, jak kolejne liczby Fibonacciego (\(1, 2, 3, 5, \dots\)).
    Ponadto, w reprezentacji liczby nie mogą pojawiać się dwie jedynki obok siebie.

    Liczby reprezentujemy jako listy zer i jedynek.
    Zaimplementuj dodawanie w systemie Zeckendorfa.

Ćwiczenia 15: Funktory

Zaprojektuj i zaimplementuj podane funktory:

1. Monoid składania funkcji -- funktor, który dla określonego typu t konstruuje
   monoid z funkcją identycznościową i operacją składania funkcji (na t).
2. Zdefiniuj funktor, który dla danego monoidu definiuje operację potęgowania.
3. Zdefiniuj funktor, który na podstawie dwóch porządków liniowych tworzy porządek leksykograficzny na parach odpowiedniego typu.
4. Zdefiniuj funktor, który dla danego pierścienia elementów tworzy pierścień macierzy 2x2.
5. [SICP]
   Przypomnijmy sobie pakiet liczb wymiernych z poprzedniego wykładu.
   Można go zapisać w postaci funktora, sparametryzowanego (wybranym typem) liczb całkowitych.
   Podaj sygnaturę liczb całkowitych zawierającą wszystkie operacje potrzebne do zaimplementowania
   pakietu liczb wymiernych ze skracaniem ułamków.
   Naszkicuj konstrukcję funktora implementującego taki pakiet liczb wymiernych.
6. [SICP]
   Wyobraźmy sobie pakiet implementujący wielomiany, wraz z rozmaitymi operacjami na wielomianach:
   suma, różnica, iloczyn, iloraz, reszta z dzielenia, porównanie, pochodna, itp.
   Pakiet taki może być sparametryzowany typem liczb (ciałem), nad którym rozpatrujemy wielomiany.
   Podaj odpowiednie sygnatury i naszkicuj sposób implementacji pakietu wielomianów jako funktora.
   Czy implementacja jest na tyle ogólna, aby pakiet działał nie tylko dla liczb zmiennopozycyjnych,
   ale również dla zespolonych i wymiernych?
7. [SICP]
   Korzystając z wyników poprzednich ćwiczeń podaj, jak można skonstruować pakiet funkcji wymiernych?
8. [SICP]
   Korzystając z wyników poprzednich ćwiczeń podaj, jak można skonstruować pakiet wielomianów dwóch zmiennych?
9. [SICP]
   Porównaj funktory z mechanizmem dziedziczenia w programowaniu obiektowym.
   W jaki sposób można zasymulować hierarchię klas za pomocą funktorów?
   Co z rzutowaniem typów?
   Co z metodami wirtualnymi?

Uwaga: Zadania oznaczone [SICP] są mocno inspirowane zadaniami i materiałem z tejże książki, choć nie ma w niej mowy o funktorach.

Ćwiczenia 16: Programowanie imperatywne

Ćwiczenia na konstrukcje imperatywne:

1. Napisz moduł Counter o następującej sygnaturze:

    
         module type COUNTER = sig
           type counter
           val make : unit -> counter
           val inc : counter -> int
           val reset : unit -> unit
         end;;
    

   Procedura make tworzy nowy licznik o początkowej wartości 0.
   Procedura inc zwiększa licznik o 1 i zwraca jego nową wartość.
   Procedura reset ustawia wartość wszystkich liczników na 0.

   Podaj złożoność czasową i pamięciową ciągu \(m\) operacji, spośród których \(n\) to operacje make.

2. Dana jest tablica liczb całkowitych zawierająca permutację liczb całkowitych od 0 do \(n\) (dla \(n \ge 0\)).
   Napisz procedurę \(\mathtt{cykl} :\mathtt{int~array} \to \mathtt{int}\), która wyznacza długość najdłuższego cyklu danej permutacji.
   Twoja procedura nie może zmieniać danej tablicy.
   Na przykład:

    
         cykl [|2; 1; 0; 5; 6; 4; 3; 8; 7|] = 4
    

   Rozwiązania

3. Dana jest tablica rozmiaru \(n+1\) zawierająca liczby od 1 do \(n\).
   Napisz procedurę, która zwraca (dowolną) wartość powtarzającą się w tablicy.

   Twoja procedura powinna działać w stałej pamięci dodatkowej.
   Natomiast może modyfikować daną tablicę.

4. Dana jest tablica znaków, która wypełniona jest nawiasami.
   Napisz procedurę \(\mathtt{nawiasy}: \mathtt{char~array} \to \mathtt{int}\), która zwróci maksymalną długość spójnego fragmentu tablicy, który jest poprawnym wyrażeniem nawiasowym.
   
   Rozwiązania
5. Dana jest deklaracja drzew binarnych, w których węzłach znajdują się dodatkowo referencje do węzłów drzewa:

    
         type α tree =
           Node of α * α tree * α tree * α tree ref |
           Null;;
    

   1. Drzewo binarne z fastrygą, to drzewo, w którym każdy węzeł posiada dodatkową referencję na następny węzeł w porządku infiksowym. (Ostatni węzeł powinien zawierać referencję na Null.)
      Napisz procedurę fastryguj : α tree → unit, która sfastryguje dane drzewo.
   2. Napisz procedurę w_lewo : α tree → unit, która w każdym węźle drzewa ustawia referencję tak, aby wskazywały na węzeł (Node) znajdujący się na tej samej głębokości w drzewie i najbliżej w lewo od danego węzła. W przypadku skrajnie lewych węzłów, referencja powinna wskazywać na Null.
   3. Napisz procedurę potomek : α tree → unit, która w każdym węźle ustawi referencję na najgłębiej położony węzeł (Node) będący jego potomkiem.
   4. Powiemy, że drzewo jest porządkowe (BST), jeśli w każdym jego wierzchołku postaci Node(x, left, right, _) wartości w poddrzewie left są mniejsze lub równe x, a wartości w poddrzewie right są większe równe x.
      Napisz procedurę fastryga: α tree → unit, która mając dane drzewo porządkowe tak ustawi w nim referencje, że węzły zawierające takie same wartości będą połączone w listy cykliczne.
      W szczególności, jeśli jakaś wartość występuje tylko raz, to referencja w jej węźle powinna być pętelką.
6. Dana jest tablica par dodatnich liczb rzeczywistych.
   Liczby te, to długości boków pewnych prostokątów o takich samych polach.
   Tablica ta jest posortowana rosnąco po pierwszych elementach par, oraz malejąco po drugich elementach par.
   Napisz procedurę diagonal: (float * float) array → float, która wyznaczy najkrótszą z przekątnych prostokątów.
7. Rozważmy zrównoważone drzewo BST, np. drzewo AVL, złożone z \(n\) węzłów. (Zrównoważone, czyli o wysokości rzędu \(O(\log n)\).) W węzłach drzewa znajdują się różne liczby całkowite.
   Samo drzewo nie jest dane, natomiast mamy daną tablicę z liczbami znajdującymi się w węzłach, w kolejności zgodnej z obejściem prefiksowym drzewa. (Obejście prefiksowe, to obejście zgodnie z rekurencyjną zasadą: najpierw korzeń, potem lewe poddrzewo a potem prawe poddrzewo.) Szukamy pewnej wartości w obejściu drzewa.
   Napisz procedurę \(\mathtt{mediana}: \mathtt{int~array} \to \mathtt{int}\), która mając daną tablicę z obejściem drzewa zwróci medianę z wartości znajdujących się w drzewie. (Jeśli w drzewie jest parzysta liczba wartości, to obie ,,środkowe'' są poprawną medianą.)
8. [M. Startek]
   Rozważmy zrównoważone drzewo BST, np. drzewo AVL, złożone z \(n\) węzłów. W węzłach drzewa znajdują się różne liczby całkowite.
   Samo drzewo nie jest dane, natomiast mamy daną tablicę z liczbami znajdującymi się w węzłach, w kolejności zgodnej z obejściem prefiksowym drzewa. Szukamy pewnej wartości w obejściu drzewa.
   Napisz procedurę \(\mathtt{znajdz}: \mathtt{int~array} \to \mathtt{int} \to \mathtt{int}\), która mając daną tablicę z obejściem drzewa i szukaną wartość, zwróci jej pozycję w danej tablicy. Jeśli szukana wartość nie występuje w obejściu drzewa, wynikiem powinno być \(-1\).
9. Rozważmy stóg złożony z \(n\) węzłów, zawierających różne liczby całkowite. Stóg jest uporządkowany tak, że wartość w dowolnym węźle jest ostro większa od wartości w jego poddrzewach. Uwaga, stóg nie musi być drzewem pełnym, ani nawet zrównoważonym.

         type 'a heap = 
            Node of 'a heap * 'a * 'a heap | 
            Null
    

   Sam stóg nie jest dany, natomiast mamy daną tablicę z liczbami znajdującymi się w węzłach, w kolejności zgodnej z obejściem infiksowym stogu.
   (Obejście infiksowe, to obejście zgodnie z rekurencyjną zasadą: najpierw lewe poddrzewo, potem korzeń a potem prawe poddrzewo.)
   Napisz procedurę \(\mathtt{rekonstrukcja}: \mathtt{int~array} \to \mathtt{int~heap}\), która mając daną tablicę z obejściem stogu odtworzy go.

10. [Bentley]
    Dana jest \(n\)-elementowa tablica znaków. Napisz procedurę rotacja\,:\,char array -> int -> unit, która rotuje daną tablicę o zadaną liczbę miejsc cyklicznie w prawo, tzn.:
    \[
    \mathtt{rotacja} [|x_1; x_2; \dots; x_n|]\ k
    \]
    zmienia zawartość tablicy na:
    \[
    [|x_{n-k+1}; \dots; x_n; x_1; \dots ; x_{n-k}|]
    \]
    Na przykład, wywołanie:
    rotacja [|'a'; 'l'; 'a'; 'm'; 'a'; 'k'; 'o'; 't';  'a'|] 4}
    zmienia zawartość tablicy na
    [|'k'; 'o'; 't'; 'a'; 'a'; 'l'; 'a'; 'm'; 'a'|].
11. Słowa Fibonacciego to ciąg napisów zdefiniowany następująco:
    \[ F_0 = [||], ~~~~ F_1 = [|'b'|], ~~~~ F_2 = [|'a'|], ~~~~ F_{n} = F_{n-1} @ F_{n-2} \]
    Kilka kolejnych słów Fibonacciego to:
    \(F_3 = [|'a'; {}'b'|]\)
    \(F_4 = [|'a'; {}'b'; {}'a'|]\),
    \(F_5 = [|'a'; {}'b'; {}'a'; {}'a'; {}'b'|]\),
    \(F_6 = [|'a'; {}'b'; {}'a'; {}'a'; {}'b'; {}'a'; {}'b'; {}'a'|]\).
    Napisz procedurę \(\mathtt{slowa}: \mathtt{char~array} \to \mathtt{int}\), która dla danego ciągu znaków wyznaczy największy indeks słowa Fibonacciego, które jest jego podciągiem (niekoniecznie spójnym).
    Na przykład: slowa [|'a'; 'b'; 'b'; 'a' ;'b'; 'a'; 'c'; 'a'; 'b'; 'a'; 'b'; 'a'; 'b'|] = 6.
12. Dana jest tablica liczb całkowitych, której pewna rotacja jest posortowana ściśle rosnąco.
    Napisz procedurę minmax : int array -> int * int, która znajduje minimum i maksimum w takiej tablicy.
13. Dana jest niepusta tablica liczb całkowitych \(a = [|x_1; \dots; x_n|]\) zawierająca ciąg ściśle monotoniczny, to jest rosnący lub malejący.
    Napisz procedurę \(\mathtt{blisko\_zera}: \mathtt{int~array} \to \mathtt{int}\), która zwraca \(\min(|x_1|, \dots, |x_n|)\).
14. Tomek chciałby popłynąć z kolegami jachtem w rejs trwający \(k\) dni. Potrzebuje zebrać grupę kolegów, którzy chcą i mogą z nim popłynąć. Od każdego ze swoich kolegów dowiedział się od kiedy do kiedy (włącznie) dysponuje wolnym czasem. Teraz zastanawia się, kiedy wyruszyć w rejs, tak żeby mogli żeglować jak największą grupą. W trakcie rejsu koledzy Tomka mogą się zmieniać (o ile obie osoby mają tego samego dnia wolne).
    Napisz procedurę \(\mathtt{rejs}: \mathtt{int} \to (\mathtt{int} * \mathtt{int})\ \mathtt{list} \to \mathtt{int}\), która mając daną liczbę \(k\) oraz informacje o dostępności kolegów Tomka zwróci maksymalną wielkość załogi (nie licząc Tomka).
    Jeżeli rejsu nie da się zorganizować, to poprawnym wynikiem jest 0.
    Na przykład: \(\mathtt{rejs}\ 20\ [(12, 36); (48, 100); (28, 70); (55, 80); (0, 65); (25, 30)] = 3\).
15. Tomek chciałby popłynąć z kolegami jachtem w rejs. Potrzebuje zebrać grupę \(k\) kolegów, którzy chcą i mogą z nim popłynąć. Od każdego ze swoich kolegów dowiedział się od kiedy do kiedy (włącznie) dysponuje wolnym czasem. Teraz zastanawia się, kiedy wyruszyć w rejs, tak żeby mógł on trwać jak najdłużej. W trakcie rejsu załoga nie może się zmieniać.

    Napisz procedurę \(\mathtt{rejs}: \mathtt{int} \to (\mathtt{int} * \mathtt{int})\ \mathtt{list} \to \mathtt{int}\), która mając daną liczbę \(k\) oraz informacje o dostępności kolegów Tomka zwróci maksymalną długość rejsu. Jeżeli rejsu nie da się zorganizować, to poprawnym wynikiem jest 0.
    Na przykład: \(\mathtt{rejs}\ 2\ [(12, 36); (48, 100); (28, 70); (50, 80); (0, 69); (25, 30)] = 42\).

16. Dana jest tablica liczb całkowitych \(a=[|x_1; x_2; \dots; x_n|]\).
    Tablica ta ma taką własność, że jej ciąg różnicowy ( \((x_{i+1} - x_i)_{i=1, 2, \dots, n-1}\)) jest ściśle rosnący.
    • [PCh] Napisz procedurę \(\mathtt{rozne} : \mathtt{int~array} \to \mathtt{bool}\), która dla danej tablicy sprawdza, czy jej elementy są parami różne.
    • Napisz procedurę \(\mathtt{minimum} : \mathtt{int~array} \to \mathtt{int}\), która dla danej tablicy wyznacz minimum z jej elementów.

    Rozwiązując to zadanie nie wolno Ci tworzyć żadnych własnych procedur rekurencyjnych.
    Wolno natomiast korzystać z pętli i innych konstrukcji imperatywnych.

    Podaj złożoność czasową i pamięciową swojego rozwiązania.

17. Dana jest tablica liczb całkowitych \(a = [|x_1; x_2; \dots; x_n|]\).
    Napisz procedurę \(\mathtt{segment} : \mathtt{int~array} \to \mathtt{int}\),
    która wyznaczy długość (\(j-i+1\)) najdłuższego takiego spójnego fragmentu tablicy \(a\),
    \([|x_i; x_{i+1}; \dots; x_j|]\), dla którego \(\min(x_i, x_{i+1}, \dots, x_j) \ge j-i+1\).
18. Dana jest tablica liczb całkowitych \(a = [|x_1; x_2; \dots; x_n|]\).
    Napisz procedurę \(\mathtt{daleko} : \mathtt{int~array} \to (\mathtt{int} * \mathtt{int})\),
    która wyznaczy taką parę indeksów \((i, j)\), że:
    • \(i < j\),
    • \(a.(i) < a.(j)\),
    • \(j - i\) jest maksymalne.

    Rozwiązując to zadanie nie wolno Ci tworzyć żadnych własnych procedur rekurencyjnych.
    Zamiast tego powinieneś użyć konstrukcji imperatywnych.

19. [PCh]
    Dane są dwie listy (bez zapętleń), które łączą się i od pewnego miejsca są tą samą listą.
    Znajdź ten wspólny fragment.
20. Napisz procedurę sprawdzającą, czy dana lista zawiera cykl.
    Czy potrafisz wyznaczyć jego długość?

Ćwiczenia 17: Imperatywne wskaźnikowe struktury danych

1. Zaimplementuj kolejki FIFO+LIFO jako imperatywne listy dwukierunkowe.
2. Dana jest definicja typu elementów tworzących listy wskaźnikowe:

         type 'a option = None | Some of 'a
         type 'a elem = {v: 'a; mutable next: 'a lista}
         and  'a lista = 'a elem option
    

   1. Napisz procedurę \(\mathtt{petla}: \mathtt{lista} \to \mathtt{unit}\), która mając daną listę jednokierunkową, tworzy z niej listę cykliczną, ale z odwróconym kierunkiem wskaźników.
      Możesz założyć, że dana lista jest poprawną listą jednokierunkową, to znaczy ma koniec i nie zapętla się.
      
      Rozwiązania
   2. Napisz procedurę \(\mathtt{przeplot}: \mathtt{lista} \to \mathtt{lista} \to \mathtt{unit}\), która splata obie listy w jedną listę postaci: pierwszy rekord pierwszej listy, pierwszy rekord drugiej listy, drugi rekord pierwszej listy, drugi rekord drugiej listy, itd. Jeśli jedna z list jest dłuższa, to jej końcówka stanowi końcówkę listy wynikowej.
      
      Rozwiązania
3. Napisz procedurę tworzącą cykliczną listę modyfikowalną.
4. Dane są deklaracje typów:

         type elem = { x: int; mutable prev: elem list };;
         type lista = elem list;;
    

   Napisz procedurę \(\mathtt{ustaw} : \mathtt{lista} \to \mathtt{unit}\), która dla danej listy \([x_1; x_2; \dots; x_n]\) typu lista, tak ustawia pola prev, aby (dla \(i=1,2,\dots, n\)) prowadziło ono z elementu \(x_i\) do listy zaczynającej się w elemencie \(x_{n-i+1}\).

5. [XII OI, Skarbonki]
   Mamy \(n\) skarbonek otwieranych kluczykami.
   Do każdej skarbonki jest inny kluczyk.
   Kluczyki do skarbonek są powrzucane do skarbonek.
   Żeby dostać się do zawartości skarbonki, skarbonkę można otworzyć kluczykiem (jeśli się go ma) lub ją rozbić.

   Skarbonki są ponumerowane od 0 do \(n-1\).
   Na podstawie tablicy \(a\) (rozmiaru \(n\)), takiej, że \(a.(i) = \) numer skarbonki, w której znajduje się kluczyk do skarbonki
   numer \(i\), oblicz minimalną liczbę skarbonek, które należy rozbić, tak aby dostać się do zawartości wszystkich skarbonek.

6. [X OI, Małpki]
   Na drzewie wisi \(n\) małpek ponumerowanych od 1 do \(n\).
   Małpka z nr 1 trzyma się gałęzi ogonkiem.
   Pozostałe małpki albo są trzymane przez inne małpki, albo trzymają się innych małpek, albo jedno i drugie równocześnie.
   Każda małpka ma dwie przednie łapki, każdą może trzymać co najwyżej jedną inną małpkę (za ogon).
   Rozpoczynając od chwili 0, co sekundę jedna z małpek puszcza jedną łapkę.
   W ten sposób niektóre małpki spadają na ziemię, gdzie dalej mogą puszczać łapki (czas spadania małpek jest pomijalnie mały).

   Zaprojektuj algorytm, który na podstawie opisu tego która małpka trzyma którą, oraz na podstawie opisu łapek puszczanych w
   kolejnych chwilach, dla każdej małpki wyznaczy moment, kiedy spadnie ona na ziemię.

7. Na szachownicy jest ustawionych \(n\) wież, które należy pokolorować.
   Jeśli dwie wieże się atakują (są w tej samej kolumnie lub wierszu), to muszą być tego samego koloru.
   Napisz procedurę kolory: int * int list → int,
   która na podstawie listy współrzędnych wież wyznaczy maksymalną liczbę kolorów, których można użyć kolorując wieże.
   Podaj złożoność czasową i pamięciową swojego rozwiązania.
8. Dana jest prostokątna mapa złóż gazu wraz z odwiertami pobierającymi gaz. Mapa jest dana w postaci dwuwymiarowej prostokątnej tablicy liczb całkowitych. Miejsca odwiertów są zaznaczone liczbami ujemnymi. Wartość bezwzględna elementu tablicy oznacza ilość znajdującego się w danym miejscu gazu.

   Pola niezerowe stykające się bokami tworzą jedno złoże. Odwierty znajdujące się w danym złożu pozwalają pobrać tyle gazu ile pól obejmuje złoże, po czym ilość gazu we wszystkich polach złoża maleje o 1. Może to spowodować zmniejszenie lub podzielenie się złoża. Dalej odwierty pozwalają pobierać gaz z tak zmienionych złóż.

   Napisz procedurę \(\mathtt{gaz}: \mathtt{int~array~array} \to \mathtt{int}\), która obliczy łączną ilość gazu, jaką wydobędą odwierty.

9. Dana jest plansza podzielona na sześciokątne pola, o wymiarach \(n \times n\) (patrz rysunek).
   \(i\)-te pole w \(j\)-tym rzędzie sąsiaduje z polami:
   • \(i-1\) i \(i\) w rzędzie \(j-1\),
   • \(i-1\) i \(i+1\) w rzędzie \(j\),
   • \(i\) i \(i+1\) w rzędzie \(j+1\).

   Plansza do gry Hex

   Dwaj gracze, biały i czarny, grają w grę hex.
   Zajmują oni na przemian wolne pola na planszy. Zaczyna gracz biały.
   Gracz biały stara się połączyć swoimi polami lewy i prawy brzeg planszy, a gracz czarny górny i dolny brzeg planszy.
   Wygrywa gracz, który jako pierwszy połączy odpowiednie brzegi planszy, w ten sposób, że z jednego brzegu na drugi
   będzie można przejść przez sąsiadujące pola zajęte przez danego gracza.

   Napisz procedurę hex : int → (int * int) list → (bool * int), która na podstawie wielkości planszy \(n\),
   oraz listy współrzędnych (rząd, pozycja w rzędzie) kolejno zajmowanych przez graczy pól określi, czy wygrał gracz biały
   (true), czy czarny (false) i w którym ruchu.

10. [XIV OI, Biura]
    W firmie pracuje \(n\) pracowników ponumerowanych od $1$ do \(n\).
    Każdy pracownik otrzymał służbowy telefon, w którym ma zapisane numery telefonów niektórych swoich współpracowników
    (a wszyscy ci współpracownicy mają w swoich telefonach zapisany jego numer).
    W związku z dynamicznym rozwojem firmy zarząd postanowił przenieść siedzibę firmy do nowych biurowców.
    Postanowiono, że każda para pracowników, którzy będą pracować w różnych budynkach, powinna znać (nawzajem) swoje
    numery telefonów, tzn. powinni oni mieć już zapisane nawzajem swoje numery w służbowych telefonach komórkowych.
    Równocześnie, zarząd postanowił zająć jak największą liczbę biurowców.

    Napisz procedurę biura : int → int * int list → int, która na podstawie liczby pracowników \(n\) oraz listy par pracowników
    posiadających nawzajem swoje numery telefonów \(l=[(a_1,b_1);\dots; (a_m,b_m)]\), wywołana jako \(\mathtt{biura}\ n\ l\), obliczy liczbę biurowców.

    Rozwiązując to zadanie przyjmij, że \(m=O(n)\).

11. [ONTAK 2007]
    Wyobraźmy sobie ciąg zer i jedynek \((x_1, x_2, \dots, x_n)\).
    Mamy dany ciąg trójek postaci \((i, j, s)\), gdzie \(i\) i \(j\) są indeksami w ciągu \((x_i)\), \(1 \le i \le j \le n\),
    natomiast \(s = (\sum_{k=i}^j x_k) \mod 2\).
    Niestety dany ciąg trójek jest sfałszowany -- nie istnieje ciąg \((x_i)\), który by go spełniał.
    Twoim zadaniem jest znalezienie takiego \(k\), że dla pierwszych \(k\) danych trójek istniejej jeszcze spełniający je ciąg, a dla \(k+1\) już nie.
    Napisz procedurę przedzialy: int → (int * int * int) list → int, która dla danego \(n\) oraz ciągu trójek oblicza takie \(k\).

Ćwiczenia 18: Logika Hoare'a

1. Udowodnij następującą trójkę:
   \[\{ x = x_0,\ y = y_0 \} \mathtt{ y := !x - !y; x := !x - !y; y := !x + !y } \{ x = y_0,\ y = x_0 \}\]
2. Udowodnij poprawność programu iteracyjnego obliczającego silnię.
3. [PCh]
   Określ dla każdego \(n\), co jest wynikiem funkcji coto i udowodnij to.

    
         x := 0;
         y := 1;
         while !y <= n do 
           x := !x - !y;
           y := !y - !x
         done;
    

4. Dana jest n-elementowa tablica a, w której znajdują się permutacja zbioru \(\{0, 1, \dots n-1\}\).
   Na tablicy wolno wykonywać tylko następujące operacje:
   • length a -- badać wielkość tabicy n,
   • \(a.(i)\) -- odczytywać elementy tablicy, oraz
   • \(\mathtt{zamien}(i,j)\) -- zamieniać elementy wartościami.

   Napisz procedurę zamiany : int array → unit, która posortuje daną tablicę
   (tj. przekształci ją w permutację identycznościową) wykonując minimalną możliwą liczbę zamian.
   Podaj niezmienniki pętli oraz odpowiednie funkcje miary.
   Nie muszą one mieć postaci formuł, ale muszą być ściśle określone.
   Udowodnij pełną poprawność programu.

5. Podaj niezmiennik pętli i wykaż poprawność następującego programu:
   \( \{ x = x_0 \ge 0 \} \)

   i := 0;
   d := 1;
   s := 1;
   while !s <= !x do
       d := !d + 2;
       s := !s + !d;
       i := !i + 1 
   done;

   \(\{ !i = \lfloor{\sqrt{!x_0}}\rfloor \}\)

Ćwiczenia 19: Przeszukiwanie grafów

1. Dany jest graf nieskierowany, którego wierzchołki są ponumerowane od 0 do \(n-1\).
   Napisz procedurę \(\mathtt{path}: \mathtt{graph} \to \mathtt{int}\), która wyznacza długość (liczoną liczbą krawędzi) najdłuższej ścieżki w tym grafie, na której numery wierzchołków tworzą ciąg rosnący.
2. [II OI, zadanie Klub Prawoskrętnych Kierowców, PCh]
   Mamy dany układ ulic, leżących na prostokątnej siatce \(m \times n\).
   Ulice są jedno- lub dwukierunkowe.
   Przyjmujemy, że cztery strony świata są reprezentowane za pomocą liczb całkowitych od 0 do 3:

    
         let north = 0 and east = 1 and south = 2 and west = 3;;
    

   Układ ulic jest dany w formie trójwymiarowej tablicy wartości logicznych ulice: \(\mathtt{ulice}.(i).(j).(k)\)
   określa, czy z punktu o współrzednych \((i,j)\) można przejechać w kierunku k jedną jednostkę odległości.
   Można założyć, że tablica ta uniemożliwia wyjechanie poza obszar \(\{0,\dots,m-1\} \times \{0,\dots,n-1\}\).

   Członkowie Klubu Prawoskrętnych Kierowców na skrzyżowaniach jeżdżą prosto lub skręcają w prawo.
   Sprawdź, czy z punktu \((0,0)\) prawoskrętny kierowca może dojechać do punktu \((m-1, n-1)\).

3. Jaka jest minimalna liczba monet potrzebna do wydania \(n\)zł reszty, przyjmując, że monety mogą być przekazywane w obie strony.
   (Na przykład, żeby otrzymać 9 zł mogę dać 1 zł i otrzymać 10 zł, razem 2).
   W obrocie są dostępne monety o zadanych (w postaci tablicy) nominałach.
4. Dana jest prostokątna mapa wysokości górzystego terenu, w postaci prostokątnej tablicy dodatnich liczb całkowitych, o wymiarach\(N \times M\).
   Chcemy przejść z pola o współrzędnych\((0,0)\) na pole o współrzędnych\((N-1, M-1)\), ale nie chcemy wspinać się zbyt wysoko.
   (Możemy się przesuwać w kierunkach N, W, S, E.)
   Napisz procedurę\(\mathtt{wysokosc} : \mathtt{int~array~array} \to \mathtt{int}\), która dla danej mapy terenu określi
   minimalną największą wysokość, na którą musimy wejść w trakcie podróży.
5. W parku jest prostokątna sadzawka pokryta lodem. Jaś bawi się na lodzie. Niestety przyszła odwilż i lód zaczął pękać.

   Masz daną prostokątną tablicę zawierającą dodatnie liczby całkowite. Jest to mapa sadzawki, a liczby reprezentują moment, w którym lód w danym miejscu pęka.
   Napisz procedurę \(\mathtt{sadzawka}: \mathtt{int~array~array} \to (\mathtt{int} * \mathtt{int}) \to \mathtt{int}\), która mając daną taką tablicę oraz współrzędne miejsca, w którym bawi się Jaś, wyznaczy moment, w którym Jaś straci możliwość wyjścia na brzeg (bo albo zostanie odcięty od brzegu spękanym lodem, albo wpadnie do wody).

   Możesz założyć, że:

   • Jaś może poruszać się po polach sąsiadujących ze sobą bokami,
   • Jaś porusza się nieporównanie szybciej, niż postępuje pękanie lodu,
   • liczby w danej tablicy są z zakresu od 1 do liczba elementów w tablicy.
6. Dana jest prostokątna mapa \(n \times m\) przedstawiająca archipelag na oceanie, reprezentowana jako bool array array.
   Elementy tablicy równe true reprezentują ląd, a false wodę.
   Na zewnątrz mapy znajduje się ocean.

   Wyspy na oceanie są wyspami rzędu 1.
   Na wyspach rzędu 1 mogą znajdować się jeziora rzędu 1, na nich mogą znajdować się wyspy rzędu 2 itd.
   Ogólnie:

   • ocean ma rząd 0,
   • wyspa na jeziorze (lub oceanie) rzędu \(k\), ma rząd \(k+1\),
   • jezioro na wyspie rzędu \(k\) ma rząd \(k\).

   Pola wody przylegające do siebie bokami lub rogami należą do tego samego jeziora (lub oceanu).
   Pola lądu przylegające do siebie bokami należą do tej samej wyspy.
   Napisz procedurę \(\mathtt{wyspa}: \mathtt{bool\ array\ array} \to \mathtt{int}\), która dla danej mapy zwróci maksymalny rząd wyspy na mapie.
   Jeżeli na oceanie nie ma żadnej wyspy, to procedura powinna zwrócić 0.

   Przykład: 69.793N, 108.241W.

7. [J.Paw.]
   Dany jest nieskierowany graf \(g\) oraz trzy wierchołki w tym grafie: \(u\), \(v\) i \(w\).
   Napisz procedurę \(\mathtt{polaczenie}: \mathtt{graph} \to \mathtt{int} \to \mathtt{int} \to \mathtt{int} \to \mathtt{int}\), która mając dane \(g\), \(u\), \(v\) i \(w\) wyznaczy minimalną liczbę krawędzi w grafie, jakie są konieczne, żeby wierzchołki \(u\), \(v\) i \(w\) pozostały połączone.
   Jeżeli nie jest to możliwe, poprawnym wynikiem jest \(-1\).
8. [XIV OI, zadanie Biura]
   Firma ma n pracowników.
   Każdy pracownik ma telefon komórkowy, a w nim telefony pewnej grupy innych pracowników.
   Przy tym, jeżeli pracownik A ma telefon pracownika B, to pracownik B ma numer pracownika A.
   Firma chce podzielić pracowników na grupy, w taki sposób żeby:
   • każdych dwóch pracowników albo było w tej samej grupie, albo miało nawzajem swoje numery telefonów,
   • liczba grup była maksymalna.

   Wyznacz podział pracowników na grupy.

9. [II OI, zadannie Palindromy]
   Podziel dane słowo (listę znaków) na minimalną liczbę palindromów parzystej długości.
10. Dany jest acykliczny graf skierowany (DAG).
    Jego wierzchołki są ponumerowane od 0 do n, a krawędzie są dane w postaci tablicy sąsiedztwa
    (kwadratowej tablicy e wartości logicznych; w grafie mamy krawędź \(u\!\!\to\!\!v\) wtw., gdy \(\mathtt{e}.(u).(v)\)).
    Powiemy, że wierzchołek u dominuje wierzchołek v, jeżeli dla każdego wierzchołka w,
    z którego można dojść do v, z u można dojść do w.

    Napisz procedurę zdominowani : bool array array -> int, która na podstawie tablicy opisującej graf
    obliczy liczbę wierzchołków, dla których istnieją wierzchołki je dominujące.

11. [XIV OI, zadanie Powódź]
    Dana jest mapa topograficzna miasta położonego w kotlinie, w postaci prostokątnej tablicy typu (int * bool) array array.
    Liczby określają wysokość kwadratów jednostkowych, a wartości logiczne określają, czy dany kwadrat należy do terenu miasta.
    Przyjmujemy, że teren poza mapą jest położony wyżej niż jakikolwiek kwadrat na mapie.

    Miasto zostało całkowicie zalane.
    Żeby je osuszyć należy w kotlinie rozmieścić pewną liczbę pomp.
    Każda z pomp wypompowuję wodę aż do osuszenia kwadratu jednostkowego, na którym się znajduje.
    Osuszenie dowolnego kwadratu pociąga za sobą obniżenie poziomu wody lub osuszenie kwadratów jednostkowych, z
    których woda jest w stanie spłynąć do kwadratu, na którym znajduje się pompa.
    Woda może przepływać między kwadratami, które stykają się bokami.

    Wyznacz minimalną liczbę pomp koniecznych do osuszenia miasta.
    Teren nie należący do miasta nie musi być osuszony.
    Miasto nie musi tworzyć spójnego obszaru.

Ćwiczenia 20: Przeszukiwanie z nawrotami (ang. back-tracking)

1. Napisz procedurę, która dla danej liczby \(n\) znajdzie jak można obejść szachownicę \(n \times n\) skoczkiem.
   Skoczek zaczyna obejście w rogu szachownicy, ale może skończyć gdziekolwiek.
   Wynikiem powinna być lista par liczb -- kolejnych pozycji skoczka.
   Jeżeli rozwiązanie nie istnieje, procedura powinna zgłaszać wyjątek Failure.
   
   Rozwiązania
2. Napisz procedurę pierwsze, która dla danej liczby całkowitej \(n\) (\(n>1\)) wyznacza
   rozbicie \(n\) na sumę minimalnej liczby składników będących liczbami pierwszymi.
   (Możesz założyć prawdziwość hipotezy Goldbacha.)
3. Dany jest (multi-)zbiór kostek domina.
   Należy wyznaczyć maksymalny łańcuch, jaki można ułożyć z danych kostek, oczywiście zgodnie z zasadami domina.
   Rozwiązanie powinno mieć postać procedury domino : (α * α) list → (α * α) list.
   Klocki można obracać.
4. [XIV OI] Atrakcje turystyczne (uproszczone).
   Mamy \(n\) miejscowości, ponumerowanych od 1 do \(n\).
   Odległości między miejscowościami są dane w postaci (symetrycznej) tablicy liczb całkowitych, o wymiarach \(n \times n\).

   Chcemy zwiedzić wszystkie te miejscowości, jednak nie w dowolnej kolejności.
   Mamy daną listę ograniczeń postaci \([(i_1, j_1); \dots; (i_k,j_k)]\).
   Ograniczenie \((i,j)\) oznacza, że miasto \(i\) musi być zwiedzone przed miastem \(j\).
   Możesz założyć, że ograniczenia da się spełnić.

   Na początku wyruszamy z miasta 1, a kończymy podróż w mieście \(n\).
   Wyznacz minimalną drogę jaką trzeba przejechać, żeby zwiedzić wszystkie miasta.

Ćwiczenia 21 i 22: Spamiętywanie i programowanie dynamiczne

1. Jaka jest minimalna liczba monet lub banknotów potrzebna do wydania \(n\)zł reszty, przyjmując, że w obrocie są dostępne monety o zadanych (w postaci tablicy) nominałach?
2. Na ile sposobów można wydać \(n\) zł reszty przyjmując, że w obrocie są dostępne monety o zadanych (w postaci listy) nominałach.
3. Dana jest kwota \(k\) oraz zestaw nominałów banknotów \(b = [b_1; b_2; \dots; b_n]\).
   Mamy dowolną liczbę banknotów każdego z nominałów.
   Napisz procedurę \(\mathtt{banknoty}: \mathtt{int} \to \mathtt{int~list} \to \mathtt{int}\), która dla danych \(k\) i \(b\) obliczy minimalną liczbę różnych nominałów banknotów jakich należy użyć do wydania kwoty \(k\).
   Jeżeli nie da się wydać kwoty \(k\) używając podanych nominałów, to procedura powinna zwrócić -1.
   Na przykład, \(\mathtt{banknoty}\ 49\ [10, 15, 11, 12, 20] = 3\).
   Liczbę 49 można uzyskać na dwa sposoby: \(49 = 12 + 12 + 10 + 15 = 11 + 11 + 15 + 12\).
4. [XII OI, zadanie Banknoty]
   W bankomacie znajdują się banknoty o nominałach \(b_1, b_2,\dots, b_n\), przy czym banknotów o nominale \(b_i\) jest w bankomacie \(c_i\).
   Jak wypłacić zadaną kwotę używając jak najmniejszej liczby banknotów?
5. Dana jest tablica zawierająca dostępne nominały monet i banknotów. Tablica ta zawiera dodatnie liczby całkowite i jest uporządkowana rosnąco.
   Napisz procedurę \(\mathtt{unikat} : \mathtt{int~array} \to \mathtt{int} \to \mathtt{int}\), która dla danej tablicy nominałów i nieujemnej kwoty \(k\) zwróci największą taką kwotę, która: nie przekracza \(k\) i może być wydana w dokładnie jeden sposób.
   Dwa sposoby wydania danej kwoty są różne, jeżeli mają różne multi-zbiory użytych nominałów.
6. Atomy bajtonium mają po \(k\) elektronów (\(k > 0\)). Elektrony w atomach bajtonium mogą znajdować się na \(n\) różnych powłokach, ponumerowanych od 0 do \(n-1\), przy czym na każdej powłoce może znajdować się co najwyżej jeden elektron. Masz daną tablicę \(t\), posortowaną niemalejąco, zawierającą liczby całkowite z zakresu od 0 do \(n^2\). Tablica ta opisuje energię elektronów znajdujących się na poszczególnych powłokach, to znaczy, elektron znajdujący się na powłoce \(i\) ma energię \(t.(i)\).

   Napisz procedurę \(\mathtt{energia}: \mathtt{int} \to \mathtt{int~array} \to \mathtt{int} \to \mathtt{int~array}\), która na podstawie liczby \(k\), tablicy \(t\) oraz energii \(e\) wyznaczy orbity, na których powinny znajdować się elektrony w atomie bajtonium tak, żeby ich łączna energia wynosiła \(e\). Wynikiem powinna być tablica \(k\) numerów powłok z elektronami, uporządkowana rosnąco. Jeżeli uzyskanie danej energii nie jest możliwe, wynikiem powinna być pusta tablica (\([||]\)).

   Przykład: wynikiem energia 4 [|2; 8; 12; 12; 20|] 42 powinno być [|0; 1; 2; 4|] lub [|0; 1; 3; 4|], natomiast energia 4 [|2; 8; 12; 12; 20|] 60 = [||].

7. Antyczny bardzo długi kijek został połamany na kawałki. Należy go skleić.
   Wszystkie kawałki zostały już ułożone w odpowiedniej kolejności, ale nie wiadomo ile potrzeba kleju.
   Długości kolejnych kawałków są dane w postaci listy \(l=[x_1;x_2;\dots;x_n]\).
   Do slejenia kawałków długości \(a\) i \(b\) potrzeba \(\max(a,b)\) ml kleju.
   Po ich sklejeniu otrzymujemy jeden kawałek długości \(a+b\).

   Napisz procedurę klej : int list → int, która na podstawie długości
   kawałków obliczy minimalną ilość kleju (w ml) potrzebną do sklejenia wszystkich kawałków.

8. Dana jest tablica dodatnich liczb całkowitych \(t = [|x_1; x_2; \dots; x_n|]\). Spójny fragment tej tablicy \([|x_i; \dots; x_j|]\) nazwiemy segmentem Fibonacciego rzędu \(k\), jeżeli:
   • \(i = j\) oraz \(x_i = x_j = k\), lub
   • istnieje takie \(l\), \(i \le l < j\), że \([|x_i; \dots; x_l|]\) oraz \([|x_{l+1}; \dots; x_j|]\) są segmentami Fibonacciego rzędu \(k-1\) i \(k-2\) (w dowolnej kolejności).

   Napisz procedurę \(\mathtt{segment}: \mathtt{int~array} \to \mathtt{int}\), która dla danej tablicy \(t\) wyznaczy największy rząd występującego w niej segmentu Fibonacciego.
   Jeżeli nie występuje w niej żaden taki segment, to poprawnym wynikiem jest zero.

   Przykład: segment [| 1; 3; 2; 3; 4; 5; 3; 6|] = 7. Segment Fibonacciego rzędu 7, to \([|3; 2; 3; 4; 5|]\) (\(Fib_7 = 13\)).

9. [XII OI, zadanie Autobus]
   Ulice miasta tworzą szachownicę -- prowadzą z północy na południe, lub ze wschodu na zachód, a każda ulica prowadzi na przestrzał przez
   całe miasto -- każda ulica biegnąca z północy na południe krzyżuje się z każdą ulicą biegnącą ze wschodu na zachód i vice versa.
   Ulice prowadzące z północy na południe są ponumerowane od 1 do \(n\), w kolejności z zachodu na wschód.
   Ulice prowadzące ze wschód na zachód są ponumerowane od 1 do \(m\), w kolejności z południa na północ.
   Każde skrzyżowanie \(i\)-tej ulicy biegnącej z północy na południe i \(j\)-tej ulicy biegnącej ze wschodu na zachód
   oznaczamy parą liczb \((i, j)\) (dla \(1 \le i \le n\), \(1 \le j \le m\)).

   Po ulicach miasta kursuje autobus. Zaczyna on trasę przy skrzyżowaniu \((1, 1)\), a kończy przy skrzyżowaniu \((n, m)\).
   Ponadto autobus może jechać ulicami tylko w kierunku wschodnim i/lub północnym.

   Przy niektórych skrzyżowaniach znajdują się pasażerowie oczekujący na autobus.
   Rozmieszczenie pasażerów jest dane w postaci prostokątnej tablicy a \(n \times m\) liczb całkowitych --
   \(a.(i-1).(j-1)\) oznacza liczbę pasażerów czekających przy skrzyżowaniu \((i,j)\).

   Napisz procedurę autobus, która na podstawie tablicy a obliczy maksymalną liczbę pasażerów, których może zabrać autobus.
   Zakładamy, że w autobusie zmieści się dowolna liczba pasażerów.

10. [VII OI, zadanie Jajka, zmodyfikowane]
    Dostaliśmy \(k\) identycznych wytrzymałych strusich jaj. Okazuje się, że są one wytrzymałe na upadki z dużych wysokości. Mieszkamy w \(n\)-piętrowym wieżowcu.
    Chcemy sprawdzić, jakie jest maksymalne piętro \(p\) (\(0\le p \le n\)), z którego jak zrzucimy strusie jajo, to się ono nie zbije.

    Napisz funkcję \(\mathtt{liczba\_prob} : \mathtt{int} \to \mathtt{int} \to \mathtt{int}\) taką, że \(\mathtt{liczba\_prob}\ n\ k\) zwróci najmniejszą (pesymistycznie) liczbę prób zrzucania jaj potrzebną do wyznaczenia \(p\) mając do dyspozycji \(k\) jaj.
    Inaczej mówiąc, szukamy takiej strategii wyznaczenia \(p\), która w najgorszym przypadku będzie wymagać jak najmniejszej liczby zrzucań jajek.

    Uwagi:

    • Jajo zbije się tylko wtedy, gdy zrzucamy je z piętra wyższego niż \(p\).
    • Jeżeli jajo się zbije, to je tracimy. Jeśli nie, to można je użyć do kolejnej próby.
    • Budynek ma \(n+1\) kondygnacji, wliczając parter.
    • Jeżeli jajo zrzucone z parteru też się zbija, to poprawnym wynikiem jest \(-1\).

    Na przykład: \(\mathtt{liczba\_prob}\ n\ 1 = n + 1\), \(~~\mathtt{liczba\_prob}\ 4\ 2 = 3\).

11. Mamy dany (w postaci listy) ciąg dodatnich liczb całkowitych \([x_1; x_2; \dots; x_n]\).
    Na ciągu tym można wykonywać operacje ,,sklejania'', tzn. dwa kolejne elementy ciągu można zastąpić jednym, równym ich sumie.
    Napisz procedurę: sklejanie : int list → int obliczającą minimalną liczbę operacji ,,sklejania'', które należy wykonać, aby ciąg był rosnący.
    Na przykład, sklejanie [3; 5; 4; 2; 7] = 1.

    Równoważne zadanie pojawiło się na konkursie USACO Open Gold w 2009\,r. i zostało opisane w
    Delcie.

12. Na rozgałęzieniach drzewa siedzą wróble.
    Każde rozgałęzienie drzewa waży 1 kilogram, a nieujemna waga siedzących na tym rozgałęzieniu wróbli podana jest w drzewie:

     
          type drzewo = Leaf | Node of int * drzewo * drzewo
     

    Waga drzewa to suma wag rozgałęzień i siedzących na nich wróbli.
    Drzewo nazwiemy zrównoważonym, jeśli w każdym rozgałęzieniu waga dwóch poddrzew będzie taka sama.
    Rzucając celnie kamieniem w rozgałęzienie drzewa możemy przegonić wszystkie wróble z poddrzewa zaczepionego w tym rozgałęzieniu.
    Napisz funkcję rownowaga : drzewo → bool, która dla danego drzewa określa, czy da się tak rzucać kamieniami w drzewo,
    aby stało się ono zrównoważone. Podaj złożoność czasową i pamięciową swojego rozwiązania.

    Dla przykładu, aby zrównoważyć następujące drzewo:

     
          Node (3, Node (5, Node (1, Leaf, Leaf), Node (7, Leaf, Leaf)), Node (2, Leaf, Leaf))
     

    wystarczy raz rzucić kamieniem (w jego lewe poddrzewo).

13. Każda latarnia jest opisana przez trójkę postaci \((x, y, p)\) oznaczającą, że latarnia może oświetlić (domknięty) odcinek alejki od \(x\) do \(y\) i pobiera wtedy \(p\)W energii elektrycznej (\(x < y, p> 0\)).
    Dana jest lista trójek opisujących latarnie, oraz para liczb \((a, b)\), \(a < b\), opisująca odcinek alejki, który chcemy oświetlić.
    Napisz procedurę \(\mathtt{moc}: (\mathtt{int} * \mathtt{int} * \mathtt{int})\ \mathtt{list} \to (\mathtt{int} * \mathtt{int}) \to \mathtt{int}\), która obliczy minimalną moc potrzebną do oświetlenia danego odcinka alejki. Jeżeli jego oświetlenie nie jest możliwe, to poprawnym wynikiem jest \(-1\).
    Przykład:

            moc [(2, 5, 10), (10, 12, 4), (-1, 2, 8), (6, 9, 10), (9, 15, 20),
                 (4, 7, 8), (0, 12, 100), (8, 10, 4), (-2, 2, 6)] (1, 11) = 42
     

14. [XVI OI, zadanie Konduktor]
    Pociąg na trasie zatrzymuje się na \(n\) stacjach, ponumerowanych od 0 do \(n-1\).
    Dana jest tablica \(a\), taka że \(a.(i).(j)\) (dla \(0 \le i < j < n\)) jest równe liczbie pasażerów, którzy
    wsiadają na stacji \(i\) i wysiadają na stacji \(j\).
    Możesz wybrać \(k\) momentów (między kolejnymi stacjami), kiedy konduktor sprawdza bilety.
    Oblicz, jaka jest maksymalna liczba pasażerów, którym zostaną sprawdzone bilety.
15. Dana jest dwuwymiarowa tablica \(a\) wypełniona nieujemnymi liczbami całkowitymi.
    Reprezentuje ona mapę prostokątnego lasu, a wartości tablicy odpowiadają liczbie drzew rosnących w różnych miejscach.
    Napisz procedurę prostokąt : int array → int → int, która dla zadanej tablicy \(a\) oraz liczby \(k\)
    znajdzie w obrębie tablicy (lasu) taki prostokąt, który:
    • zawiera przynajmniej \(k\) drzew, tzn.\ suma elementów tablicy w prostokącie jest \(\ge k\),
    • obwód prostokąta jest minimalny.

    Wynikiem procedury powinien być obwód tego prostokąta.
    Podaj złożoność czasową i pamięciową swojego rozwiązania.

    Prostokąt o dolnym lewym rogu \((x_1,y_1)\) i górnym prawym \((x_2,y_2)\) zawiera wszystkie elementy tablicy \(a.(i).(j)\) dla
    \(x_1 \le i \le x_2\), \(y_1 \le j \le y_2\), oraz ma obwód \(2 \cdot (x_2 - x_1 + 1) + 2 \cdot (y_2 - y_1 + 1)\).

16. Dana jest prostokątna mapa złóż gazu. Mapa jest dana w postaci dwuwymiarowej prostokątnej tablicy nieujemnych liczb całkowitych, oznaczających ilość znajdującego się w danym miejscu gazu.
    Chcemy zakupić prawa do wydobywania gazu z terenu, który ma kształt prostokąta i zawiera łącznie przynajmniej \(k\) jednostek gazu.
    Napisz procedurę \(\mathtt{gaz}: \mathtt{int~array~array} \to \mathtt{int} \to \mathtt{int}\), która obliczy minimalną powierzchnię takiego terenu.
17. Zosia bardzo lubi czekoladę z orzechami, a im więcej orzechów tym lepiej. Mama pozwoliła Zosi zjeść jeden prostokątny kawałek czekolady składający się z dokładnie \(k\) kosteczek. Zosia wpatruje się w tabliczkę czekolady i zastanawia się jaki kawałek wybrać, tak żeby było w nim jak najwięcej orzechów. Kawałek ten może być wybrany z dowolnego miejsca w czekoladzie, nawet ze środka tabliczki. Pomóż Zosi.
    Napisz procedurę \(\mathtt{orzechy} : \mathtt{int} \to \mathtt{int~array~array} \to \mathtt{int}\), która mając dane: liczbę \(k\) (\(k > 0\)) oraz prostokątną tablicę nieujemnych liczb całkowitych, określającą ile orzechów znajduje się w poszczególnych kosteczkach tabliczki czekolady, wyznaczy maksymalną liczbę orzechów w kawałku czekolady, który może zjeść Zosia.
    Możesz założyć, że tabliczka czekolady jest na tyle duża, że zawiera przynajmniej jeden prostokątny kawałek czekolady złożony z dokładnie \(k\) kosteczek.
    Na przykład, dla \(k = 6\) oraz tablicy:
    \[
    \begin{array}{|c|c|c|c|c|c|}
    \hline
    0 & 0 & 4 & 1 & 2 & 0 \\\hline
    3 & 3 & 8 & 11 & 3 & 2 \\\hline
    1 & 3 & 9 & 8 & 1 & 2 \\\hline
    2 & 1 & 1 & 2 & 0 & 12 \\\hline
    \end{array}
    \]
    poprawnym wynikiem jest 42.
18. Mamy most linowy długości\(N\) metrów (\(N \ge 1\)).
    Dla każdego metrowego odcinka mostu znamy jego wytrzymałość, to jest maksymalny ciężar jaki może znaleźć się łącznie na moście nie powodując rozerwania lin na tym odcinku.
    Możemy rozmieścić\(K\) podpór, dzieląc efektywnie most na\(K+1\) przylegających do siebie połączonych mostów.
    Podpory mają znikomą szerokość i rozmieszczamy je na styku metrowych odcinków mostu.

    Przed wjazdem na most zostaną ustawione dwa ograniczenia: maksymalny dopuszczalny ciężar pojazdu\(C\) jaki może wjechać na most, oraz minimalna odległość\(D\) jaką należy zachować między pojazdami.
    Jeśli dwie kolejne podpory znajdują się w odległości\(X\), to odcinki łączącego je mostu muszą mieć wytrzymałość przynajmniej \(\lceil \frac{X}{D}\rceil \cdot C\).

    Ograniczenie\(C\) będzie równe minimalnej wytrzymałości całego mostu.
    Twoim zadaniem jest wyznaczenie minimalnej możliwej wartości ograniczenia\(D\), jakie można uzyskać odpowiednio rozmieszczając podpory.
    Napisz procedurę\(\mathtt{most}: \mathtt{int~array} \to \mathtt{int} \to \mathtt{int}\), która mając dane wytrzymałości odcinków mostu oraz liczbę podpór\(K\) wyznaczy minimalną możliwą wartość ograniczenia\(D\).

19. [XV OI, zadanie Kupno gruntu]
    Dana jest kwadratowa tablica \(n \times n\) nieujemnych liczb całkowitych \(a\), oraz dodatnia liczba całkowita \(k\).
    Napisz procedurę prostokat : int array array → int → (int * int) * (int * int), która dla tablicy \(a\) i
    liczby \(k\) znajdzie taki prostokątny obszar w obrębie tej tablicy, że suma liczb z tego obszaru jest między \(k\), a \(2k\).
    Ściśle mówiąc, jeśli \(\mathtt{prostokat}\ a\ k = ((x_1,y_1), (x_2, y_2))\), to \(k \le \sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} a.(i).(j) \le 2k\).
    Możesz założyć, że taki obszar istnieje.
20. [BOI'2003, przeformułowane]
    Tomcio chce zrobić model drzewa (acyklicznego nieskierowanego grafu spójnego) z nitki i szklanych koralików i to taki,
    w którym koraliki tego samego koloru nie sąsiadują ze sobą.
    Nitkę już ma, ale koraliki musi kupić za swoje kieszonkowe.
    Ceny koralików różnych kolorów są różne, dla każdego dodatniego całkowitego \(n\) w sprzedaży są koraliki
    jednego koloru w cenie \(n\)\,gr za koralik.
    Tomcio zastanawia się z jakich koralików zrobić model drzewa, tak aby wydać jak najmniej.

    Opis drzewa ma postać struktury listowej, w której każdy węzeł to lista jego synów.
    Napisz procedurę koraliki, która na podstawie opisu drzewa obliczy minimalny koszt koralików
    potrzebnych do wykonania jego modelu.

    Uwaga: Dwa kolory wystarczą do wykonania modelu, ale nie dają minimalnego kosztu.
    Możesz założyć, że optymalna liczba kolorów nie przekracza \(\log_2 n\), gdzie \(n\) to liczba koralików.

21. [IX OI, zadanie ,,Waga'']
    Dany jest zestaw odważników.
    Czy można na szalkach wagi położyć część odważników tak, żeby waga nadal była zrównoważona?
    Jeśli tak, to jaki najcięższy odważnik można przy tym użyć?
22. [IX OI, zadanie ,,Nawiasy'']
    Dane jest wyrażenie postaci \(x_1 \pm x_2 \pm \dots \pm x_n\).
    Na ile różnych sposobów można uzyskać wyrażenie równoważne danemu wstawiając nawiasy do wyrażenia \(x_1 - x_2 - \dots - x_n\)?
    Uwaga: wstawiamy \(n-1\) par nawiasów w pełni określając kolejność wykonywania odejmowań.
23. [XI OI, zadanie ,,Sznurki'']
    Interesują nas modele drzew (spójnych grafów acyklicznych) wykonane ze sznurka.
    Każde drzewo składa się z wierzchołków i pewnej liczby krawędzi łączących różne wierzchołki.
    Ten sam wierzchołek może być połączony z wieloma innymi wierzchołkami.
    Wierzchołki grafów mają być modelowane przez węzły zawiązane na kawałkach sznurka, a krawędzie przez odcinki sznurka pomiędzy węzłami.
    Każdy węzeł może być wynikiem zasuplenia kawałka sznurka lub związania w tym samym miejscu wielu kawałków.
    Każda krawędź ma długość 1. Długość sznurka użytego do zrobienia węzłów jest pomijalna.

    Chcemy zoptymalizować liczbę i długość kawałków sznurka użytych do wykonania modelu drzewa:

    • w pierwszym rzędzie należy zminimalizować liczbę potrzebnych kawałków sznurka,
    • zakładając, że liczba kawałków sznurka jest minimalna, należy zminimalizować długość najdłuższego kawałka sznurka.

Ćwiczenia 23 i 24: Programowanie zachłanne

Poniższe zadania rozwiązuje się (mniej lub bardziej) zachłannie.
Dla każdego z nich, oprócz programu, należy uzasadnić poprawność rozwiązania zachłannego.

1. [CLR, p. 17.1]
   Problem wyboru zajęć (historyjka o kinomanie i jak największej liczbie filmów do obejrzenia).
2. Dany jest zbiór odcinków na prostej.
   Jaka jest minimalna liczba gwoździ, za pomocą których można je przybić do prostej?
   Każdy odcinek musi być przybity przynajmniej jednym gwoździem.
3. [CLR, ćw 17.2-4]
   Problem tankowania na stacjach benzynowych.
4. Napisz procedurę \(\mathtt{silnie}: \mathtt{int} \to \mathtt{int~list}\), która dla danej dodatniej liczby całkowitej \(n\)
   znajduje najkrótszy taki ciąg dodatnich liczb całkowitych \([x_1; x_2; \dots; x_k]\), że \(x_1! + x_2! + \cdots + x_k! = n\).
   Na przykład, dla \(\mathtt{silnie}\ 42\) poprawnym wynikiem jest n.p. \([3; 4; 3; 3]\).
5. [PCh]
   Dany jest ciąg nawiasów, otwierających i zamykających.
   Napisz procedurę nawiasy, która obliczy minimalną liczbę nawiasów które należy obrócić, tak aby uzyskać poprawne wyrażenie nawiasowe.
   Jeżeli nie jest to możliwe, to poprawny wynik wynosi -1.

    
         type nawias = Otwierający | Zamykający
         val nawiasy : nawias list → int
    

6. W trakcie wakacji n informatyków pojechało razem na obóz informatyczny.
   Zamieszkali oni w domkach kempingowych stojących wzdłuż prostej drogi.
   Firma telekomunikacyjna chce im zapewnić dostęp do Internetu rozstawiając wzdłuż drogi nadajniki sieci bezprzewodowej.
   Jeden nadajnik może obsługiwać co najwyżej k domków znajdujących się od niego w odległości co najwyżej r.
   Napisz procedurę wakacje : int → int → int list → int, która na podstawie liczb k i r, oraz
   listy współrzędnych domków obliczy minimalną liczbę potrzebnych nadajników.
7. Ciąg \([x_1; x_2; \dots]\) nazwiemy naprzemiennym, jeżeli:
   • \(x_1 < x_2 > x_3 < x_4 > \dots\), lub
   • \(x_1 > x_2 < x_3 > x_4 < \dots\).

   Ciąg jednoelementowy i pusty są również naprzemienne.
   Napisz procedurę $\mathtt{naprzemienny} : \mathtt{int~array} \to \mathtt{int}$, która mając dany ciąg liczb całkowitych
   w postaci tablicy obliczy długość najdłuższego jego naprzemiennego podciągu.
   Na przykład, \texttt{naprzemienny [|4;8;6;5;3;4;5;3;7;9;5;7|] = 8}.

8. Rozważamy ciągi liczb całkowitych \((x_1, x_2, \dots, x_k)\) konstruowane zgodnie z następującymi regułami:
   • \(x_1 = 1\),
   • \(x_{i+1} = x_i + f_i\) dla pewnej liczby Fibonacciego \(f_i\).

   Napisz procedurę \(\mathtt{ciag} : \mathtt{int} \to \mathtt{int~list}\),
   która dla danej dodatniej liczby całkowitej $n$ wyznaczy najkrótszy taki
   ciąg \((x_1, x_2, \dots, x_k)\), że \(x_k = n\).

9. [XII OI, zadanie Lot na marsa]
   Bajtazar postanowił polecieć na Marsa, aby zwiedzić istniejące tam stacje badawcze.
   Wszystkie stacje na Marsie leżą na okręgu.
   Bajtazar ląduje w jednej z nich, a następnie porusza się za pomocą specjalnego pojazdu, który jest napędzany odpowiednim paliwem.
   Litr paliwa starcza na metr jazdy.
   Zapasy paliwa są jednak niewielkie, różne jego ilości znajdują się w różnych stacjach.
   Bajtazar może tankować paliwo na stacji, na której w danym momencie się znajduje, nie więcej jednak, niż dostępna tam jego ilość
   (pojemność baku jest nieograniczona).
   Musi mu to wystarczyć na dojazd do następnej stacji.
   Bajtazar musi zdecydować, gdzie powinien wylądować, tak żeby mógł zwiedzić wszystkie stacje.
   Na koniec Bajtazar musi wrócić do stacji, w której wylądował.
   W czasie podróży Bajtazar musi poruszać się po okręgu, stale w wybranym jednym z dwóch kierunków.
10. Firma X podjęła się szeregu zobowiązań, z których wykonaniem zalega.
    Wykonanie każdego z nich zajmuje określoną liczbę dni.
    Za każdy dzień opóźnienia wykonania każdego z zobowiązań firma płaci określone kary.
    Napisz procedurę harmonogram która obliczy optymalną kolejność wykonywania zaległych zobowiązań.
    Procedura ta otrzymuje listę trójek postaci: (nazwa czynności, liczba dni, kara za dzień zwłoki).
    Jej wynikiem powinna być lista nazw czynności w kolejności, w jakiej należy je wykonywać.
11. [II OI, zadanie Palindromy]
    Podziel dane słowo (listę znaków) na maksymalną liczbę palindromów parzystej długości.
12. [V OI, zadanie Suma ciągu jedynkowego (uproszczone)]
    Dana jest liczba \(n \ge 0\) oraz \(0 \le s \le \frac{n(n+1)}{2}\).
    Podaj podzbiór zbioru \(\{1, \dots, n\}\), którego suma elementów jest równa s.
    Czy jest to zbiór o minimalnej liczbie elementów?
13. Napisz procedurę podzial : int → int list, która dla danej nieujemnej liczby całkowitej
    przedstawi ją jako sumę jak największej liczby (dodatnich) różnych liczb Fibonacciego.
    Na przykład, podzial 42 = [1; 2; 5; 13; 21].
14. [IV OI, zadanie Lotniska]
    W n miastach (ponumerowanych od 1 do n) znajdują się lotniska.
    Każde lotnisko ma określoną przepustowość, tj. liczbę połączeń z innymi miastami.
    Połączenia takie są zwrotne, czyli połączenie z A do B jest jednocześnie połączeniem z B do A.
    Podaj połączenia realizujące dokładnie podane przepustowości, lub stwierdź, że się nie da.
    Dane mają postać listy uporządkowanej niemalejąco wg przepustowości miast.
    • wersja łatwiejsza: między dwoma miastami może być wiele połączeń,
    • wersja trudniejsza: między dwoma miastami może być co najwyżej jedno połączenie.
15. Dana jest lista par liczb postaci \((x, y)\), \(x < y\), opisujących (domknięte) odcinki alejki jakie mogą oświetlić poszczególne latarnie, oraz para liczb \((a, b)\), \(a < b\), opisująca odcinek alejki, który chcemy oświetlić.
    Napisz procedurę \(\mathtt{ile}: (\mathtt{int} * \mathtt{int})\ \mathtt{list} \to (\mathtt{int} * \mathtt{int}) \to \mathtt{int}\), która obliczy minimalną liczbę latarni, jakie są konieczne do oświetlenia danego odcinka alejki.
    Przykład:

            ile [(1, 4); (7, 9); (-2, 3); (4, 9); (9, 12); (0, 5); (3, 7)] (-1, 11) = 4
     

16. [X OI, zadanie Czekolada]
    Dana jest tabliczka czekolady, którą należy połamać na cząstki.
    Każde przełamanie kawałka czekolady jest obarczone pewnym kosztem.
    Koszt ten nie zależy od wielkości kawałka czekolady, ale od prostej, wzdłuż której łamiemy.
    Dla wszystkich prostych, na których leżą krawędzie cząstek czekolady mamy stałe określające koszty łamania.
17. [III OI, zadanie Wieże]
    Na szachownicy \(n \times n\) należy ustawić n wież tak, żeby żadne dwie się nie szachowały, a
    ponadto każda z tych wież ma wyznaczony prostokąt, w którym ma stać.
    Znajdź takie ustawienie, lub stwierdź, że się nie da.
18. [XI OI, zadanie Most]
    Dana jest grupa osób, które chcą przejść nocą przez most.
    Mają oni jedną latarkę, która pozwala przejść jednej lub dwóm osobom.
    Każda osoba potrzebuje określonego czasu na przejście przez most.
    (Możesz założyć, że dane są posortowane.)
    Jeśli dwie osoby idą razem, to potrzebują tyle czasu, co wolniejsza z nich.
    Jaki jest minimalny czas potrzebny do przejścia wszystkich?
19. [XII OI, zadanie Samochodziki; OSC, optymalna strategia wymiany stron]
    Jasio jest trzylatkiem i bardzo lubi bawić się samochodzikami.
    Jasio ma n różnych samochodzików.
    Wszystkie samochodziki leżą na wysokiej półce, do której Jasio nie dosięga.
    W pokoju jest mało miejsca, więc na podłodze może znajdować się jednocześnie co najwyżej k samochodzików.

    Jasio bawi się jednym z samochodzików leżących na podłodze.
    Oprócz Jasia w pokoju cały czas przebywa mama.
    Gdy Jasio chce się bawić jakimś innym samochodzikiem i jeśli ten samochodzik jest na podłodze, to sięga po niego.
    Jeśli jednak samochodzik znajduje się na półce, to musi mu go podać mama.
    Mama podając Jasiowi jeden samochodzik, może przy okazji zabrać z podłogi dowolnie wybrany przez siebie
    inny samochodzik i odłożyć go na półkę (tak, aby na podłodze nie brakło miejsca).

    Mama bardzo dobrze zna swoje dziecko i wie dokładnie, którymi samochodzikami Jasio będzie chciał się bawić.
    Dysponując tą wiedzą mama chce zminimalizować liczbę przypadków, gdy musi podawać Jasiowi samochodzik z półki.
    W tym celu musi bardzo rozważnie odkładać samochodziki na półkę.

    Napisz procedurę samochodziki, która dla danej liczby k oraz listy samochodzików, którymi zechce się
    bawić Jasio, obliczy minimalną liczbę razy, kiedy mama będzie musiała Jasiowi podać samochodzik.

20. [XV OI, zadanie Plakatowanie]
    Rozważamy następującą łamigłówkę.
    Dana jest tablica nieujemnych liczb całkowitych \(a = [|a_1; \dots; a_n|]\).
    Jeśli \(a_i=a_{i+1} = \dots = a_{j-1} = a_j\) (dla \(1 \le i \le j \le n\)), to w jednym ruchu można zmniejszyć
    wszystkie liczby \(a_i, a_{i+1}, \dots, a_j\) o dowolną dodatnią liczbę, nie większą niż \(a_i\)
    (tak żeby po zmniejszeniu nadal były nieujemne).
    Napisz procedurę: ruchy : int array → (int * int * int) list, która dla danej tablicy a wyznaczy
    najkrótszą sekwencję ruchów potrzebnych do wyzerowania wszystkich liczb \(a_1,\dots,a_n\).
    Trójka liczb \((i, j, k)\) reprezentuje zmniejszenie liczb \(a_i,\dots, a_j\) o k.

Ćwiczenia 25 i 26: Programowanie dynamiczne, zachłanne i back-tracking -- powtórzenie

Rozwiązanie każdego z poniższych zadań wymaga użycia jednej z trzech technik:
back-trackingu, programowania dynamicznego lub zachłannego.
Pytanie której?

1. [PCh, Zadanie o misjonarzach i kanibalach]
   Przez rzekę chcą przeprawić się kanibale i misjonarze.
   Kanibali i misjonarzy jest po trzech.
   Mają jedną łódkę, którą może płynąć do dwóch osób.
   Łódką umieją wiosłować kanibale i tylko jeden misjonarz.
   Jeżeli w dowolnej chwili, na dowolnym brzegu rzeki będzie więcej kanibali, niż misjonarzy, to zjedzą oni misjonarzy.
   W jaki sposób wszyscy mogą bezpiecznie przeprawić się na drugi brzeg.
2. [PCh, Zadanie o trzech małżeństwach]
   Przez rzekę chcą przeprawić się trzy małżeństwa.
   Mają jedną łódkę, którą może płynąć do dwóch osób.
   Każda z kobiet może pozostać na brzegu w obecności mężczyzn tylko, jeżeli jest wśród nich jej mąż.
   W jaki sposób wszyscy mogą bezpiecznie przeprawić się na drugi brzeg?
3. [CLR]
   Minimalny koszt mnożenia n macierzy, o wymiarach \(x_1 \times x_2, x_2 \times x_3, \dots, x_n \times x_{n+1}\).
4. [CLR 17.2-5]
   Dany jest zbiór punktów na osi.
   Podaj minimalną liczbę odcinków jednostkowych, jakimi można pokryć punkty z tego zbioru.
5. Rozważmy taką oto łamigłówkę:
   Dana jest lista liczb całkowitych \(l = [x_1; x_2; \dots; x_n]\).
   W jednym ruchu możemy wybrać dowolne dwa równe elementy listy, usunąć je i wstawić na koniec listy ich sumę.
   Takie ruchy możemy powtarzać.
   Jaka jest minimalna długość listy jaką można uzyskać?

   Napisz procedurę \(\mathtt{lamiglowka} : \mathtt{int~list} \to \mathtt{int}\), która dla danej listy \(l\) wyznaczy minimalną długość listy jaką można uzyskać.

   Na przykład, \(\mathtt{lamiglowka}\ [4; 3; 4; 5; 12; 2; 3; 1; 6; 1] = 4\).

6. Rozważmy taką oto łamigłówkę:
   Dana jest lista dodatnich liczb całkowitych \(l = [x_1; x_2; \dots; x_n]\). W jednym ruchu możemy wybrać dowolne dwa różne elementy listy, usunąć je i wstawić na koniec listy wartość bezwzględną ich różnicy. Takie ruchy możemy powtarzać. Kończymy, gdy wszystkie elementy listy są sobie równe. Jaka jest minimalna wartość, jaką można na koniec uzyskać na liście?
   Napisz procedurę \(\mathtt{lamiglowka} : \mathtt{int~list} \to \mathtt{int}\), która dla danej listy \(l\) wyznaczy minimalną wartość jaką można uzyskać.
7. W korytarzu harcują myszy. Korytarz ma długość \(n\) metrów.
   Dana jest tablica \(n\) nieujemnych liczb całkowitych \(a\) opisująca gdzie jest ile myszy,
   dokładnie na odcinku od \(i\) do \(i+1\) metrów od wejścia do korytarza jest \(a.(i)\) myszy.

   Dysponujesz \(k\) kotami (\(k \le n\)).
   Twoim zadaniem jest takie rozmieszczenie kotów w korytarzu, żeby złapały jak najwięcej myszy.
   Każdy kot może pilnować ustalonego przez Ciebie spójnego fragmentu korytarza (na przykład, może mieć założoną smycz odpowiedniej długości, przymocowaną do podłogi pośrodku pilnowanego fragmentu korytarza).
   Fragmenty korytarza pilnowane przez różne koty nie mogą zachodzić na siebie (żeby koty się nie pobiły a smycze nie poplątały), choć mogą się stykać.
   Niektóre fragmenty korytarza mogą pozostać niepilnowane przez żadnego kota.

   Kot, który pilnuje fragmentu korytarza od \(i\) do \(j\) metrów od wejścia (dla \(i < j\)), na którym znajduje się \(s = a.(i) + a.(i+1) + \cdots + a.(j-1)\) myszy, złapie: \(\max(s - (j-i-1)^2, 0)\) myszy.

   Na przykład, dla \(k=2\) oraz \(a = [|1; 5; 1; 4; 3; 2; 7; 0|]\) poprawnym wynikiem jest 14, jeden kot może pilnować fragmentu korytarza od 1 do 4 metrów od wejścia (łapiąc 6 z 10 myszy), a drugi może pilnować fragmentu korytarza od 4 do 7 metrów od wejścia (łapiąc 8 z 12 myszy).

   Napisz procedurę \(\mathtt{myszy}: \mathtt{int} \to \mathtt{int~array} \to \mathtt{int}\), która dla danej liczby \(k \ge 0\) oraz tablicy \(a\), wyznaczy maksymalną liczbę myszy, jakie złapią koty.

   Rozwiązanie tego zadania zostało omówione w Delcie

8. Rozpatrujemy przedstawienia liczby naturalnej \(n\) jako sumy różnych składników nieparzystych, tzn. rozważamy takie ciągi \((x_1, \dots, x_k)\), że:
   • \(1 \le x_i\) i \(x_i\) jest nieparzyste (dla \(i=1,\dots, k\)),
   • \(x_1 > x_2 > \dots > x_k\),
   • \(x_1 + \cdots + x_k = n\).
   1. Napisz procedurę, która dla danej liczby \(n\) obliczy, na ile różnych sposobów można ją przedstawić jako sumę różnych nieparzystych składników.
      Na przykład, dla \(n=2\) poprawnym wynikiem jest 0, a dla \(n=12\) poprawnym wynikiem jest 3.
   2. Napisz procedurę, która dla danej liczby \(n\) wyznaczy (pewne) przedstawienie tej liczby jako sumy maksymalnej liczby nieparzystych składników.
      Na przykład, dla \(n=42\) poprawnym wynikiem może być [15; 11; 7; 5; 3; 1].
9. Rozważamy ciągi liczb całkowitych \((x_1, x_2, \dots, x_k)\) konstruowane zgodnie z następującymi regułami:
   • \(x_1 = 1\),
   • \(x_{i+1} = x_i + 1\), lub
   • \(x_{i+1} = x_i \cdot f_i\) dla pewnej liczby Fibonacciego \(f_i\).

   Napisz procedurę \(\mathtt{ciag} : \mathtt{int} \to \mathtt{int~list}\), która dla danej dodatniej liczby całkowitej \(n\) wyznaczy najkrótszy taki ciąg \((x_1, x_2, \dots, x_k)\), że \(x_k = n\).

   Na przykład \texttt{ciag 42} powinno zwrócić \([1; 2; 42]\) lub \([1; 21; 42]\).

10. Tworzymy ciąg liczb całkowitych \((x_k)\) w następujący sposób:
    • \(x_0 = 1\),
    • dla każdego \(k > 0\) wybieramy pewne \(0 \le i, j < k\) i przyjmujemy \(x_k = x_i + x_j\).

    Napisz procedurę ciąg : int → int list, która dla danego \(n \ge 1\) znajdzie najkrótszy taki ciąg \(x_0, x_1, ..., x_k\), który spełnia powyższe warunki, oraz \(x_k = n\).
    Wynikiem procedury powinna być lista \([x_0; ...; x_k]\).

11. Rozważamy ciągi liczb całkowitych \((x_1, x_2, \dots, x_k)\) konstruowane zgodnie z następującymi regułami:
    • \(x_1 = 1\),
    • \(x_{i+1} = x_i + 1\), lub
    • \(x_{i+1} = x_i \cdot p_i\) dla pewnej liczby pierwszej \(p_i\).

    Napisz procedurę \(\mathtt{ciag} : \mathtt{int} \to \mathtt{int~list}\), która dla danej dodatniej liczby całkowitej \(n\) wyznaczy najkrótszy taki ciąg \((x_1, x_2, \dots, x_k)\), że \(x_k = n\).

    Możesz założyć, że dane są procedury:

    • \(\mathtt{prime}:\mathtt{int}\to\mathtt{bool}\) sprawdzająca czy dana liczba jest pierwsza, oraz
    • \(\mathtt{primes}:\mathtt{int}\to \mathtt{int~list}\), która dla danej dodatniej liczby całkowitej \(n\) zwraca listę liczb pierwszych nie przekraczających \(n\) (uporządkowaną rosnąco).
12. Dla danych dodatnich liczb całkowitych \(l\) i \(m\) szukamy przedstawienia ułamka \(\frac{l}{m}\), jako możliwie najkrótszej sumy odwrotności dodatnich liczb całkowitych: \[\frac{l}{m} = \frac{1}{s_1} + \frac{1}{s_2} + \cdots + \frac{1}{s_k}\]
    Napisz procedurę rozklad : int * int → int list, która dla danych liczb \(l\) i \(m\) wyznaczy szukany ciąg mianowników \([s_1;\dots;s_k]\).
13. Dana jest dodatnia liczba całkowita \(x\).
    Interesują nas różne rozkłady \(x\) na sumę różnych (dodatnich) liczb Fibonacciego.
    Dwa rozkłady, które różnią się jedynie kolejnością składników uznajemy za takie same.
    Tylko rozkłady, które mają inne zbiory składników uznajemy za różne.

    Napisz procedurę \(\mathtt{rozklady} : \mathtt{int} \to \mathtt{int}\), która dla danej liczby \(x\)
    policzy na ile różnych sposobów można przedstawić \(x\) jako sumę różnych (dodatnich) liczb Fibonacciego.

    Na przykład \(\mathtt{rozklady}\ 42 = 6\).

14. Dana jest lista dodatnich liczb całkowitych \([x_1; x_2; \dots; x_n]\) oraz dodatnia liczba całkowita \(k\).
    Napisz procedurę podzial : int list → int → int list list, która podzieli daną listę na \(k\) spójnych fragmentów
    \([[x_1; \dots; x_{n_1}]; [x_{n_1+1}; \dots; x_{n_2}]; \dots; [x_{n_{k-1}+1}; \dots;x_n]]\) w taki sposób, że
    \(\max \{x_1+ \cdots+ x_{n_1}, x_{n_1+1}+\cdots+ x_{n_2}, \dots, x_{n_{k-1}+1}+ \cdots+ x_n\}\) jest jak najmniejsze.
    Jeżeli \(k > n\), to w liście wynikowej mogą występować puste listy.

    Na przykład podzial [1; 4; 2; 2; 4; 1; 2; 4] 3 = [[1; 4; 2]; [2; 4]; [1; 2; 4]].

15. Na przystanku autobusowym pojawiają się pasażerowie czekający na autobus. O określonych godzinach podjeżdżają puste autobusy, do których mogą wsiadać pasażerowie. Należy obliczyć minimalną wielkość autobusów, pozwalającą na przewiezienie wszystkich pasażerów (wszystkie autobusy są tej samej wielkości).
    Tablica \(p\) zawierająca \(n\) nieujemnych liczb całkowitych opisuje pojawianie się pasażerów, w chwili \(i\) na przystanek przychodzi \(p.(i)\) pasażerów.
    Tablica \(a\) opisuje momenty przyjazdu autobusów na przystanek -- jest ona uporządkowana niemalejąco i zawiera liczby całkowite z zakresu od 0 do \(n\).
    Napisz procedurę \(\mathtt{autobusy}: \mathtt{int~array} \to \mathtt{int~array} \to \mathtt{int}\), taką że \(\mathtt{autobusy}\ p\ a\) oblicza minimalną konieczną wielkość autobusów.
    Jeżeli nie da się obsłużyć wszystkich pasażerów, to poprawnym wynikiem jest -1.
    Na przykład, autobusy [|1; 0; 2; 1; 2; 0; 1; 2; 6; 0; 6; 0|] [|2; 6; 8; 11|] = 7}.
16. [XVI OI, zadanie Słonie]
    Dane jest tablica \(p\) długości \(n\) zawierająca permutację liczb ze zbioru \(\{0,\dots,n-1\}\).
    Chcemy posortować tablicę \(p\) rosnąco, ale jedyną operacją modyfikującą, którą możemy wykonywać na niej jest zamiana zawartościami dwóch komórek o podanych indeksach.
    Zamiana komórek zawierających liczby \(x\) i \(y\) kosztuje \(x+y+1\).
    Napisz procedurę koszt : int array → int, która oblicza minimalny koszt posortowania tablicy \(p\).
17. [II OI]
    Dany jest zestaw \(n\) czynności.
    Wykonanie każdej z tych czynności trwa tym dłużej, im później się ją zacznie, konkretnie jeżeli zaczniemy wykonywać czynność \(i\) w chwili \(t\), to jej wykonanie będzie trwać \(a_i t + b_i\).
    Jaki jest minimalny czas wykonania wszystkich tych czynności, jeżeli zaczynamy je wykonywać w chwili 0?
18. Rozważamy drzewa postaci:

     
          type expr = 
            NWD of expr * expr | 
            NWW of expr * expr | 
            Number of int
     

    Drzewa takie reprezentują wyrażenia.
    NWD oznacza największy wspólny dzielnik, a NWW najmniejszą wspólną wielokrotność dwóch podwyrażeń.
    Argumentami Number są liczby nieujemne.
    \(\mathtt{Number}\ x\), dla \(x>0\) oznacza liczbę \(x\).
    \(\mathtt{Number}\ 0\) oznacza miejsce, w które należy wstawić dodatnią liczbę.

    Napisz procedurę \(\mathtt{wstaw}: \mathtt{expr} * \mathtt{int} \to \mathtt{int}\), która dla danego drzewa \(t\) i dodatniej liczby całkowitej \(n\) znajdzie taką najmniejszą dodatnią liczbę całkowitą \(x\), że gdy wstawimy \(\mathtt{Number}\ x\) w miejsce wszystkich wystąpień \(\mathtt{Number}\ 0\) w \(t\), to wartością wyrażenia będzie \(n\).
    Jeżeli taka liczba \(x\) nie istnieje, to poprawnym wynikiem jest 0.

    Na przykład, dla \(t = \mathtt{NWW(NWW(Number 2, Number 0), NWD(Number 0, Number 49))}\) i \(n = 42\), \(\mathtt{wstaw}\ t\ n = 21\).
    
    Rozwiązania

19. Przez park biegnie długa prosta alejka. Przy tej alejce, w określonych miejscach, znajduje się \(n\) ławeczek. Wzdłuż alejki chcemy zamontować \(k\) latarni. Dla każdej ławeczki interesuje nas odległość do najbliżej położonej latarni. Latarnie chcemy rozmieścić tak, żeby maksymalna odległość od ławeczki do najbliżej niej położonej latarni była jak najmniejsza, przy czym latarnie mogą być umieszczone tylko w miejscach o współrzędnych całkowitych.
    Masz daną posortowaną tablicę $n$ liczb całkowitych określających położenie ławeczek oraz liczbę \(k\). Napisz procedurę \(\mathtt{latarnie}: \mathtt{int~array} \to \mathtt{int} \to \mathtt{int~array}\), która na ich podstawie wyznaczy gdzie należy postawić latarnie i zwróci posortowaną tablicę z ich pozycjami.
    Na przykład, dla tablicy \([|-4; -3; -1; 2; 2; 3; 8; 10; 11|]\) oraz \(k=3\) jednym z możliwych wyników jest \([|-2; 2; 10|]\).
20. Dane jest drzewo typu:

     
          type choinka = 
            Koniuszek | 
            Galaz of choinka | 
            Rozgalezienie of choinka * choinka;;
     

    opisujące kształt choinki.

    1. [PCh]
       W węzłach choinki (Rozgalezienie, Galaz i Koniuszek) możemy umieszczać świeczki.
       Powiemy, że choinka jest oświetlona, jeżeli dla każdej krawędzi (łączącej węzły) choinki przynajmniej w jednym jej końcu znajduje się świeczka.
       Napisz procedurę, która dla danej choinki obliczy minimalną liczbę świeczek potrzebnych do oświetlenia choinki.
    2. [PCh]
       Na każdej krawędzi (łączącej węzły) choinki wieszamy jedną bombkę.
       Mamy do dyspozycji trzy rodzaje bombek: czerwone po 2zł, niebieskie po 5zł i srebrne po 7zł.
       Choinkę należy przystroić w taki sposób, żeby na krawędziach o końcach w tym samym węźle wisiały bombki o różnych kolorach, a łączny koszt przystrojenia całej choinki był jak najmniejszy.
    3. W węzłach choinki (Rozgalezienie, Galaz i Koniuszek) wieszamy bombki.
       Dostępne są trzy rodzaje bombek:
       • czerwone, wykonane z miedzi, każda taka bombka waży 1kg,
       • srebrne, wykonane z białego złota niskiej próby, każda taka bombka waży 2kg,
       • złote, wykonane ze szczerego złota, każda taka bombka waży 3kg.

       Bombki należy zawiesić tak, aby choinka nie chwiała się, tzn. dla każdego rozgałęzienia łączny ciężar bombek
       zawieszonych po lewej i po prawej stronie musi być taki sam.
       Pytanie czy jest to możliwe, a jeżeli tak, to na ile sposobów?

       Napisz procedurę, która dla danej choinki obliczy na ile sposobów można powiesić na niej bombki.

Ćwiczenia 27: Wyszukiwanie wzorców w tekście

1. Dana jest lista elementów.
   Wyznacz wszystkie nietrywialne rotacje cykliczne danej listy, które dają w wyniku ją samą.
2. Dane są dwa napisy (w postaci tablic znaków) x i y.
   Napisz procedurę szukaj : char array → char array → int, która znajduje najdłuższy
   spójny fragment w napisie x, który jest prefiksem (fragmentem początkowym) napisu y.
   Wynikiem procedury powinna być jego długość.
3. Okresem ciągu \([x_1; x_2; \dots; x_n]\) nazwiemy najmniejszą dodatnią liczbę całkowitą k,
   taką że \(x_i = x_{i+k}\), dla \(i=1, 2, \dots, n-k\).
   Napisz procedurę okresy: int list → int list, której wynikiem dla danej listy \([x_1; x_2; \dots; x_n]\)
   jest taka lista \([y_1; y_2; \dots; y_n]\), że \(y_i\) jest okresem \([x_i; x_{i+1}; \dots; x_n]\).
4. Niech \((x_1, x_2, \dots, x_n)\) będzie danym niepustym ciągiem liczb.
   Okresem całkowitym tego ciągu nazwiemy najmniejszą taką liczbę k, że:
   • \(1 \le k \le n\),
   • k jest dzielnikiem n,
   • \(x_i = x_{i+k}\) dla wszystkich \(i = 1, \dots n-k\).

   Zauważmy, że każdy ciąg ma okres całkowity, co najwyżej jest to \(k=n\).
   Na przykład, okresem całkowitym ciągu \([1;3;2;1;1;3;2;1;1;3;2;1]\) jest 4, a okresem całkowitym ciągu \([1;3;2;1;1]\) jest 5.
   Napisz procedurę okres : int array → int, która dla danego ciągu wyznaczy jego okres całkowity.

5. Dana jest tablica \(a\) zawierająca ciąg \(n\) elementów.
   Napisz procedurę \(\mathtt{presuf}: \alpha\ \mathtt{array} \to \mathtt{int}\),
   która dla danej tablicy \(a\) znajduje długość najdłuższego jej prefikso-sufiksu,
   który ma przynajmniej trzy rozłączne wystąpienia w \(a\).
6. Dana jest tablica \(a\) zawierająca ciąg \(n\) elementów.
   Napisz procedurę \(\mathtt{double}: \alpha\ \mathtt{array} \to \mathtt{int}\),
   która dla danej tablicy \(a\) znajduje długość \(i\) najdłuższego jej prefiksu, który powtórzony dwukrotnie nadal jest jej prefiksem,
   tzn.\ \(a.(0) = a.(i)\), \(a.(1) = a.(i+1)\), ..., \(a.(i-1) = a.(2i-1)\).
7. [XII OI, zadanie Szablon]
   Chcemy wykonać długi napis.
   W tym celu najpierw przygotowujemy odpowiedni szablon z wyciętymi literkami.
   Następnie taki szablon można przyłożyć we właściwym miejscu do ściany i malujemy po nim farbą.
   Malujemy zawsze po całym szablonie, ale dopuszczamy, aby litery były malowane wielokrotnie.
   Literki na szablonie znajdują się koło siebie (nie ma tam przerw).
   Zadanie polega na wyznaczeniu minimalnej długości szablonu, za pomocą którego można wykonać cały napis.
8. [XIII OI, zadanie Okresy słów]
   Napis Q jest okresem A, jeśli Q jest prefiksem właściwym A oraz A
   jest prefiksem (niekoniecznie właściwym) napisu QQ.
   Przykładowo, napisy abab i ababab są okresami napisu abababa.
   Maksymalnym okresem napisu A nazywamy najdłuższy z jego okresów, lub napis pusty, jeśli A nie posiada okresu.
   Dla przykładu, maksymalnym okresem napisu ababab jest abab.
   Maksymalnym okresem abc jest napis pusty.

   Napisz procedurę, która dla danego (w postaci listy) napisu obliczy listę długości maksymalnych
   okresów kolejnych jego prefiksów.

9. Dana jest tablica \(a\) zawierająca \(n\) znaków.
   Rotacją cykliczną takiej tablicy o \(i\) (dla \(0 \le i < n\)) nazwiemy tablicę powstałą z przeniesienia elementów
   \(a.(0), \dots, a.(i-1)\) z początku tablicy na jej koniec, przy równoczesnym przesunięciu elementów \(a.(i),\dots, a.(n-1)\) o \(i\) pozycji w lewo.

   Napisz procedurę \(\mathtt{minrot}: \mathtt{char~array} \to \mathtt{int}\),
   która dla danej tablicy znaków \(a\) zwróci taką liczbę \(i\), że rotacja tablicy \(a\) o \(i\) pozycji jest najmniejsza w porządku leksykograficznym,
   spośród wszystkich jej rotacji cyklicznych.

10. Dane są dwa napisy (w postaci tablic znaków) \(x\) i \(y\).
    Napisz procedurę \(\mathtt{szukaj}:\mathtt{char~array}\to\mathtt{char~array}\to\mathtt{int}*\mathtt{int}\),
    która znajduje najdłuższy spójny fragment występujący w obu napisach.
    Wynikiem procedury powinna być para: pozycje jego początków w obu napisach.
11. Dany jest tekst w postaci tablicy znaków \([|c_1;\dots;c_n|]\).
    Napisz procedurę podsłowo : char array → (int * int),
    która znajduje takie pozycje w tekście \((i,j)\), że:
    • \(0 < i \le j \le n\),
    • liczba wystąpień \(k\) napisu \([|c_i;\dots;c_j|]\) w danym tekście, pomnożona przez jego długość
      (czyli \(k \cdot (j-i+1)\)) jest maksymalna.

    Dla pustej tablicy poprawnym wynikiem jest (0,0).