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: make i Makefile

Automatyzacja kompilacji: program make

Narzędzie make służy do automatycznej kompilacji projektów programistycznych.
Historycznie make został oczywiście stworzony dla programów w języku C, ale dzięki swojej elastyczności
może być z powodzeniem stosowany do kompilacji projektów w innych językach oraz w dowolnych innych sytuacjach,
gdy mamy do czynienia z wielokrotnym automatycznym przerabianiem na różne sposoby pewnej liczby różnorodnych plików.
Do sterowania działaniem programu make służy plik o nazwie Makefile.

Podstawowy Makefile

W przypadku przykładowego projektu z jednego z poprzednich laboratoriów składającego się z modułów
plik i
drugi_plik, w najbardziej
bezpośredniej i podstawowej wersji plik Makefile
mógłby wyglądać tak:

 
      test: plik.cmo drugi_plik.cmo 
          ocamlc -o test plik.cmo drugi_plik.cmo
 
      plik.cmi: plik.mli 
          ocamlc -c plik.mli
 
      plik.cmo: plik.ml 
          plik.cmi ocamlc -c plik.ml
 
      drugi_plik.cmo: drugi_plik.ml plik.cmo 
          ocamlc -c drugi_plik.ml
 
      clean: rm *.cmi *.cmo
 

Aby użyć tego przepisu, należy po prostu wydać polecenie make, oczywiście wcześniej upewniwszy się, że jesteśmy w katalogu, w
którym znajdują się pliki plik.ml,
plik.mli,
drugi_plik.ml i
Makefile
(można je pobrać w postaci pliku zip).

Program make sam zorientuje się w jakiej kolejności należy wykonywać poszczególne polecenia i w wyniku
(o ile nie będzie błędów) otrzymamy gotowy plik test.

Jak widać plik Makefile
składa się z pewnej liczby przepisów, postaci:

 
      cel: zależności
          instrukcje
 

Cel zwykle jest nazwą pliku, który tworzy się za pomocą instrukcji, zwykle wykorzystując do tego
zależności (czyli inne cele, zwykle także pliki).
Lista zależności, jak i instrukcje mogą być puste, a dla jednego celu może być tylko jeden przepis z niepustą instrukcją.

Uwaga natury składniowej: instrukcje muszą być poprzedzone prawdziwym znakiem tabulacji (a nie zwykłymi odstępami!)

Make wywołany przez make nasz_cel działa w ten sposób, że najpierw buduje sobie drzewko zależności między
celami i następnie stara się zrealizować nasz_cel jak najtańszym kosztem.
Decyduje, czy należy daną instrukcję wykonać porównując datę pliku cel, z datą plików zależności.
Oczywiście po wykonaniu jednej instrukcji może zaistnieć konieczność wykonania innych i make to właśnie zrobi we właściwej kolejności.
Wywołanie make bez parametrów spowoduje próbę wykonania celu z pierwszego przepisu.
Zazwyczaj jest to cel o nazwie all.

Jak widać na przykładzie celem nie musi być plik, ale również dowolne hasło, np. clean.
Po wydaniu polecenia make clean, ponieważ plik clean nie występuje na dysku, więc make
zorientuje się, że wykonanie instrukcji jest konieczne i zgodnie z naszymi intencjami wyczyści wszystkie pośrednie efekty kompilacji.
Plik clean oczywiście nie zostanie stworzony, więc przy następnym wywołaniu make clean, instrukcja znów się wykona.

Bardziej zaawansowany Makefile

Oczywiście pisanie takiej ilości tekstu dla tak prostego projektu byłoby bardzo niewygodne.
Na szczęście większą część pliku Makefile można napisać w taki sposób, żeby pasowała
nie tylko do naszego konkretnego projektu, ale także do wszystkich podobnych.
Oto bardziej zaawansowana i uniwersalna wersja pliku
Makefile:

 
      test: plik.cmo drugi_plik.cmo 
          ocamlc -o $@ $^
 
      %.cmo: %.ml 
          ocamlc -c $<
 
      %.cmi: %.mli 
          ocamlc -c $<
 
      clean: rm *.cmi *.cmo
 
      depend: 
          ocamldep *.ml *.mli > .depend
 
      include .depend 
 

