prompt$ polecenie [ENTER]mc Twoim przyjacielemls - list - czyli wyświetl pliki w katalogu,
ls /usr/
ls -l
ls -a
ls -al /usr/
ls -R
cd - change directory - zmień katalog
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]
mcedit - prosty, wbudowany w mc,joe - w stylu edytorów Borlanda, pico, nano - proste, tekstowe, gedit, kate - okienkowe
vi - jest wszędzie, tekstowy, początkowo nieintuicyjny, skomplikowany, po dokładnym poznaniu efektywny, emacs - rozbudowany, początkowo skomplikowany, po bliższym poznaniu efektywny,C:\, jest jedno drzewo plików.mount) w systemie plików ils 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
ln plik1.ocaml plik1.ml
ln -s docs Dokumenty
mount - pokazuje co gdzie jest zamontowane. 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).
pine / mutt -- używanie poczty w konsoli.forwardPoziomy te będziemy dalej oznaczali literkami u, g, o oraz a (All).
ls -l
chmod - change mode - zmiana praw dostępu.chmod u+rwx * chmod o-r *.c chmod ug+rx Pliki
chown - change owner - zmień właścicielachgrp - change group - zmień grupę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ścieuniq - 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`
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ówCtrl-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,x="ala ma kota" - przypisanieecho $x w paski - odwołanie się do wartościx=$[y * 2 + z] - wyrażenia arytmetyczneecho $HOME $USER $MAIL $PATH - różne ciekawe zmienne.#!/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
ls --help
man ls
info ls
opcja --help działa dla wszystkich poleceń
man polecenie - też!
info polecenie - też (wyjście: ^X^C)
.
ocaml 2+3;; ^D
(nie działają strzałki itp.)
ledit ocaml
(działają strzałki!!!)
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";;
#use "plik.ml";;
W terminalu piszemy:
ab123456@komputer:~$ ocaml
2+3;;
^D
(nie działają strzałki itp :-( )
ab123456@komputer:~$ ledit ocaml
(dzialaja strzalki! :-)
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";;
W terminalu wpisujemy ocaml (lub lepiej ledit ocaml).
W drugim okienku uruchamiamy edytor i co chwilę kopiujemy kod myszką.
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ę).
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.
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
emacsemacs poleceniem emacs plik.ml,;;W przypadku gdy chcemy rozpocząć pracę w ocamlu od nowa:
| Załącznik | Wielkość |
|---|---|
| emacs. | 846 bajtów |
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.
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.
| Załącznik | Wielkość |
|---|---|
| plik.mli | 90 bajtów |
| plik.ml | 135 bajtów |
| drugi_plik.ml | 119 bajtów |
| moduly.zip | 537 bajtów |
Celem tego laboratorium jest przećwiczenie operacji na listach.
Środkiem do tego celu będą operacje na wielomianach symbolicznych.
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.:
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, 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.
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. *)
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?
Kompilator ocamla możemy wywołać jako program o nazwie ocamlc lub ocamlopt.
Ocamlc generuje kod bytecode'u (pliki *.byte), który nie jest bezpośrednio wykonywany, ale interpretowany. Taki kod jest niezależny od maszyny, na której jest wykonywany, a więc jest przenośny. Jego interpretacją zajumuje się program ocamlrun, dla użytkownika nie jest to jednak widoczne. Po prostu uruchamiamy plik skompilowany.
Ocamlopt generuje kod dla konkretnej architektury i systemu (kod natywny, pliki *.native). Nie jest on przenośny, ale działa szybciej.
Obu kompilatorom przekazujemy podobne zestawy argumentów:
Przykład: ocamlc leftist.mli leftist.ml test.ml -o test
Kompilująć program w ten sposób, zawsze kompilujemy wszystkie pliki źródłowe. W przypadku bardzo małych projektów, może to być akceptowalne.
Jednak już w przypadku projektów średniej wielkości właściwe jest kompilowanie osobno wszystkich modułów (które tego wymagają) i łączenie ich kodu w jeden plik wykonywalny.
Skompilowane interfejsy modułów (pliki *.mli) to pliki o rozszerzeniu *.cmi.
Implementacje modułów skompilowane do kodu natywnego mają postać plików z rozszerzeniem *.o (standardowy format object-code) oraz *.cmx (pliki typowe dla Ocamla).
Implementacje modułów skompilowane do bytecode'u maję postać plików z rozszerzeniem *.cmo.
Chcąc skompilować tylko jeden plik, interfejsu lub implementacji modułu, wystarczy podać odpowiedniemu kompilatorowi opcję -c.
Typowym narzędziem uniksowym do kompilowania projektów jest program make wraz z plikiem Makefile opisującym
zależności między plikami. Jednak do kompilacji małych lub średnich projektów w Ocamlu lepiej użyć programu ocamlbuild.
Założenia: wszystkie potrzebne pliki źródłowe są w bieżącym katalogu.
Wystarczy wykonać ocamlbuild program.native lub ocamlbuild program.byte. Ocamlbuild sam zbada zależności między modułami i skompiluje dokładnie to co jest niezbędne. Wszystkie pliki generowane automatycznie będą umieszczone w katalogu _build,
a w bieżącym katalodu pojawi się dowiązanie do skompilowanego programu.
Więcej o programie ocamlbuild: https://ocaml.org/learn/tutorials/ocamlbuild/
Programowanie to sport zespołowy. Duże programy są tworzone przez zespoły, lub wiele współpracujących zespołów. Bywa i tak, że nikt nie ma wiedzy o całym systemie, a każdy zna tylko jego fragmenty. Jak sensownie funkcjonować w takich realiach? Oto kilka zasad dobrego warsztatu programisty.
Dla kogo piszemy kod? Dla komputera? Ależ skąd! Piszemy dla siebie i swoich współpracowników. Inaczej, po skompilowaniu pierwszej wersji programu, możnaby kod źródłowy wyrzucić. Tymczasem program, który jest używany, będzie wielokrotnie modyfikowany, przez nas i naszych kolegów. Modyfikacje same są zwykle niewielkie, ale wymagają przeczytania większego fragmentu kodu. Wniosek: kod źródłowy jest więcej razy czytany, niż pisany. Powinniśmy więc go tak pisać, żeby się łatwo czytało i modyfikowało, a nie żeby jak najszybciej stworzyć pierwszą wersję.
Wcięcia muszą być! Kod bez wcięć nie będzie oceniany. Wszytkie szczegóły dotyczące wcięć wynikają z tego po co one są: wcięcia mają ułatwić szybkie dopasowanie początku i końca konstrukcji składniowej.
Wielkość wcięć: od 2 do 4, w zależności od smaku, ale konsekwentnie stała. Minimalna wielkość wcięcia to 2, bo inaczej "schodki" nie są widoczne. Maksymalna to 4, bo inaczej kod robi się strasznie szeroki.
W pozostałych szczegółach, możecie dobrać Państwo styl, który najbardziej Wam odpowiada, byle konsekwentnie. Tutaj można znaleć przykładowy dobry styl.
Robimy odstępy wokół operatorów binarnych i po znakach interpunkcyjnych. Nie robimy odstępów po wewnętrznej stronie nawiasów. Na przykład: 2 + 2 * 4, [2; 3; 4], (2, 3 - 4).
Odstępy w pionie (puste wiersze) też są ważne. Między definicjami procedur robimy wiersz lub dwa odstępu. Wewnątrz dłuższych procedur możemy też robić pojedyncze wiersze odstępu dla podkreślenia struktury kodu.
W podejściu do komentarzy można spotkać dwie skrajności:
Oba podejścia są złe. Owszem, kod ma być przejrzysty i ma być widać co się w nim dzieje, ale zawsze są pewne aspekty, które z niego nie wynikają, np. co jest celem? po co coś się dzieje? co zakładamy? Z drugiej strony, umieszczanie w komentarzach "relacji na żywo" z obliczeń mija się z celem i tylko utrudnia czytanie kodu. Podstawowa zasada brzmi: Komentarze mają ułatwić czytanie i zrozumienie kodu. Odnosi się to tak samo do innych programistów, z którymi współpracujemy, jak i do nas samych tylko za jakiś czas. Oto kilka typowych miejsc, w których warto umieszczać komentarze:
Identyfikatory powinny być znaczące. Jeśli z nazwy identyfikatora wynika czym jest argument, to często nie trzeba nic więcej o nim pisać w komentarzach.
Identyfikatory (nazwy stałych i procedur) powinny zaczynać się z małej litery. Wieloczłonowe nazwy proponuję łączyć podkreśleniem: taki_sobie_identyfikator.
Program, który jest rozwijany podlega ciągłym zmianom. Jak sprawdzić, czy kolejne zmiany nie wprowadzają nowych błędów do programu? Testować! Warto utrzymywać bogaty zestaw testów, które po każdej zmianie w programie możemy łatwo uruchomić. Testy nie zagwarantują nam poprawności kodu, ale odpowiedni zestaw testów potreafi wykryć większość błędów.
Pisząc kod, powinniśmy odrazu tworzyć dla niego testy. Dla każdej funkcjonalności / procedury piszemy testy. Mamy jakąś elementarną procedurę wykorzystywaną w naszym kodzie -- piszemy dla niej testy. Mamy procedurę integrującą kilka procedur pomocniczych w coś większego -- piszemy dla niej testy. Tak jak procedury tworzą hierarchię, tak testy tworzą swoistą piramidę. Powiniśmy mieć wiele prostych testów dla elementarnych procedur (unit testy), oraz mniejszą liczbę testów-scenariuszy symulujących sposób użycia całego systemu.
Jak pisać testy w Ocamlu? Najlepiej wykorzystać operację assert <warunek>;. (Uwaga na ";". Narazie nie wnikamy w imperatywność.) Sprawdza ona, czy warunek jest spełniony i jeśli nie, przerywa obliczenia. Gdy uruchamiamy kod "dla użytkownika", możemy wyłączyć sprawdzanie asercji opcją -noassert. Testy mogą być po prostu asercjami na poziomie definicji (tj. nie zagnieżdżonymi wewnątrz definicji). Umieszczanie asercji wewnątrz definicji procedur też ma sens, ale to już coś innego niż testowanie.
Dwie najpopularniejsze techniki pisania kodu, mające na celu wyeliminowanie błędów, to code reviews i pair-coding. Pair-coding polega na pisaniu razem w parach. Jedna osoba pisze kod, a druga śledzi i komentuje ten proces. Obie muszą rozumieć co się dzieje i być przekonane, że powstający kod jest poprawny. Code review polega na tym, że kod, lub zmiana w kodzie, napisana przez jednego programistę jest przeglądana przez innego programistę. Przeglądający może zgłaszać zastrzeżenia i wskazywać co należy poprawić. Zasadniczo reviewer nie wprowadza poprawek sam, z wyjątkiem drobiazgów. Tę właśnie technikę zastosujemy na Laboratorium.
Jeśli pracujemy w zespole wieloosobowym nad programem składającym się z wielu plików, to jak synchroizować wyniki swojej pracy? Do tego właśnie służą systemy kontroli wersji. System kontroli wersji pamięta:
Starsze systemy kontroli wersji (RCS) wymagały blokowania plików w celu wprowadzania zmian w nich. Nowsze systemy kontroli wersji (Subversion, Git) pozwalają na równoczesne wprowadzanie zmian w tych samych plikach przez wielu programistów. W praktyce dobrze się to sprawdza. Jednak zmiany takie nie zawsze można automatycznie scalić. Czasami konieczna jest interwencja człowieka.
Git jest aktualnie chyba najpopularniejszym systemem kontroli wersji. Git jest systemem rozproszonym. Na każdym komputerze biorącym udział w tworzeniu programu znajduje się repozytorium zawierające kompletną (choć niekoniecznie aktualną) informację o historii wersji programu. Repozytoria mogą wymieniać między sobą informacje o wprowadzanych zmianach. Zwykle każdy programista ma jedno repozytorium lokalne na swoim komputerze, oraz istnieje jedno zdalne repozytorium, służące synchronizowaniu zmian.
W Git'ie konkretna wersja programu to commit. Commit ma poprzedni commit i wiadomo jakie zmiany względem niego wprowadza. Jeden poprzedni commit może mieć wiele następnych commitów (fork). Możliwy jest też commit o dwóch poprzednich commitach (merge), scalający zmiany wprowadzone od ich wspólnego poprzednika.
Zwykle myślimy w kategoriach gałęzi (branch), a nie commit'ów. Branch to wskaźnik na konkretny commit. W miarę wprowadzania zmian do kodu, wskaźnik ten jest przesuwany na kolejne commity. Zwykle mamy główną gałąź (trunk/master) oraz wiele gałęzi pobocznych, tworzonych na potrzeby opracowania poszczególnych zmian i łączonych potem z główną gałęzią.
Git bardzo dobrze wspiera przeglądy kodu. Typowy cykl opracowania zmiany w kodzie wygląda następująco:
Istnieje wiele serwisów oferujących przechowywanie zdalnego repozytorium, np. GitHub, BitBucket. Można też do tego wykorzystać współdzielony system plików, choć właściwa kontrola praw dostępu wymaga pewnie utworzenia mnóstwa grup. Jeżeli będziecie Państwo przechowywać swoje programy zaliczeniowe w repozytoriach, to proszę zadbać, żeby nie były one publicznie dostępne (przynajmniej dopóki nie minie ostateczny termin oddawania programów).
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:
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:
arytmetyka.ml,| Załącznik | Wielkość |
|---|---|
| wpf-0-arytmetyka.mli | 1.53 KB |
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:
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:
Łą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.
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.
| Załącznik | Wielkość |
|---|---|
| wpf-1-leftist.mli | 801 bajtów |
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
| Załącznik | Wielkość |
|---|---|
| wpf-2-origami.mli | 1.62 KB |
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.
| Załącznik | Wielkość |
|---|---|
| wpf-3-pSet.mli | 2.72 KB |
| wpf-3-pSet.ml | 4.51 KB |
| wpf-3-iSet.mli | 2.75 KB |
| wpf-3-modyfikacja.zip | 4.39 KB |
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.
| Załącznik | Wielkość |
|---|---|
| wpf-4-topol.mli | 436 bajtów |
| wpf-4-pMap.mli | 3.39 KB |
| wpf-4-pMap.ml | 4.58 KB |
| wpf-4-topol.zip | 3.47 KB |