Programmazione I e laboratorio
Da InformaWiki.
| Programmazione I e Laboratorio | |
|---|---|
| Sigla Corso: | PRL |
| Nome Docente/i: | Roberto Barbuti Paolo Mancarella |
| Corso di laurea: | Informatica |
| Anno di corso: | 1 |
| Home page del corso: | Corsi A e B |
Indice |
Programma
Obiettivi didattici
Introduzione alla risoluzione di problemi e alla programmazione con esercitazioni in laboratorio.
Programma completo
- Grammatiche libere
- Presentazione del Linguaggio funzionale Caml
- Programmazione funzionale
- Presentazione del Linguaggio imperativo C (rappresentazione numerica, funzioni, procedure, parametri, puntatori)
- Programmazione imperativa (array, liste, ecc.)
- Definizione di un interprete in Caml del Linguaggio Imperativo
Materie affini
Bibliografia
- Deitel & Deitel, C Corso Completo di Programmazione
- Kerighan & Ritchie, Il Linguaggio C
Approfondimenti
Libreria di funzioni utili
Le funzioni presenti nella seguente libreria sono tutte presenti sulla dispensa "Note di Programmazione Funzionale" di Giuseppe Manco, che fa riferimento alla release 0.73 di CAML Light. Nella release 0.74 alcune funzioni non sono definite nativamente ma sono definite in questa libreria. Per caricare la libreria in CAML Light salvare il codice in file con estensione .ml, lanciare l'interprete e da lì aprire il file. Se siete particolarmente pigri ma non vi pesa il dover aspettare, la libreria può essere anche scaricata da MegaUpload sia in formato testuale che Word... occhio però che la versione sia la più recente (i.e. sperabilmente quella riportata qui sotto).
(*
Le funzioni presenti in questa libreria sono tutte presenti sulla dispensa
"Note di Programmazione Funzionale" di Giuseppe Manco, che fa riferimento alla
release 0.73 di CAML Light. Nella release 0.74 alcune funzioni non sono definite
nativamente ma sono definite in questa libreria.
Versione: 1.2
*)
(* Funzione che associa ad un numero il suo quadrato *)
let square x = x * x;;
(* Funzione che associa il minimo tra due numeri *)
let min x y = if x <= y then x else y;;
(* Funzione che raddoppia il suo argomento *)
let double x = x + x;;
(* Funzione identità *)
let id x = x;;
(* Funzione che permette di passare da una versione uncurry ad una curry *)
let curry f x y = f (x,y);;
(* Funzione che permette di passare da una versione curry ad una uncurry *)
let uncurry f (x,y) = f x y;;
(* Funzione primitiva associata al tipo char che restituisce il carattere
relativo al codice ASCII passato come argomento *)
let chr = char_of_int;;
(* Funzione primitiva associata al tipo char che restituisce il valore ASCII di
un carattere passato come argomento *)
let code = int_of_char;;
(* Predicato che indica se un carattere rappresenta un numero *)
let isdigit x = `0` <= x & x <= `9`;;
(* Predicato che indica se un carattere rappresenta una lettera maiuscola *)
let isupper x = `A` <= x & x <= `Z`;;
(* Predicato che indica se un carattere rappresenta una lettera minuscola *)
let islower x = `a` <= x & x <= `z`;;
(* Funzione che rende maiuscolo un carattere *)
let uppercase x = if islower x
then let offset = code `A` - code `a`
in chr (offset + code x)
else x;;
(* Funzione che rende minuscolo un carattere *)
let lowercase x = if isupper x
then let offset = code `A` - code `a`
in chr (code x - offset)
else x;;
(* Funzione che seleziona il primo elemento di una coppia *)
let fst (x,y) = x;;
(* Funzione che seleziona il secondo elemento di una coppia *)
let snd (x,y) = y;;
(* Composizione di funzioni *)
let compose f g x = f (g (x));;
(* Funzione che restituisce il successore di un numero intero *)
let succ n = n + 1;;
(* Funzione che dice se una lista è vuota *)
let null xs = match xs with
[] -> true |
_ -> false;;
(* Funzione fold_right *)
let rec fold_right f z l = match l with
[] -> z |
(x::xs) -> f x (fold_right f z xs);;
(* Funzione che restituisce la lunghezza di una stringa
(definibile anche ricorsivamente) *)
let rec length = let oneplus x n = n + 1 in fold_right oneplus 0;;
(* Funzione che seleziona l'elemento ennesimo di una lista (da verificare) *)
let rec nth n xs = match xs with
(x::xs) -> match n with
1 -> x |
n when n>0 -> nth (n - 1) xs ;;
(* funzione che prende come argomenti un intero n ed una lista e seleziona
i primi n elementi della lista *)
let rec take n xs = match n, xs with
x, [] -> [] |
0, ys -> [] |
x, (y::ys) -> y::(take (x-1) ys);;
(* funzione che prende come argomenti un intero n ed una lista ed elimina i
primi n elementi della lista *)
let rec drop n xs = match n, xs with
0, ys -> xs |
x, [] -> [] |
x, (y::ys) -> drop (x-1) ys;;
(* Funzione che prende come argomento una lista di liste e restituisce la lista
risultante dalla concatenzazione delle liste *)
let concat = fold_right (prefix @) [];;
(* Funzione che permette di invertire l'ordine degli elementi di una lista *)
let rev = let postfix x xs = xs @ [x] in fold_right postfix [];;
(* Funzione fold_left *)
let rec fold_left f z l = match l with
[] -> z |
(x::xs) -> fold_left f (f z x) xs ;;
(* Funzione foldl (da verificare) *)
let foldl f xs = fold_left f (hd xs) (tl xs);;
(* Funzione foldr (da verificare) *)
let foldr f xs = fold_right f (hd (rev xs)) (rev (tl (rev xs)));;
(* Funzione che calcola il massimo valore di una lista *)
let maxlist = foldl max;;
(* Funzione che implementa la funzione somma sugli elementi di una lista *)
let sumlist = fold_right (prefix +) 0;;
(* Funzione che implementa la funzione prodotto sugli elementi di una lista *)
let product = fold_right (prefix *) 1;;
(* Funzione che implementa la funzione And sugli elementi di una lista *)
let And = fold_right (prefix &) true;;
(* Funzione che implementa la funzione Or sugli elementi di una lista *)
let Or = fold_right (prefix or) false;;
(* Funzione che prende come argomenti un predicato ed una lista e verifica che
tutti gli elementi della lista soddisfino il predicato *)
let for_all p xs = let cond x n= (p(x) & n) in fold_right cond true xs;;
(* Definizione ricorsiva di intervallo *)
let rec interval m n = if m>n then [] else m::interval (m+1) n;;
(* Funzione ausiliaria per la funzione "diff" *)
let rec remove xs y = match xs with
[] -> [] |
z::zs when z=y -> zs |
z::zs when z<>y -> z::remove zs y ;;
(* Funzione che restituisce una lista ottenuta da xs rimuovendo la prima
occorrenza di ogni y appartenente a ys *)
let rec diff xs ys = match ys with
[] -> xs |
(z::zs) -> diff (remove xs z) zs;;
(* Funzione ricorsiva che permette di invertire l'ordine degli elementi di
una lista *)
let rec rev l = match l with
[] -> [] |
(x::xs) -> rev xs@[x] ;;
(* Funzione ausiliaria necessaria per l'ottimizzazione della funzione "rev" *)
let rec revit l l1 = match l with
[] -> l1 |
x::xs -> revit xs (x::l1) ;;
(* Ottimizzazione della funzione "rev" *)
let reverse xs = revit xs [];;
(* Funzione ausiliaria per la successione di Fibonacci *)
let rec fibgen a b x = match x with
0 -> a |
n when n>0 -> fibgen b (a+b) (n-1) ;;
(* Funzione che calcola la successione di Fibonacci *)
let fastfib n = fibgen 0 1 n;;
(* Funzione che calcola la lista di tutti i segmenti iniziali di una lista,
per lunghezza crescente *)
let rec inits ls = match ls with
[] -> [[]] |
x::xs -> [[]] @ map (curry (prefix ::) x) (inits xs) ;;
(* Funzione che restituisce la lista di tutte le sottosequenze di una lista *)
let rec subs l = match l with
[] -> [[]] |
x::xs -> (subs xs) @ map (curry (prefix ::) x) (subs xs) ;;
(* Funzione che restituisce la lista di tutte le possibili liste ottenute da ys
inserendo il termine x *)
let rec interleave x ls = match ls with
[] -> [[x]] |
y::ys -> [x::y::ys] @ map (curry (prefix ::) y) (interleave x ys);;
(* Funzione che calcola tutte le possibili permutazioni di una lista *)
let rec perms l = match l with
[] -> [[]] |
x::xs -> concat (map (interleave x) (perms xs)) ;;
(* Funzione che ci dice se un numero è pari oppure dispari *)
let rec pari x = match x with
0 -> true |
1 -> false |
n when n>1 -> pari (n - 2) ;;
(* Funzione che restitisce il resto della divisione tra x e y *)
let rec mod1 x y = if x < y then x else mod1 (x-y) y;;
(* Dichiarazione di tipo *)
type temp = Celsius of float | Farhenheit of float | Kelvin of float;;
(* Funzione che converte una temperatura in gradi Chelsius *)
let convCels x = match x with
Celsius n -> Celsius n |
Farhenheit n -> Celsius ((5.0/.9.0)*.(n-.32.0)) |
Kelvin n -> Celsius (n+.273.0) ;;
(* Definizione di albero binario *)
type 'a btree = Empty | Node of 'a * 'a btree * 'a btree;;
(* Funzione che seleziona il figlio sinistro di un albero binario *)
let left bt = match bt with
Empty -> Empty |
Node (x, l, r) -> l ;;
(* Funzione che ricerca un elemento in un albero binario *)
let rec search x bt = match bt with
Empty -> false |
Node (y, lt, rt) when x=y -> true |
Node (y, lt, rt) when x<>y -> (search x lt) or (search x rt);;
(* Funzione che conta i nodi di un albero *)
let rec count bt = match bt with
Empty -> 0 |
Node (y, lt, rt) -> 1 + (count bt) + (count rt);;
(* Funzione che permette di definire la lista derivata dalla visita anticipata
di un albero *)
let rec prelim bt = match bt with
Empty -> [] |
Node (x, lt, rt) -> x::(prelim lt @ prelim rt) ;;
(* Funzione che restituisce il sottoalbero sinistro del sottoalbero bt la cui
radice è etichettata con x (da verificare) *)
let rec left x bt = match bt with
Empty -> [] |
Node (y, lt, rt) when x=y -> x::(prelim lt) |
Node (y, lt, rt) when x<>y -> left x lt ;;
(* Funzione che restituisce il sottoalbero destro del sottoalbero bt la cui
radice è etichettata con x (da verificare) *)
let rec right x bt = match bt with
Empty -> [] |
Node (y, lt, rt) when x=y -> x::(prelim rt) |
Node (y, lt, rt) when x<>y -> left x rt ;;
(* Funzione che trasforma una lista in un albero binario di ricerca,
utilizzando come perno l'ultimo elemento della lista *)
let rec buildtree l =
let rec insord x bt = match bt with
Empty -> Node (x, Empty, Empty) |
Node (y, lt, rt) when x<=y -> Node (y, insord x lt, rt) |
Node (y, lt, rt) when x>y -> Node (y, lt, insord x rt)
in match l with
[] -> Empty |
x::xs -> insord x (buildtree xs) ;;
Modifiche Versione
1.1
Corretto fold_left secondo il funzionamento illustrato nella dispensa (Note di Programmazione Funzionale p. 36) e in questa pagina Fold_(higher-order_function)
1.2
Corretto foldr secondo il funzionamento illustrato nella dispensa (Note di Programmazione Funzionale p. 37)
Modalità di esame
Scritto e orale. Per accedere all'orale si deve avere un voto o una media dei compitini >=16
Materiale aggiuntivo
Vecchi esami
Fondamenti di Programmazione (Vecchio Ordinamento)
Commenti
Corso abbastanza interessante, soprattutto per la parte di programmazione funzionale. Professore molto chiaro nelle spiegazioni e disponibile.