W powyższym pliku, po pierwszym przepisie na plik test, zamiast przepisów do kompilacji poszczególnych
plików występuje po jednym przepisie na kompilacje plików jednego rodzaju.
Po przepisie na test, kolejny przepis mówi jak dostać plik o rozszerzeniu .cmo z pliku
(którego nazwa ma ten sam rdzeń) o rozszerzeniu .ml.
W instrukcjach występują tajemnicze znaczki $<, $^ i $@.
Oznaczają one odpowiednio: pierwszą z zależności ($<), wszystkie zależności ($^) i cel ($@) reguły.
Podobny przepis opisuje kompilację plików .mli do .cmi.

Zauważmy, że w tym Makefile'u nie podaliśmy zależności pomiędzy plikami.
Istotnie, zależności obliczone są automatycznie przez program ocamldep i zapisane
w pliku .depend, który jest przez make włączany do Makefile'a.
Z tego powodu przed pierwszym uruchomieniem make, gdy nie ma jeszcze pliku .depend,
należy go utworzyć z dowolną zawartością, choćby pustą, np. poleceniem touch .depend, a następnie
wykonać make depend.
Dopiero teraz jesteśmy gotowi do prawdziwej kompilacji (make test lub make).
Zauważmy, że po każdej większej zmianie projektu, tzn. takiej w której zmienia się graf zależności
między plikami należy na nowo ręcznie wykonać make depend.

Jeszcze bardziej zaawansowany Makefile

Makefile podany poniżej,
oprócz wszystkich rzeczy opisanych wcześniej, sam tworzy sobie plik .depend (o ile ten plik nie istnieje),
umożliwia dodanie flag do komendy ocamlc dla wszystkich jego wywołań, umożliwia wywołanie kompilatora do kodu
natywnego (czyli użycie komendy ocamlopt zamiast ocamlc do kompilacji) oraz automatyczne
wygenerowanie dokumentacji (aby ją obejrzeć należy zrobić make doc; firefox doc/index.html).

 
      # The base name of the executable
      PROG=test
 
      # The list of object files
      CMOS=pierwszy.cmo lewy.cmo prawy.cmo ostatni.cmo
      CMXS=$(CMOS:.cmo=.cmx)
 
      # Choose your target: bytecode or native
      $(PROG): $(PROG).byte
          cp $< $@
 
      # Special rule to create pierwszy.ml
      pierwszy.ml: pierwszy.txt
	  echo "let tekst=\"\\" > $@
	  cat $< >> $@
	  echo '"' >> $@
 
      OCAMLC=ocamlc
      OCAMLOPT=ocamlopt
      OCAMLDEP=ocamldep
      OCAMLDOC=ocamldoc
      INCLUDES=                 # all relevant -I options here
      OCAMLFLAGS=$(INCLUDES)    # add other options for ocamlc here
      OCAMLOPTFLAGS=$(INCLUDES) # add other options for ocamlopt here
 
      $(PROG).byte: $(CMOS)
          $(OCAMLC) $(OCAMLFLAGS) -o $@ $^
 
      $(PROG).native: $(CMXS)
          $(OCAMLOPT) $(OCAMLOPTFLAGS) -o $@ $^
 
      .SUFFIXES: .ml .mli .cmo .cmi .cmx
 
      %.cmo: %.ml
          $(OCAMLC) $(OCAMLFLAGS) -c $<
 
      %.cmx: %.ml
          $(OCAMLOPT) $(OCAMLOPTFLAGS) -c $<
 
      %.cmi: %.mli
          $(OCAMLC) $(OCAMLFLAGS) -c $<
 
      .FORCE:
 
      doc:	.FORCE
          mkdir -p doc
          $(OCAMLDOC) -html -d doc *.mli *.ml
 
      clean:
          rm -f *.cm[iox] *.o
 
      .depend:
          $(OCAMLDEP) $(INCLUDES) *.mli *.ml > $@
 
      depend:
          rm .depend
          $(MAKE) .depend
 
      include .depend
 

Oczywiście, aby dopasować ten Makefile do innego projektu wystarczy zmienić pierwsze
dwie definicje (PROG i CMOS).
Przykładową zmianę z dodanym niestandardowym przepisem tworzenia jednego z plików .ml można
zobaczyć tu.

