1
Informatica GeneraleMarzia Buscemi [email protected]
Ricevimento: Giovedì ore 16.00-18.00, Dipartimento di Informatica, stanza 306-PS o per posta elettronica
Pagina web del corso: http://www.di.unipi.it/~buscemi/IG07.htm
(sommario delle lezioni in fondo alla pagina)
2
Nella scorsa lezione abbiamo visto esempi di algoritmi per risolvere
problemi (numerici e non numerici) come dividere un problema in sotto-
problemi e quindi trovare un algoritmi componendo sotto-algoritmi
... usando generalmente gli array
3
Oggi..
Completeremo l’argomento della scorsa lezione trattando un’altra struttura dati: i record
Vedremo due diversi paradigmi di programmazione (imperativa, orientata agli oggetti)
Parleremo di ipertesti e vedremo un linguaggio ipertestuale (l’HTML)
4
Record 1 Gli array sono sequenze di valori dello stesso tipo:
interi, reali … caratteri (‘a’,’b’, …) sequenze di caratteri (dette stringhe, ”gatto ”, ”oggi piove !” …)
I record sono aggregati di variabili di tipo diverso e permettono di definire nuovi tipi
5
Record 2 A cosa possono servire…...
A rappresentare le schede della biblioteca:
Nome Autore
Cognome Autore
Titolo
Scaffale
Posizione
… altre informazioni …..
stringa
stringa
stringa
intero
intero
Campi del record
6
Record 3 Il tipo record scheda espresso in linguaggio C
struct scheda {
char nome[100]; //stringa di al più
//100 caratteri
char cognome[100];
char titolo[300];
int scaffale;
int posizione;} ;
7
Record 4//Come dichiaro che voglio
//una variabile di tipo ‘scheda’
struct scheda nuovo_libro;
// come assegno valori ai diversi campi
nuovo_libro.nome =”Jorge";
nuovo_libro.cognome =”Amado";
nuovo_libro.titolo =”Dona Flor e i suoi due mariti";
nuovo_libro.scaffale =8;
nuovo_libro.posizione =356;
8
Record 5 Si possono definire array di record
questo può servire, ad esempio a definire l’insieme delle schede di una biblioteca:
struct scheda archivio[100000] possiamo quindi formalizzare un semplice
algoritmo per la ricerca in uno schedario
Importante: archivio[2] è il record con indice 2 dell’array archivio[100000], mentre archivio[2].titolo è il campo titolo del libro che corrisponde al record archivio[2].
9
Esempio: ricerca in un archivio La biblioteca
Libri disposti sugli scaffali La posizione di ogni libro è fissata dalle due coordinate (S,P) dove
S è il numero dello scaffale dove si trova il libro P è la posizione all’interno dello scaffale
La biblioteca ha uno schedario con una scheda per ogni libro. Ogni scheda contiene, nell’ordine: cognome e nome dell’autore titolo del libro numero scaffale (S) e posizione nello scaffale (P)
10
Esempio: ricerca in un archivio 2
La biblioteca (cont.) Le schede sono ordinate in ordine alfabetico del campo autore
Problema: Vogliamo specificare un algoritmo che spieghi all’utente della biblioteca come trovare un libro cercato supponendo di sapere : Autore e Titolo
11
Esempio: ricerca in un archivio 3
Un primo algoritmo per il prestito:1. Decidi il libro da richiedere 2. Cerca la scheda nello schedario3. Trascrivi la posizione (S,P) 4. Accedi alla posizione (S,P)5. Preleva il libro e compila la scheda di prestito
Le operazioni elementari in questo caso sono piuttosto complesse…
12
Esempio: ricerca in un archivio 4
… e se non so come si effettua la ricerca nello schedario ?
Tutte le operazioni specificate devono essere ‘elementari’ per chi esegue l’algoritmo. Se non lo sono è possibile spiegarle a parte per mezzo di un sotto-algoritmo
13
Esempio: ricerca in un archivio 5
Un sotto-algoritmo per cercare nello schedario :1. Apri il classificatore2. Prendi la prima scheda3. Confronta il campo autore e titolo con quelli cercati4. Se sono uguali, allora la ricerca è terminata, altrimenti prendi la scheda successiva e vai al passo 35. Se le schede sono esaurite, allora il libro cercato non esiste.
14
I < 100000 ?
Inizio
Fine
Si No
Ricerca scheda(ricerca)
I = 0
I = I + 1
Strutture dati: struct scheda archivio // l’array di schede
Input : struct schedaarchivio
Output : la scheda cercata e un valore (si/no) che dice se c’è
Leggi Nome, Cognome e Titolo del libro cercato
archivio[I].nome = Nome archivio[I].cognome = Cognome
archivio[I].titolo = Titolo?
Si Fine
No
L’ho trovata!
Non l’ho trovata!
15
Esercizi proposti
Dare il diagramma per il sottoalgoritmo stampa_Na Trovare un algoritmo (e fornire il diagramma di flusso) per i
seguenti problemi : trovare la somma dei primi K numeri (K letto in input) trovare la media di una sequenza di numeri positivi (la
sequenza viene letta dall’esterno e si interrompe al primo numero negativo letto)
trovare il max dei numeri posti sulla diagonale di una matrice M*M
Date in input N schede di un archivio (vedi esempio), stampare il titolo e la collocazione di tutte le schede che hanno il campo autore “Umberto Eco”.
16
Paradigmi di programmazione
Programmazione imperativa (es. Linguaggio C)
Programmazione dichiarativa (funzionale, logica; es. ML, Lisp, Prolog)
Programmazione orientata agli oggetti (Java)
17
La programmazione imperativa Obiettivo: efficienza nella progettazione e
scrittura dell’algoritmo Caratteristiche:
attinenza al modello architetturale di Von Neumann
è conforme ai principi della programmazione strutturata (usa strutture di controllo)
ma permette di manipolare i dati facendo riferimento alla struttura fisica del calcolatore (le istruzioni sono assegnamenti da dare alle locazioni di memoria)
18
La programmazione imperativa.Esempio: funzione max in C 1
d > 0 ?
Inizio
Fine
Leggi x e y
Si No
d = x - y
Scrivi ‘max è x’ Scrivi ‘max è y’
19
La programmazione imperativa.Esempio: funzione max in C 2
main() /* calcola max */
{
int x, y, d; //def. Delle variabili
scanf ("%d %d”, &x, &y) ; //lettura x,y
d = x - y ;
if (d > 0) //scrittura risultati
printf (”il max è %d”, &x) ;
else
printf (”il max è %d”, &y) ;
return ; //terminazione
}questo programma stampa il risultato ma non restituisce nessun valore in output
20
La programmazione imperativa.Esempio: funzione max_N in C 1
main() /* calcola max_N */
{ int m, i, a, b;
i = 2 ;
scanf ("%d %d”, &a, &b);
m = max(a,b);
while (i < N) { scanf ("%d ”, &a) ;
m = max(a,m); }
printf (”il max è %d”, &m) ;
return ;
}
21
La programmazione imperativa.Esempio: funzione max_N in C 2
int max(int x, int y)
/* sottoprogramma che calcola max */
{ int d;
d = x - y ;
if (d > 0) return x;
else return y;
} notare che questo programmaè una variante del programmavisto nella penultima slide che:•prende in input x e y, piuttosto che leggerli da tastiera•restitusce in output il risultato, piuttosto che stamparlo
22
I < N ?
Inizio
Fine
Leggi i primi due numeri x1 e x2e memorizzali nelle variabili a e b
Si No
Leggi il nuovo numero in a
Scrivi ‘max è m’
m = max(a,b)
m = max(a,m)
DF per il problema delmassimo di N numeri
Leggi N I = 2
I = I + 1
Supponiamo N almeno 2
23
La programmazione imperativa.Esempio: funzione ordina_Na in C
main() /* calcola max_N */
{ int m, i, t, X[N], N, lung;
leggi_Na (N, X) ;
m = X[0];
lung = N ;
while (N > 1) { max_Na(X,N,&m,&i) ;
t = X[N];
X[N] = X[i] ;
X[i] = t ;
N = N - 1 ; }
stampa_Na (X,lung) ;
return ;}
24
La programmazione orientata agli oggettiEnfasi: semplicità di programmazione e riuso di
sottoprogrammi esistenti (modularità)Concetti base: classe: entità astratta caratterizzata da un insieme
di proprietà che definiscono sia le strutture dati della classe (attributi) sia le sue funzionalità (metodi)
oggetti: istanze delle classi descritte da valori associati alle diverse proprietà definite per la classe
Un programma in POO è costituito da oggetti che interagiscono tra loro
La POO è particolarmente adatta per programmare interfacce grafiche
25
La programmazione orientata agli oggetti. Esempio in Java 1
Java è un linguaggio di programmazione OO. Java fornisce moltissime classi raccolte in packages.
Es. consideriamo la classe java.awt.Rectangle che definisce degli oggetti che rappresentano rettangoli. Ogni rettangolo (istanza della classe) ha quattro variabili, che rappresentano la dimensione del rettangolo (height e width) e la posizione nel piano del suo vertice superiore sinistro (x e y).
26
La programmazione orientata agli oggetti. Esempio in Java 2
Rappresentazione grafica dei tre oggetti
Es. Consideriamo tre rettangoli, ognuno rappresentato da una scatola avente in alto il nome della classe, e sotto le variabili.
27
La programmazione orientata agli oggetti. Esempio in Java 3
Vogliamo scrivere un programma che:
•Crea un rettangolo di coordinate x = 5 e y = 10 e dimensioni height = 20 e width = 30; •Stampa lo stato del rettangolo; •Sposta il rettangolo di 15 unità lungo l'asse x e di 25 lungo l'asse y; •Stampa il nuovo stato del rettangolo.
28
La programmazione orientata agli oggetti. Esempio in Java 4
Consultando la documentazione della classe Rectangle vediamo come costruire un rettangolo con i valori desiderati per le variabili, e che esiste un metodo d'istanza translate. Il programma risultante è il seguente:
import java.awt.Rectangle;
public class MoveRectangle {
public static void main(String[] args) { Rectangle rect;rect = new Rectangle(5, 10, 20, 30);System.out.println(rect); rect.translate(15, 25); System.out.println(rect);
} }
29
La programmazione orientata agli oggetti. Esempio in Java 5
Vediamo questo semplice esempio in dettaglio:1. Dichiariamo di voler usare la classe Rectangle del package
java.awt: import java.awt.Rectangle;
...2. Dichiariamo una variabile rect di tipo Rectangle e le assegnamo
un nuovo oggetto con i valori desiderati per le variabili d'istanza: ...
public class MoveRectangle { public static void main(String[] args) {
Rectangle rect;
rect = new Rectangle(5, 10, 20, 30); ...
3. Stampiamo lo stato del rettangolo: ...
System.out.println(rect); ...
nome del programma
tipo dell’inputcrea un nuovo oggetto
30
La programmazione orientata agli oggetti. Esempio in Java 6
Invochiamo il metodo d'istanza translate sull'oggetto rect per spostarlo della quantità voluta:
... rect.translate(15, 25);
... Infine stampiamo lo stato finale:
... System.out.println(rect);
Output: java.awt.Rectangle[x=20,y=35,width=20,height=30]
Importante: per invocare un metodo d'istanza su di un oggetto si scrive <oggetto>.<metodo>(<parametri>)
31
Linguaggi Ipertestuali
Ipertesto: documento la cui consultazione è non lineare, cioè le sue parti (paragrafi, capitoli, etc.) sono organizzate non semplicemente in successione, ma secondo una struttura più complessa
Ogni parte del documento può contenere dei punti di aggancio (link) che rimandano ad altre parti
Es. ciascuna pagina Web, l’intero World Wide Web (le pagine possono risiedere su siti diversi)
I documenti ipertestuali contengono sia informazione (dati) sia meta-informazione (organizzazione dei dati)
32
Linguaggi Ipertestuali: HTML 1
HTML (Hyper Text Mark-up Language) è un linguaggio usato per descrivere ipertesti.
Non è un linguaggio di programmazione, ma un linguaggio di markup, cioè descrive il contenuto (testuale e non) delle pagine Web per mezzo di opportuni “segnaposto”.
Elementi: sono gli atomi principali di della sintassi di documenti HTML
(strutture del linguaggio) Ogni elemento è racchiuso da segnalini (tag), uno di apertura
e uno di chiusura. Es. <html> <head> <title> Nome del documento </title> </head> <body> Testo visibile </body> </body> </html>
33
Linguaggi Ipertestuali: HTML (2)
All’interno di <body> </body> è possibile inserire mediante tag: intestazioni di varie dimensioni(<h1>, <h2>, etc.) elementi di testo (paragrafi, linee orizzontali) stili (grassetto, corsivo, etc.) link ad altre pagine e a immagini liste puntate e numerate tabelle ...
Manuali e esempi on line su HTML: http://www.w3schools.com/html/default.asp
34
Scrivere documenti in HTML
I documenti in HTML possono essere editati come semplici documenti (con estensione .htm o .html) o tramite dei programmi
Nvu è un editor html molto semplice da usare, che permette di creare pagine web senza conoscere il linguaggio html, basta saper formattare le pagine
NVU è open source e gratutito e si può scaricare da:
http://www.nvu.com