Podobny (choć gorszy) uniwersalny Makefile dla projektów ocamlowych znajduje się w dokumentacji do
Ocamla, w rozdziale 13, poświęconym generatorowi zależności ocamldep:
http://caml.inria.fr/pub/docs/manual-ocaml/manual027.html#htoc148

Naprawdę zaawansowany Makefile

Oto naprawdę potężny Makefile do projektów w Ocamlu, który (prawie) wszystko robi sam:
http://hg.ocaml.info/release/ocaml-make/file/d4e96574afbe/OCamlMakefile
Jego autorem jest Markus Mottl, a tu jest opis:
http://www.ocaml.info/home/ocaml_sources.html#ocaml-make

Główna wada tego narzędzia jest taka jak wszystkich skomplikowanych narzędzi, które starają się być bardzo domyślne:
jeśli wszystko działa dobrze -- jesteśmy szczęśliwi; ale jeśli pojawi się najmniejszy problem, nie mamy
pojęcia jak go naprawić, bo nie wiemy jak działa nasze skomplikowane narzędzie.

Dokumentacja make

Pełna dokumentacja programu make znajduje się np. na stronach GNU:
http://www.gnu.org/software/make/manual/

To samo można również znaleźć za pomocą komendy info make lub spod emacsa: M-x info ENTER m make ENTER.

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ń,
• tutaj znajduje się plik z testami.
  

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.
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.

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.
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.
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\).
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.
6. 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.

Ć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).
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).
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!\).
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\)).
5. 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].
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).

8. Dane są dwie listy liczb całkowitych uporządkowane niemalejąco.
   Oblicz ile różnych liczb występuje na tych listach.
9. Napisz program wybierający \(\max\) i \(\min\) z listy i dokonujący (w miarę) jak najmniejszej liczby porównań.
10. Napisz program wybierający element dominujący z listy większościowej; uzasadnij jego poprawność.
11. 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]]\).

12. 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\).
13. 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.

14. 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.

15. [V OI, zadanie Bankomaty]
    System -2-kowy jest podobny do systemu binarnego, ale podstawą tego systemu jest liczba -2.
    Mamy 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ę reprezentacja : int → int list, która dla danej liczby całkowitej
    znajdzie jej przedstawienie w systemie o podstawie -2.
    Lista wynikowa powinna zawierać cyfry w kolejności od mniej do bardziej znaczących.
    Przyjmujemy, że lista pusta reprezentuje 0.

16. 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]
     

17. 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.
18. 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]] \).

19. [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).

20. 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. 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{inc} : \mathtt{int~list} \to \mathtt{int~list}\), która dla
       danej listy będącej reprezentacją liczby \(x\), wyznaczy reprezentację liczby \(x+1\).
    3. 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\).
    4. 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].
21. 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 | 
          Leaf;;
    

   Drzewo nazywamy ultralewicowym jeśli głębokości kolejnych liści (Leaf), 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. 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).

6. Dana jest deklaracja typu drzew binarnych:

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

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

   • skosokość Leaf 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, Leaf, Node(2, Leaf, Leaf)), 
               Node(6, 
                 Node(1, Leaf, Leaf), 
                 Node(3, Leaf, Leaf)
               )
             )
    
         skosokosc t = Node(5,
                         Node(6, 
                           Node(1, Leaf, Leaf), 
                           Node(3, Leaf, Leaf)
                         ),
                         Node(4, Node(2, Leaf, Leaf), Leaf) 
                       )
    

   Skosokość tak uzyskanego drzewa wynosi 5.

7. [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?

8. Dane jest definicja typu:

    
         type tree = 
           Node of tree * tree | 
   	Leaf
    

   .
   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 (Leaf) jest równa 0.

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

9. Dana jest deklaracja typu:

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

   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?

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

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

    Przekrojem drzewa nazwiemy dowolny taki zbiór jego wierzchołków (Node), że na każdej ścieżce
    od korzenia do liścia (Leaf) 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.

11. 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.
12. Napisz procedurę, która przekształca dane drzewo binarne w wyważone drzewo binarne, zachowując kolejność elementów w porządku infiksowym.
13. Dany jest typ reprezentujący drzewa binarne:

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

    Zdefiniuj typ α przechadzka oraz procedury:

     
          buduj    : α tree        → α przechadzka
          w_lewo   : α przechadzka → α przechadzka
          w_prawo  : α przechadzka → α przechadzka
          w_gore   : α przechadzka → α przechadzka
          obejrzyj : α przechadzka → α
     

    umożliwiające ,,przechadzanie'' się po drzewie i oglądanie go.
    Wywołanie buduj d powinno konstruować przechadzkę, w której znajdujemy się w korzeniu drzewa d.
    Wywołanie w_lewo p powinno konstruować przechadzkę powstałą przez przejście do lewego poddrzewa.
    Analogicznie powinny działać procedury w_prawo i w_gore.
    Procedura obejrzyj powinna zwrócić element przechowywany w wierzchołku drzewa, w którym aktualnie jesteśmy.

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

Ć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 z operacjami kresu górnego i dolnego.
9. Struktura implementująca porządek liniowy na liczbach całkowitych z operacjami max i min.

Ć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ść?

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.
6. 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].
7. 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].
8. 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]].
9. 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 [] = []
    

10. 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]\).
11. 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 \(i < 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.

12. 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.

13. Maksymalne plateau w liście (bez rekurencji).
    Napisz procedurę palteau : α list → int, która oblicza długość najdłuższego stałego (spójnego) fragmentu danej listy.
14. 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.
15. 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.
16. 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.
17. 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.

18. 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}|\).
19. 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.
20. 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.
21. 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]
     

22. 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]
     

23. 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]]
     

24. 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]]
     

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

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

1. Dane są następujące definicje:

    
           type 'a tree = Node of 'a tree * 'a * 'a tree | Leaf;;
           let rec fold_tree f a t = 
             match t with
               Leaf -> a |
               Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;
    

   Mówimy, że drzewo ma kształt drzewa AVL, jeżeli dla każdego węzła drzewa wysokości jego obu poddrzew różnią się o co najwyżej 1.
   Napisz procedurę: \(\mathtt{avl\_shaped} : \alpha\ \mathtt{tree} \to \mathtt{bool}\), która sprawdza czy dane drzewo ma kształt drzewa AVL.

   Rozwiązując to zadanie nie wolno Ci tworzyć żadnych procedur rekurencyjnych.
   Zamiast tego należy wykorzystać procedurę fold_tree lub inne standardowe procedury wyższych rzędów.

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

    
         type α tree = Node of α tree * α * α tree | Leaf;;
         let rec fold_tree f a t = 
           match t with
             Leaf -> a |
             Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;
    

   Użyj procedury fold_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. zaimplementowania procedury map_tree --- odpowiednika procedury map dla drzew,
   6. skonstruowania listy elementów znajdujących się w wierzchołkach drzewa, w kolejności infiksowej,
3. 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. policzenia wysokości drzewa,
   3. zaimplementowania procedury map_tree --- odpowiednika procedury map dla drzew,
   4. sprawdzić czy drzewo jest zrównoważone, tzn. wszystkie jego liście są na tej samej głębokości,
   5. sprawdzić czy drzewo regularne, tzn. wszystkie jego wierzchołki, z wyjątkiem liści, są tego samego stopnia.
   6. Powiemy, że wartość w węźle drzewa jest widoczna, jeżeli na ścieżce od tego węzła do
      korzenia drzewa nie ma większej wartości (w sensie standardowego porządku >).
      W szczególności liczba w korzeniu drzewa jest zawsze widoczna, a liczby mniejsze od niej nie są nigdy widoczne.
      
      Napisz procedurę widoczne : int drzewo → int, która dla zadanego drzewa (zawierającego wyłącznie
      nieujemne liczby całkowite) wyznaczy listę widocznych liczb.
4. 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. Wanna (w kształcie prostopadłościanu) jest wypełniona wodą.
   Po wyciągnięciu korka woda wylewa się z wanny z prędkością proporcjonalną do wysokości słupa wody \(h\).
   Jakiego rzędu jest czas potrzebny do wylania wody z wanny (z wyjątkiem warstewki grubości 1mm, która może zostać na dnie).
3. 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?
4. 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ść?
5. 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.
6. 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.

7. [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.

8. [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.

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.
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. 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\).
3. Rozszerzyć implementację kolejek FIFO o wkładanie i wyjmowanie elementów z obydwu stron (w koszcie zamortyzowanym stałym).
4. 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.

5. 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)\).
6. 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.
7. 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].
8. [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).

9. [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.
10. [*][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. [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.
5. [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?
6. [SICP]
   Korzystając z wyników poprzednich ćwiczeń podaj, jak można skonstruować pakiet funkcji wymiernych?
7. [SICP]
   Korzystając z wyników poprzednich ćwiczeń podaj, jak można skonstruować pakiet wielomianów dwóch zmiennych?
8. [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
    

3. Dana jest deklaracja drzew binarnych, w których węzłach znajdują się dodatkowo referencje do węzłów drzewa:

    
         type α drzewo =
           Puste |
           Wezel of α * α drzewo * α drzewo * α drzewo ref;;
    

   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 Puste.)
      Napisz procedurę fastryguj : α drzewo → unit, która sfastryguje dane drzewo.
   2. Napisz procedurę w_lewo : α drzewo → unit, która w każdym węźle drzewa ustawia referencję tak,
      aby wskazywały na węzeł (Wezel) 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 Puste.
   3. Napisz procedurę potomek : α drzewo → unit, która w każdym węźle ustawi referencję na najgłębiej położony węzeł
      (Wezel) będący jego potomkiem.
4. Dana jest tablica par dodatnich liczb rzeczywistych.
   Liczby te, to długości boków pewnych prostokątów o takich samych polach.
   Lista 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.
5. 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.
6. [PCH]
   Dana jest tablica liczb całkowitych \(a=[|x_1; x_2; \dots; x_n|]\).
   Tablica ta ma taką własność, że liczby \(x_{i+1} - x_i\), dla \(i=1, 2, \dots, n-1\), tworzą ciąg rosnący.
   Napisz procedurę \(\mathtt{rozne} : \mathtt{int~array} \to \mathtt{bool}\), która dla danej tablicy sprawdza, czy jej elementy są parami różne.

   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.

7. [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.
8. Napisz procedurę sprawdzającą, czy dana lista zawiera cykl.
   Czy potrafisz wyznaczyć jego długość?

Ćwiczenia 17: Imperatywne wskaźnikowe struktury danych

1. Zaimplementuj imperatywną kolejkę FIFO.
2. Zaimplementuj kolejki FIFO+LIFO jako imperatywne listy dwukierunkowe.
3. [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.

4. [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łpkaxtrzyma którą, oraz na podstawie opisu łapek puszczanych w
   kolejnych chwilach, dla każdej małpki wyznaczy moment, kiedy spadnie ona na ziemię.

5. 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.
6. 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.

7. [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)\).

8. [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ę liczby ze 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.

Ćwiczenia 19: Przeszukiwanie grafów

1. [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)\).

2. [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.

3. [II OI, zadannie Palindromy]
   Podziel dane słowo (listę znaków) na minimalną liczbę palindromów parzystej długości.
4. 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.

5. [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ę 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.)
2. 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ć.
3. [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.

4. 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.

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

1. Jaka jest minimalna liczba monet potrzebna do wydania \(n\)zł reszty, przyjmując, że w obrocie są dostępne monety o zadanych (w postaci listy) 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. [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?
4. 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.

5. [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.

6. 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).

7. [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.
8. 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)\).

9. [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.
10. [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.

11. [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ć?
12. [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ń.
13. [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. [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.
9. 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ć.
10. [II OI, zadanie Palindromy]
    Podziel dane słowo (listę znaków) na maksymalną liczbę palindromów parzystej długości.
11. [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?
12. 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].
13. [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.
14. [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.
15. [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.
16. [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?
17. [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.

18. [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. [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}\).
3. [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.
4. 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].
5. 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]\).

6. 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]\).
7. Dany jest ciąg liczb całkowitych, w postaci listy.
   Napisz procedurę podciagi : int list → int list list, która rozbije dany ciąg liczb na minimalną liczbę podciągów (ściśle) rosnących.
8. 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]].

9. [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\).
10. [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?
11. 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\).

12. 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. [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.
6. [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.

7. 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).