Matlab Matlab Matlab Matlab Matlab Matlab

Matlab

Matlab

• MATLAB(Matrix Laboratory) è un ambiente di programmazione interattivo finalizzato all’esecuzione di calcoli con array e matrici, nel quale esistono sia strutture di controllo analoghe a quelle dei linguaggi di programmazione (cicli, condizioni), sia funzioni che forniscono semplici soluzioni numeriche (autovalori), sia funzioni che permettono la costruzione di grafici.

Matlab

• Esistono molti testi su Matlab, alcuni finalizzati ad argomenti specifici.

• L’utilizzo di questo ambiente necessita di una licenza.

• È disponibile gratuitamente in rete, in formato pdf, un Manuale Matlab a cura di Giuseppe Ciaburro, www.ciaburro.it

Matlab

• Per entrare nell’ambiente Matlab si deve digitare il comando matlab

• Si apre una finestra (nella versione installata in aula) suddivisa in tre parti: ambiente di programmazione, elenco dei file della propria cartella, elenco dei comandi utilizzati

• Il prompt dei comandi è >>

• Si esce dall’ambiente chiudendo la finestra (quit o exit).

Matlab

• In questo ambiente c’è uno spazio di lavoro, workspace, nel quale vengono memorizzate le variabili usate in quella sessione di lavoro.

Non esiste il concetto di “dichiarazione delle variabili”: infatti lo stesso nome di variabile può essere uno scalare e poi una matrice, un numero e poi una stringa, …

• Per attribuire un valore ad una variabile si scrive

nome = espressione

• Si ottiene una “risposta”: il nome della variabile e il suo valore.

Matlab

• Operatori.

* / + -

\ (divisione da destra a sinistra)

^ (elevamento a potenza)

• Lo spazio è un separatore.

Matlab

• Esempi.

>> x = 5 (linea di comando)

x = (risposta)

5

>> 2^3 (linea di comando) ans = (risposta)

8

• Quando non c’è un nome di variabile ma solo un’espressione (2^3), la risposta è memorizzata nella variabile ans.

Matlab

• Se successivamente eseguiamo un’altra operazione

>> 4\2 (linea di comando)

ans = (risposta)

0.5

anscambia il suo valore (ora vale 0.5).

• Per non avere la visualizzazione del valore dell’istruzione inserita, l’istruzione deve terminare con un ; . Il valore della variabile è comunque memorizzato nello spazio di lavoro.

Matlab

• Matricie vettori.

• Matrici e vettori (matrici con una sola riga) si possono introdurre elencando, tra parentesi quadre, tutti gli elementi.

• Si può definire un vettore riga (matrice 1_××××n) s= [ 1 1]

oppure

s= [ 1 , 1]

• dove gli elementi sono separati da spazi o virgole. Matlab distingue maiuscole e minuscole.

Matlab

• Il ; individua le righe, pertanto un vettore colonna (2_××××1) viene definito:

s = [ 1 ; 1]

• Costruiamo una matrice 2××××3 a = [1 2 3;4 5 6]

• Possiamo aggiungere una nuova riga:

r = [7,8,9]

a = [a;r] a = 1 2 3

4 5 6 7 8 9 s = 1

1 a = 1 2 3

4 5 6

Matlab

• Si può estrarre una sottomatrice, indicando quali e quante righe e colonne si vogliono estrarre:

b = a(1:2, 2:3)

si estrae dalla matrice a dalla prima alla seconda riga le colonne dalla 2 alla 3

• Se si vogliono estrarre tutte le colonne si indica solo il :

c = a(1:2,:)

b = 2 3 5 6

c = 1 2 3 4 5 6

Matlab

• Possiamo costruire una matrice accostandone altre:

a = [1 2 3;4 5 6]

b = [7;7]

c = [0 0 0 0;4 4 4 4]

d = [a b;c]

d = 1 2 3 7 4 5 6 7 0 0 0 0 4 4 4 4

Matlab

• Per costruire la trasposta di una matrice nota o di un vettore si usa l’apice:

a = c'

t = s'

a = 1 4 2 5 3 6

t = 1 1

Matlab

• Si può costruire una sequenza di valori da attribuire ad un vettore indicando: inizio, passo e fine, separati dal simbolo :

v = [1:2:8]

• Se si omette il passo, questo vale 1:

v = [1:6]

v = 1 2 3 4 5 6 v = 1 3 5 7

Matlab

• Con riferimento alla matrice d, abbiamo:

s = d(1:2:3, 1:2:3)

estraiamo dalle righe 1 e 3 le colonne 1 e 3 d = 1 2 3 7

4 5 6 7 0 0 0 0 4 4 4 4

s = 1 3 0 0

Matlab

• Somma e prodotto tra matrici.

• Date due matrici A e B di dimensioni compatibili, la somma e il prodotto si ottengono con gli operatori + e *:

A + B (somma)

A * B (prodotto righe per colonne)

• invece A .* B indica il prodotto elemento per elemento.

Matlab

• Prodotto tra vettori.

a = [1 2 3]

s = a .* a s = [1, 4, 9]

prodotto scalare

s = a * a' s = 14

s = a' * a s = 1 2 3

2 4 6 3 6 9

Matlab

• Funzioni per l’utilizzo di matrici. Siano a una matrice e v un vettore.

diag(a): restituisce un vettore che contiene la diagonale di a

diag(v): restituisce una matrice che ha v come diagonale

diag(a,k): restituisce un vettore che contiene la diagonale k-esima di a; con k = 0 si intende la diagonale principale, con k = -1,-2,… le diagonali sotto quella principale e con k = 1, 2, 3, … le diagonali sopra quella principale

Matlab

diag(v,k): restituisce una matrice la cui diagonale k-esima è v; con k = 0 si intende la diagonale principale, con k = 1,-2,… le diagonali sotto quella principale e con k = 1, 2, 3, … le diagonali sopra quella principale ones(n,m) : restituisce una matrice n ××× m× con tutti gli elementi uguali a 1; per ottenere un vettore (riga o colonna), n o m sono 1 zeros(n,m): restituisce una matrice n ×××× m con tutti gli elementi uguali a 0; per ottenere un vettore (riga o colonna), n o m sono 1

Matlab

• Costruzione di matrici combinando funzioni e operazioni:

a = diag([5:11]) (la diagonale di a ha 7 elementi)

a = a + diag(ones(6,1),1) (diagonale k=1 con 6 elementi)

v = [1:7]

a = a + diag(v(2:7),-1)

a = 5 1 0 .. 0 2 6 1 0 .. 0 0 3 7 1 0 ..0

…………..

0 … 6 10 1 0 0 .. 7 11

Matlab

• eye(n): restituisce la matrice identica di dimensione n

• tril(a) : restituisce una matrice che è la triangolare inferiore di a compresa la diagonale

• triu(a) : restituisce una matrice che è la triangolare inferiore di a compresa la diagonale

• eig(a) : restituisce la matrice degli autovettori e quella con gli autovalori

• inv(a) : restituisce l’inversa della matrice

Matlab

• Uso di Matlab nei problemi di calcolo numerico.

• Soluzione di un sistema lineare Ax = b

• Metodo di Jacobi.

• Indichiamo con

D la matrice diagonale di A -E= L la triangolare inferiore di A -F= U la triangolare superiore di A

Matlab

• La formula matriciale che esprime l’iterazione del metodo è:

x ^(k+1)= D^-1(E +F) x ^(k)+ D^-1b

x_i^(k+1)= b_i/a_ii-

∑

con s = 1,…, n e s≠ i

• La matrice d’iterazione è H = D^-1(E +F)

Matlab

• Usiamo le funzioni di Matlab per verificare se l’autovalore massimo della matrice d’iterazione H è in modulo minore di 1.

diag(A) diagonale di A

D = diag(diag(A)) matrice diagonale E + F = -(L + U) = D – A

H = D^-1(E +F) = D^-1(D - A) = I - D^-1A Calcolo dell’autovalore massimo di H

Matlab

[n,m]=size(A) deve essere n=m H = eye(n)- D\A

barra rovescia: D\A = inv(D)*A [autovett, autoval] = eig(H)

av = diag(autoval) m = max(abs(av))

Matlab

• Strutture di controllo.

for variabile=inizio:passo:fine istruzioni

end while P

istruzioni end

• I predicati sono scritti senza parentesi. La parola chiave end (deve essere scritta a capo) termina la struttura.

Matlab

• I confronti sono: == ^~= < >

• I predicati sono composti con & e |

if P istruzioni end

if P

istruzioni else istruzioni end

Matlab

if P

istruzioni elseif Q

istruzioni else

istruzioni end

• I commenti si introducono con il simbolo %

% commento su una riga

• Gli spazi sono separatori.

Matlab

• Il comando whos fornisce un elenco delle variabili con il loro nome e l’occupazione di memoria.

• Le matrici appaiono come n ×××× m, mentre gli array sono 1 _×××× n oppure n _×××× 1 e gli scalari sono 1 _××××1.

• Con il comando save nomefile si può salvare il contenuto del workspace in un file che in una successiva sessione può essere caricato con il comando load.

Matlab

• Programmi.

• Un programma scritto in Matlab può essere inserito in un file, la cui estensione deve essere .m

prova.m

• Si hanno due tipi di programmi:

1) script o file di comandi: non hanno argomenti

2) funzione: possono avere argomenti e restituire valori.

Matlab

• Uno script viene lanciato indicando il nome del file

>> prova

• Le istruzioni agiscono sulle variabili del workspace, e costruiscono valori che sono noti anche dopo che è terminata l’esecuzione del programma.

Matlab

• Le variabili all’interno della funzione sono variabili locali (non più note dopo la terminazione).

• La prima riga di una funzione deve essere:

function [parametri uscita] = nomefun(parametri ingresso)

• I parametri sono separati da virgole.

• La funzione deve essere scritta in un file con lo stesso nome.

Matlab

• Grafici.

• La funzione plot visualizza il grafico di una funzione in una finestra; si indicano i due array che rappresentano le ascisse e le ordinate e uno stile facoltativo (simbolo e colore) con cui si vuole rappresentare la curva:

plot(x, y, stile) plot(x1, y1, stile1,

x2, y2, stile2)

Matlab

• Si può inserire un titolo o delle etichette:

title('testo')

xlabel('testo') : il testo verrà inserito in basso nella direzione dell’asse x hold on : la pagina grafica viene bloccata così che il successivo grafico si sovrappone al precedente

hold off: la pagina grafica ritorna libera

Reti di calcolatori

Reti di calcolatori

• Testi di riferimento.

• A. S. Tanenbaum Reti di Computer Quarta Ed. Pearson, 2004

• M. R. Laganà, M. Righi, F. Romani Informatica. Concetti e sperimentazioni Seconda Ed. Apogeo, 2007

Cap.3 e 12

Reti di calcolatori

• Consideriamo una grande azienda composta da varie fabbriche dislocate in posti molto lontani tra loro: ogni fabbrica deve poter elaborare la gestione di acquisti, vendite, stipendi, ecc.

• Negli anni settanta esistevano grossi calcolatori a cui erano collegati terminali e stampanti, così che i vari utenti potevano risiedere nelle sedi lontane effettuando una elaborazione a distanza dell’unica macchina.

Reti di calcolatori

• Con l’avvento dei personal computer, sempre meno costosi e sempre più potenti, l’organizzazione del lavoro si è trasformata:

nelle varie aziende è presente un calcolatore che effettua una sua elaborazione autonoma.

• La necessità di comunicare informazioni di interesse comune rende comunque necessario che i calcolatori possano scambiare informazioni tra loro.

Reti di calcolatori

• A metà degli anni sessanta il Dipartimento della Difesa degli Stati Uniti affidò al suo ente di ricerca ARPA (Advanced Research Project Agency) il compito di costruire una rete che potesse resistere ad una guerra nucleare. Essa collegava centri di ricerca, università e strutture governative. La rete doveva essere composta da vari calcolatori, collegati da linee di trasmissione così che se un calcolatore fosse stato distrutto la comunicazione poteva avvenire per una via diversa. Questa rete prenderà il nome di Arpanet e sarà la progenitrice dell’attuale Internet.

Reti di calcolatori

• Con il termine rete di calcolatori si intende un insieme di calcolatori indipendenti, collegati tra di loro, in grado cioè di scambiarsi informazioni.

• Con gli anni novanta le reti di calcolatori incominciarono a fornire servizi ai singoli individui: accesso ad informazioni remote (servizi bancari, web, …), comunicazione uomo-a-uomo (email, videoconferenza), intrattenimento interattivo (giochi, video, …).

Reti di calcolatori

• La distanza tra le varie componenti porta ad una classificazione delle reti, accompagnata anche da diverse tecniche di trasmissione.

• Si parla principalmente di:

• reti locali

• reti metropolitane

• reti geografiche.

• Le reti di calcolatori possono a loro volta essere interconnesse tra loro (internetwork).

Reti di calcolatori

• Un’altra importante distinzione è la tecnologia di collegamento:

• reti a diffusione globale (broadcast), dove un unico canale di trasmissione è condiviso dalle varie macchine; il pacchetto di informazione viene inviato a tutte e un campo indirizzo indica quale è il destinatario

• reti punto-a-punto (point-to-point), dove sono connesse coppie di macchine e il pacchetto può attraversare più macchine intermedie (algoritmi di routing per scegliere il cammino più conveniente).

Reti di calcolatori

• Le reti locali, chiamate Local Area Network, sono reti private situate all’interno di uno stesso edificio o gruppo di edifici collegati (università, aziende) di dimensione che varia tra alcune decine di metri a qualche chilometro.

• Dal momento che le dimensioni sono ridotte spesso viene usata una linea telefonica locale (un solo cavo) a cui sono collegate tutte le macchine. La tecnologia broadcast può essere lineareo ad anello.

Reti di calcolatori

• Architettura broadcast (lineare)

M D

Reti di calcolatori

• Le reti metropolitane, chiamate Metropolitan Area Network, coprono aree poco più vaste delle LAN, con collegamenti sia privati che pubblici che collegano gruppi di edifici all’interno della stessa città.

• Utilizzano uno standard chiamato Distributed Queue Dual Bus composto da due bus a cui tutti i calcolatori sono collegati: il traffico destinato ad un calcolatore situato alla destra del mittente usa il bus superiore, quello che va a sinistra usa quello inferiore.

Reti di calcolatori

• Architettura DQDB

1 2 3 N

Bus A

Bus B

computer …..

Reti di calcolatori

• Le reti geografiche, chiamate Wide Area Network, coprono grandi aree: nazioni e continenti. Sono costituite da un insieme di macchine, dette host (ospite), che eseguono i programmi per gli utenti; ogni host è collegato ad una LAN su cui è presente un router.

Questi sono calcolatori intermedi (detti anche nodiper lo scambio di pacchetti) che eseguono la scelta di quale linea deve far proseguire il pacchetto.

Reti di calcolatori

• Due router possono essere collegati direttamente da una linea, oppure tramite una sottorete (router intermedi).

• In tale modo un pacchetto viene ricevuto da ogni router intermedio, memorizzato fino a quando la linea non è disponibile e quindi viene fatto proseguire. Questa tipologia si chiama: point-to-point, store-and-forward (memorizza e inoltra), sottorete packed- switched(commutazione di pacchetto).

Reti di calcolatori

• Architettura point-to-point

M

D

Reti di calcolatori

router

LAN

sottorete

WAN

Host

Reti di calcolatori

• L’architettura client-server (nasce negli anni ’90) è costituita da un calcolatore centrale, server, in grado di gestire grandi basi di dati, collegato a più utenti (centinaia, migliaia).

• Solitamente la comunicazione è un messaggio che l’utente, client, invia al server affinché esso esegua un certo lavoro (ricerca l’informazione). La macchina server esegue il lavoro e invia la risposta al client che la utilizza (visualizza l’informazione).

• Un server Web è un servizio attivo su un calcolatore (server) che si occupa di fornire all’utente un qualsiasi tipo di file, in particolare pagine Web.

Software delle reti

Software delle reti

• Con architetture di reti sempre più complesse si è reso necessario un software di gestione della rete.

• Le reti sono organizzate a livelli (strati) secondo dei modelli di riferimento (OSI e TCP/IP).

• Ogni rete si distingue per il numero dei livelli, nome e funzionalità diverse per ogni livello.

Ogni livello fornisce un servizio al livello immediatamente superiore.

Software delle reti

• Supponiamo di dover scambiare informazioni tra due host e di avere una architettura con 4 livelli.

• La comunicazione tra le due macchine avviene a parità di livello; le regole per attuare tali conversazioni si chiamano protocolli; c’è un protocollo per ogni livello.

I protocolli

Mezzo fisico Livello 1

Livello 4 Livello 3 Livello 2

Livello 1 Livello 2 Livello 3 Livello 4

Host 1 Host 2

protocollo di livello 1 interfaccia

livello 1/2

protocollo di livello 4

I protocolli

• Lo scambio di informazioni reale tra l’host1 e l’host2 non avviene direttamente e nemmeno tra entità allo stesso livello, bensì l’informazione viene passata al livello inferioree da questo a quello ancora inferiore (4-3-2-1), realmente trasmessa dal livello fisico e poi passata al primo livello e da questo a quello superiore attraversando i vari livelli (1-2-3-4).

I protocolli

• Accade una cosa analoga quando un mittente a spedisce una lettera da un punto pa, della città Ca e dello stato Sa ad un destinatario b ad un punto pb di una città Cbdello stato Sb:

• cassetta della posta, raccolta del postino, smistamento all’ufficio postale pa

• mezzo fisicotreno, aereo (città, Stato)

• ufficio postale pb, consegna del postino, cassetta delle lettere.

I protocolli

• Il mittente a scrive la lettera al destinatario bcon le sue regole di scrittura (protocollo), gli uffici postali pa e pb comunicano tra loro utilizzando convenzioni (protocolli) come timbri, francobolli, …, gli incaricati del servizio postale del treno prelevano dalla città Ca pacchi, sacchi di posta cartacea dagli addetti dell’ufficio postale e consegnano agli addetti dell’ufficio postale della città Cb, firmano ricevute di consegna (protocolli).

I protocolli

• La comunicazione tra due livelli consecutivi avviene tramite un’interfaccia che definisce quali servizi il livello inferiore fornisce a quello superiore.

• Questo permette di sostituire facilmente un’implementazione con un’altra perché basta che si mantenuto il servizio: ad esempio una comunicazione che prima avveniva tramite linea telefonica può essere trasmessa per via satellitare.

I modelli di riferimento

I modelli di riferimento

• Le principali architetture di reti sono i modelli di riferimento ISO-OSI e TCP/IP.

• Modello ISO-OSI (International Standard Organization – Open System Interconnection).

• È un sistema aperto alla comunicazione con altri sistemi che segue uno standard internazionale.

• Esso è composto da sette livelli:

• livello fisico: trasmissione dei bit lungo un canale di comunicazione.

I modelli di riferimento

• livello data link: i dati sono decomposti in pacchetti, spediti in sequenza e si attende un messaggio di ricezione del pacchetto; in caso di errore il pacchetto può essere rispedito

• livello di rete: si deve stabilire quale cammino deve essere scelto nella sottorete e gestire gli eventuali problemi che possono sorgere per la congestione della rete, o nella comunicazione tra reti diverse.

I modelli di riferimento

• livello di trasporto: vengono accettati i dati dal livello superiore e passati al livello di rete;

a volte può essere utile far condividere lo stesso canale a più messaggi e perciò è fondamentale un controllo del flusso delle informazioni

• livello di sessione: può essere un collegamento ad un sistema remoto o un trasferimento di archivi; si effettua un controllo sul dialogo (trasferimento in un’unica direzione o in entrambe), e la sincronizzazione (gestione di una interruzione nel trasferimento dei dati)

I modelli di riferimento

• livello di presentazione: riguarda la codifica delle informazioni trasmesse (stringhe, numeri) che possono avere diverse codifiche (ASCII, Unicode) e che devono essere rappresentati in maniera uniforme nella rete

• livello di applicazione: utilizzo di vari tipi di terminali con una diversa gestione dello schermo, diversi tipi di file system per la gestione dei file, delle directory, gestione remota di processi, …

I modelli di riferimento

• Ogni livello è programmato come se la comunicazione avvenisse con la sua entità pari (allo stesso livello) anche se, invece, l’informazione viene passata al livello inferiore: è analogo a quanto succede quando, in un’assemblea con persone che parlano lingue diverse, l’oratore crede di parlare ai suoi ascoltatori, mentre in realtà egli parla all’interprete.

I modelli di riferimento

• Il modello OSI era quello adottato per Arpanet e i primi collegamenti avvenivano tramite linee telefoniche; ma presto si aggiunsero collegamenti via radio e satellitari, c’era inoltre la necessità di far funzionare la comunicazione anche in caso di guasti di macchine intermedie, e di trasferire non solo archivi ma anche suoni e immagini, perciò i protocolli dovettero essere cambiati.

• L’architettura cambiò e si costruì un nuovo modello.

I modelli di riferimento

• Il nuovo modello di riferimento TCP/IP (Transmission Control Protocol / Internet Protocol) (1974).

• Il modello ha quattro livelli:

• livello Host-rete: i pacchetti vengono inviati lungo la rete

• livello internet: l’informazione è suddivisa in pacchetti che possono essere inviati in maniera indipendente e giungere in ordine diverso; si definisce un protocollo IP tramite il quale si

“consegnano” i pacchetti dove devono andare.

I modelli di riferimento

• livello di trasporto: ci sono due protocolli; il primo TCP controlla che la trasmissione delle sequenze di byte avvengano senza errori, UDP (User Datagram Protocol) viene utilizzato per le trasmissioni veloci

• livello delle applicazioni: esso contiene tutti i protocolli di alto livello tra cui ftp (per il trasferimento di archivi), DNS (per la gestione di nomi da associare agli indirizzi di rete), pop e imap (per scaricare la posta), smtp (per spedire), http (per le applicazioni del web);

I modelli di riferimento

• Un altro protocollo è Telnet (che rappresenta un terminale virtuale con cui si può lavorare in remoto) e che ora è stato sostituito dal protocollo SSH (Secure SHell).

• Ad esempio:

ssh laura nomeserver.adt.unipd.it (chiede una password per poter accedere alla propria home)

Domain Name System

• Il Domain Name System è un protocollo utilizzato per convertire il nome di un host (nome simbolico più facile da ricordare) in un indirizzo IP (risoluzione) e viceversa, convertire un indirizzo IP (32 bit) in un nome di dominio (risoluzione inversa).

• Un nome di dominio è composto da gruppi di stringhe separate da punti: math.unipd.it . La parte principale del nome è la stringa di destra, ad esempio .it .org e si chiama dominio di primo livello. Quando il nome è costituito da due parti si parla di dominio di secondo livello: unipd.it .

Internet e il web

Internet e il Web

• Internet è una rete di calcolatori mondiale ad accesso pubblico che rappresenta attualmente uno dei principali mezzi di comunicazione di massa o mass medium (“mass media”).

• La locuzione “mass media” è l’unione del termine inglese “mass” con la parola latina “media”, plurale di “medium” (sia medium che media pertanto vanno correttamente pronunciati all’italiana). Medium corrisponde a “mezzo” con il suo doppio significato.

Internet e il Web

• Il World Wide Web, più spesso abbreviato in Web e indicato con la sigla www e detto anche

“Ragnatela Mondiale”, è un servizio di Internet e consiste in un insieme vastissimo di documenti multimediali e di servizi accessibili a tutti gli utenti di Internet.

• Le informazioni contenute nei vari server Web diventano accessibili tramite applicazioni, chiamate browser, che solitamente utilizzano il protocollo HTTP (Hyper Testual Transfer Protocol).

Internet e il Web

• Quando l’utente indica l’indirizzo numerico o simbolico, il browser visualizza una pagina Web; questa in realtà è un insieme di testi, immagini, ed anche filmati sonori, a cui si accede cliccando con il mouse su punti della pagina che appaiono “attivi”.

• Ad ogni pagina sono collegate, attraverso dei collegamenti, detti link, altri documenti che possono risiedere sullo stesso server, ma anche su server diversi. Questo passare da una pagina ad un’altra permette di “navigare” nel Web.

Internet e il Web

• Un insieme di pagine collegate e relative ad un argomento comune si chiama sito Web;

l’indirizzo di tale sito, ad esempio http://www.studenti.math.unipd.it o il corrispondente indirizzo numerico 147.162.84.215) viene chiamato URL (Uniform Resource Locator).

Il motore di ricerca Google

Google: il problema del page ranking

• Due studenti dell’Università di Stanford, Sergey Brin e Larry Page, hanno dato vita a Google nel 1998, uno dei più importanti motori di ricerca nel Web.

• La parola google deriva da googol, termine

“inventato” da Milton Sirotta nel 1938 (all’epoca ragazzino e nipote di un matematico), per indicare un numero seguito da 100 cifre zero.

• L’azienda che gestisce tale motore di ricerca ha utilizzato questo nome per la vastità di informazioni trattate.

Google: il problema del page ranking

• Uno dei problemi era:

• come ordinare le pagine presenti sul web in base alla loro importanza? come definire l’importanza?

• I due fondatori si ispirarono all’algoritmo HyperSearch dell’italiano prof. Massimo Marchiori, che all’epoca era ricercatore negli USA e che attualmente insegna al Dipartimento Matematica Pura ed Applicata dell’Università di Padova.

Google: il problema del page ranking

• Si possono scegliere varie possibilità:

• il numero di volte che una parola viene cercata

• il numero di link che partono o arrivano a quella parola

• il numero delle pagine importanti che partono o arrivano alla pagina.

Google: il problema del page ranking

• L’idea di Page e Brin era che una pagina ha una sua importanza che deriva dalle sue connessioni(piuttosto che dal suo contenuto).

• L’importanza di una pagina si trasferisce in parti uguali alle pagine che essa punta (una persona importante dà importanza alle persone che frequenta).

• L’importanza di una pagina è data dalla somma dell’importanza che viene dalle pagine che puntano ad essa (una persona è importante se frequenta molte persone importanti).

Google: il problema del page ranking

• Vediamo il modello matematico.

• Supponiamo che siano n le pagine del web, e definiamo la matrice seguente:

h₁₁ h₁₂ h_1n h₂₁ h₂₂ h_2n H = . . . . . .

h_n1 h_n2 h_nn

1 se c’è un link dalla pagina i alla pagina j con hij =

0 altrimenti

Google: il problema del page ranking

• Esempio. Sia n = 4 e sia H la seguente matrice:

0 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0

• Sommando i valori sulla riga i-esima si trova il numero di link che partono dalla pagina i: r_i

• Sommando i valori sulla colonna j si trova il numero di pagine che puntano alla pagina i: c_j.

Google: il problema del page ranking

• Indichiamo ora con x_jl’importanza della pagina j; risulta:

x_j= h_1jx₁/r₁ + h_2jx₂/r₂+ … + h_njx_n/r_n per j = 1, 2, 3, …, n

• Questo è un sistema lineare in n equazioni ed n incognite. Le soluzioni x₁, x₂, …, x_n forniscono il livello di importanza delle n pagine: page rank.

• L’equazione usata in Google è un po’ diversa, perché

“pesata” con un parametro e le soluzioni che derivano sono tutti valori compresi tra 0 e 1.

Google: il problema del page ranking

• Le pagine attive (odierne) sono oltre n= 8.5 ××××10⁹

• Un sistema lineare con la regola di Cramer si risolve con un numero di operazioni dell’ordine di n!.

• Il metodo di eliminazione di Gauss risolve il sistema con circa 2n³/3operazioni.

• Se usassimo quest’ultimo avremmo un numero di operazioni dell’ordine di:

2/3 ×××× (8.5 10⁹)³ ~4.1 ×××× 10²⁹

(miliardi di miliardi di miliardi) di operazioni aritmetiche.

Google: il problema del page ranking

• Uno dei calcolatori più veloci al mondo è attualmente il Blue Gene dell’IBM.

• Ha una velocità di circa 478 teraflops:

4.78××××10¹⁴operazioni al secondo (1 tera = 1000 giga)

• Per eseguire 4.1××××10²⁹ operazioni impiegherebbe più di 27 milioni di anni.

• Come può essere se Page e Brin calcolano il page rank ogni mese?

• Anche un calcolatore mille volte più veloce non risolverebbe il problema.

Google: il problema del page ranking

• Esistono metodi numerici (metodi che costruiscono soluzioni approssimate che possono essere implementate sul calcolatore) con i quali si riesce a risolvere il sistema lineare, in tempi più brevi.

• Si parte da una ipotetica soluzione, si stima un errore e in maniera iterativa la si migliora; si costruisce così una successione che converge indipendentemente dalla approssimazione iniziale:

x_j⁽¹⁾, x_j⁽²⁾ , x_j⁽³⁾, …. x_j

con un errore di approssimazione che risulta essere:

e^(k)≤ λ^k dove λ (0 < λ < 1) è il modulo del secondo autovalore più grande di una certa matrice.

Google: il problema del page ranking

• L’algoritmo è molto più efficiente: il numero di prodotti e di somme dipende dal numero di 0 della matrice H, che solitamente sono molti (la matrice è sparsa); se ci fossero circa 50 elementi non nulli su una riga, l’algoritmo implementato sul calcolatore impiegherebbe pochi secondi per trovare la soluzione.

• Questo è il metodo adottato in Google.

HTML

HTML

• Un sito Web è costituito da più pagine (testo, immagini, video) collegate tra loro; volendo costruire un sito per prima cosa occorre pianificarne la struttura (Laganà, Righi, Romani Cap.11)

• Uno dei linguaggi per la costruzione di siti

Web è HTML (HyperText Markup

Language).

• Il file che contiene il testo scritto in questo linguaggio ha estensione .htm o .html

HTML

• Caratteristica del linguaggio è l’uso di tag, parole chiave che indicano l’operazione che deve essere eseguita sulla stringa che racchiudono.

• I tag sono racchiusi tra parentesi angolari;

ognuno ha il suo corrispondente di chiusura composto dal tag stesso preceduto dal simbolo /.

HTML

• Ogni documento HTML inizia e termina con la seguente coppia di tag:

<HTML>

…..

</HTML>

• Alcuni tag indicano l’inizio di una nuova riga

<BR> (andare a capo) o di un paragrafo <P>

(andare a capo e lasciare una riga bianca) e non hanno necessariamente il tag di chiusura.

HTML

• Solitamente un documento è suddiviso in una sezione di testa:

<HEAD> </HEAD>

e un corpo:

<BODY> </BODY>

• Nella sezione di testa si può inserire un titolo che il browser (Mozilla, Explorer, …) assegnerà al documento:

<TITLE> </TITLE>

HTML

• Alcuni tag di uso frequente:

<CENTER> testo </CENTER >

• scrive il testo nella zona centrale della finestra

<LI> … </LI>

• introduce un simbolo (un pallino o un numero) per rappresentare un elenco (non ordinato o ordinato); il tag per l’elenco ordinato è <OL>

per quello non ordinato <UL> con i rispettivi tagdi chiusura.

HTML

<B> … </B>

• grassetto

• Per introdurre caratteri speciali si deve scrivere una codifica preceduta dal simbolo &

&gt > (parentesi del tag)

&lt <

&egrave è

&Egrave È

&amp &

HTML

• Si possono costruire dei livelli di intestazione con dimensione di caratteri che diminuisce:

<H1> … </H1>

<H2> … </H2>

<H3> … </H3>

fino a 6 livelli.

• Si possono introdurre immagini

<IMG SRC="nomefile.jpeg">

HTML

• Collegamenti ad altre pagine. Il tag di riferimento è

<A HREF=" posizione pagina">

visualizzazione del link </A>

• Per una pagina esterna si deve fornire l’indirizzo completo, ad esempio http://www.nomedelsito

• Per una pagina locale, solo il nome del file.

• Vediamo un esempio.

HTML

<HTML>

<HEAD>

<TITLE>Pagina personale di Mario Rossi </TITLE>

</HEAD>

<BODY>

<H1>

<IMG SRC="bandiera.jpeg">

HTML

<B><CENTER><FONT COLOR = fuchsia> MARIO ROSSI

</FONT> </CENTER></B></H1>

<H2>

<B><CENTER><FONT

COLOR=green>futuro studente di ingegneria</FONT> </CENTER></B>

</h2>

<P><BR>

<HR><BR>

HTML

<B> Nome:</B> Mario Rossi (nato a ...., il 1 gennaio

2011)<BR>

<B>Indirizzo:</B> Via ...

<BR>

<B>Città :</B> da definire <BR>

HTML

<B>e-mail (per ora in

"prestito" ):</B>

<A HREF="mailto:

laurap@math.unipd.it">

laurap@math.unipd.it

</A>

<BR>

<HR>

<LI>

HTML

<B><A HREF=

"http://www.math.unipd.it/

~laurap/didattica/

Informatica-EN-0910/">

Corso di Informatica </A>

per Ingegneria dell'Energia

</B>

</LI>

<BR>

<HR>

<P>

HTML

<P>

<LI>

<A HREF="pagina2.html">

<B>IMMAGINE</B></A>

</LI>

</BODY>

</HTML>

Riepilogo TDA e strutture di dati

TDA

• Un Tipo di Dato Astratto è:

• un insieme di elementi chiamato dominio del tipo di dato

• caratterizzato da un nome

• possiede delle funzioni che operano sul dominio

• operatori, predicati, operatori di creazione

• può avere delle costanti che lo caratterizzano

TDA

• Nel linguaggio Java i TDA :

• si definiscono in una interfaccia che dichiara quali sono le funzioni che operano sul dominio (cosa fa il TDA)

• si realizzano in una classe che definisce la struttura di dati e le funzioni che operano su di essa (come agisce il TDA).

TDA

• I seguenti TDA sono contenitori di informazioni caratterizzati dalle loro diverse funzioni :

• Pila o Stack

• Coda o Queue

• Lista

• Dizionario e Tavola

TDA

• Questi TDA estendono l’interfaccia GenericContainer, un contenitore generico che rappresenta una proprietà generale comune a tutti i contenitori:

• un contenitore può essere vuoto (costante)

• un contenitore viene inizializzato come contenitore vuoto

Strutture di dati

• Una struttura di dati è un modo di organizzarei dati in un contenitore ed ha una sua propria modalità di accesso. Sono state viste le seguenti strutture:

• array(riempito in parte)

• ordinato

• non ordinato

• lista concatenata.

Strutture di dati

• L’accesso agli elementi dell’array è casuale, vale a dire arbitrario, non prestabilito. Poiché l’array ha dimensione fissa, si è utilizzata la tecnica del raddoppio (riassegnando il riferimento) per rappresentare sequenze di lunghezza arbitraria.

• L’accesso agli elementi di una lista concatenataè sequenziale.

Strutture di dati

Array Lista concatenata

accesso diretto sequenziale

successivo i+1 a.next

dimensione massima sì* no

spazio info info e next

spostamento dati sì no

(inserire e cancellare) (* senza raddoppio)

Pila o Stack (Last In First Out)

• Le operazioni coinvolgono solo il primo elemento della Pila. Il TDA viene descritto nella seguente interfaccia:

public interface Stack { boolean isEmpty();

void push(Object x);

void pop(); //oppure Object pop();

Object top();

}

Pila o Stack (Last In First Out)

• Complessità delle funzioni

push pop top

array O(1) O(1) O(1)

(in media*)

lista O(1) O(1) O(1)

concatenata

(* raddoppio)

Coda o Queue (First In First Out)

• Le operazioni coinvolgono il primo elemento e l’ultimo elemento della Coda. Il TDA viene descritto nella seguente interfaccia:

public interface Queue{

boolean isEmpty();

void enqueue(Object x);

void dequeue(); //oppure Object dequeue();

Object front();

}

Coda Queue (First In First Out)

• Complessitàdelle funzioni

enqueue dequeue front

array O(1) O(1) O(1)

(circolare) (in media*)

lista O(1) O(1) O(1)

concatenata

(* raddoppio)

Dizionario o Dictionary

• È costituito da coppie (chiave, attributo); la chiave è unica e deve permettere il confronto.

Il TDA viene descritto nella seguente interfaccia:

public interface Dictionary{

boolean isEmpty();

void insert(Comparable chiave, Object x);

Object find(Comparable chiave);

void remove(Comparable chiave);

}

Dizionario o Dictionary

• Complessitàdelle funzioni:

insert * find remove

array O(1) O(n) O(n)

(non ordinato) (in media)

array O(n) O(log₂n) O(n) (ordinato)

lista O(1) O(n) O(n)

concatenata

(*senza la ricerca per l’unicità della chiave che è O(n) o O(log₂n))

Tavola o Table

• È un dizionario a chiave intera. Il TDA viene descritto nella seguente interfaccia:

public interface Tavola{

boolean isEmpty();

void insert(int chiave, Object x);

Object find(int chiave);

void remove(int chiave);

}

• Nell’implementazione su array, se la chiave coincide con l’indice, la ricerca è O(1).

Tavola Hash

• È un dizionario in cui si esegue una trasformazione della chiave allo scopo di ottimizzarne la memorizzazione e la successiva ricerca:

posizione = h(chiave)

• h : resto della divisione intera chiave/dim

• dim : dimensione della tavola

Tavola Hash

• Si utilizzano assieme le due strutture dati costruendo un array di liste concatenate (bucket).

• Se le chiavi sono n e le liste hanno la stessa lunghezza, le prestazioni sono O(n/dim).

Java

Java

• Un algoritmo rappresenta l’astrazione della realtà.

• Un linguaggio di programmazione rappresenta l’astrazione del processore.

• La variabile e il tipo della variabile rappresentano l’astrazione della locazione di memoria e delle operazioni sulla variabile.

Java

• Un Tipo di Dato Astratto (nuovo concetto) è un tipo di dato che può essere definito dall’utente, che descrive sia l’insieme degli elementi del TDA (campi, forma) sia il comportamento del TDA (metodi, proprietà).

• I linguaggi orientati agli oggetti permettono la costruzione di TDA.

• Il linguaggio Java è un linguaggio di programmazione ad alto livello orientato agli oggetti.

Java : compilatore e interprete

• Il linguaggio Java è dotato di un compilatore che traduce il codice sorgente in un codice binario, detto bytecode, e di un interprete, Java Virtual Machine, che elabora ed esegue il bytecode.

• Il compilatore, durante la traduzione in codice macchina, esegue una analisi lessicale, sintatticae semantica.

Java Virtual Machine

• La macchina virtuale Java (JVM) è un interprete che carica in memoria il bytecode, esegue gli agganci con le classi delle librerie standard (già compilate), interpreta ed esegue il bytecode.

• Si hanno così efficienza (compilatore) e portabilità, non solo a livello di codice sorgente, ma anche a livello di bytecode.

Programma Java

• Un programma Java è composto da una o più unità compilabili: classi contenute in file di estensione .java .

• Ogni file sorgente può contenere una sola classecon accesso pubblico il cui nome deve coinciderecon quello del file che la contiene.

• Il file in uscita dal compilatore ha estensione .class

Alfabeto

• L'alfabeto del linguaggio è UNICODE, a 16 bit.

• I primi 128 caratteri costituiscono il codice ASCII.

• Si distinguono le lettere minuscole dalle maiuscole.

• Lo spazio è un separatore.

• Le parole chiave (parole che hanno un particolare significato per il linguaggio) sono riservate, ossia non si possono usare come nomi di identificatori.

Token

• Le unità lessicali (token) con cui si costruiscono le frasi del linguaggio sono:

identificatori parole chiave costanti separatori operatori

• Parole chiave, costanti, separatori e operatori sono costruiti con i simboli del codice ASCII.

Tipi di dato in Java

• I tipi di dato sono:

• tipi base (primitivi, predefiniti):

• numeri, caratteri, valori logici

• riferimenti a oggetti

• Le variabili associate a questi tipi sono memorizzate in una parte della memoria detta Stack.

Tipo Intero

• A seconda dell’occupazione in byte si hanno i seguenti tipi:

byte (1), short (2), int (4), long (8)

• Degli n bit a disposizione, il primo è il bit del segno

0 positivi 1 negativi

• I rimanenti n-1 sono per il numero.

Tipo Intero

• Si possono rappresentare 2^{n -1} valori diversi.

• Costanti del tipo di dato: - 2^{n -1} e 2^{n -1}-1 che delimitano l’intervallo di rappresentazione.

In Java:

• Byte.MIN_VALUE Byte.MAX_VALUE

• Short.MIN_VALUE Short.MAX_VALUE

• Integer.MIN_VALUE Integer.MAX_VALUE

• Long.MIN_VALUE Long.MAX_VALUE

Tipo Intero

• Dato x, per trovare la sua rappresentazione r(x) in base b (b=2) si divide per la base e si prendono i resti.

• La rappresentazione dell'opposto r(-x) è definita in complemento a 2

r(x) + r(-x) = 2ⁿ

• Per trovare la rappresentazione dell’opposto si invertono tutti i bit di r(x) fatta eccezione degli 0 a destra e del primo 1 a destra (oppure: si invertono tutti i bit e si aggiunge 1).

Tipo Reale

• A seconda dell’occupazione in byte si hanno i seguenti tipi: float (4), double (8).

• Dati n bit a disposizione il primo è il bit del segno

0 positivi 1 negativi

• Dei rimanenti n-1 bit si ha una ripartizione tra esponentee mantissa.

Mantissa

• I numeri reali sono rappresentati in modulo e segno, riferiti alla base 2, con mantissa normalizzatae bit nascosto.

• Dato x per costruire la rappresentazione r(x) si deve trasformare in binario il numero reale:

parte intera: si divide per la base e si prendono i resti

parte frazionaria: si moltiplica per la base e si prendono e parti intere

Mantissa

• Si deve poi portare il numero binario in forma normalizzata

1.c₁c₂c₃.... ×××× 2^e

• L’esponente e viene rappresentato con l’eccesso (in traslazione) vale a dire che e deve essere aumentato, di 127 per i float (eccesso).

Il nuovo esponente (intero) viene trasformato in binario.

Esponente

• Costanti del tipo di dato

minimo reale ≠ 0 float ~ 10 ^-38 (*) massimo reale float ~ 10 ³⁸ (* con mantissa non normalizzata 10 ^-45)

• In Java

Float.MIN_VALUE Float.MAX_VALUE Double.MIN_VALUE Double.MAX_VALUE

Classi e oggetti

• Java è un linguaggio orientato agli oggetti, basato su classi.

• Per costruire un nuovo concetto dobbiamo definire la sua forma (campi) e le sue proprietà (metodi).

• La classe ci permette di descrivere il nuovo concetto, con la definizione di campi e metodi.

• Per poter utilizzare il concetto si deve creare un oggettodel tipo della classe.

Classi e oggetti

• Un oggetto è una entità che può essere usata attraverso i metodi della classe.

• L’oggetto creato si chiama anche esemplare della classe o istanza della classe.

• Per creare un oggetto si usa l’operatore new.

• La variabile oggetto, il cui tipo è nomeclasse, dopo l’attivazione dell’operazione new, contiene il riferimento all’oggetto creato (informazioni sulla posizione di memoria dell’oggetto creato).

Campi

• Gli oggetti stanno in una parte della memoria detta Heap.

• All’interno di una classe sono definiti campi e metodi.

• I campi di una classe, chiamati anche campi di esemplare o variabili di istanza; solitamente sono dichiarati con accesso privato:

incapsulamentoo protezione dei dati.

• Con l’incapsulamento, solo i metodi della classe possono accedere ai campi.

Interfaccia pubblica

• Nella classe viene definita una interfaccia pubblica costituita dall’insieme dei metodi pubbliciche permettono di utilizzare l’oggetto dall’esterno.

• All’interfaccia pubblica appartiene anche il costruttore, che inizializza l’oggetto al momento della sua creazione.

• Astrazione: all’utente esterno è noto solo il nome del metodo e il suo comportamento; si usa l’oggetto senza conoscere la realizzazione dei suoi metodi.

Tempo di vita e inizializzazione delle variabili in una classe

All’interno di una classe ci sono:

• variabili di istanza (campi)

• variabili locali

• variabili parametro

• Queste variabili hanno un diverso tempo di vitae diverse modalità di inizializzazione.

Variabile di istanza

• Una variabile di istanza:

• appartieneall’oggetto

• è visibile ai metodi della sua classe

• viene inizializzata da un costruttore (default, esplicitamente)

• viene creata, “nasce”, quando l’oggetto viene creato

• viene eliminata, “muore”, quando l’oggetto viene eliminato, ossia non è più referenziato(garbage collector)

Variabile locale

Una variabile locale:

• appartienea un metodo

• è visibile all’interno del metodo

• deve essere inizializzata esplicitamente

• viene creata, “nasce”, quando viene eseguito l’enunciato in cui è definita

• viene eliminata, “muore”, quando l’esecuzione del programma esce dal blocco nel quale è stata definita (che può anche essere

il metodo che l’ha definita)

Variabile parametro

Una variabile parametro (formale):

• appartienea un metodo

• è visibile all’interno del metodo

• viene inizializzata all’atto della invocazione del metodo (con il valore fornito dall'invocazione)

• viene creata, “nasce”, quando viene invocato il metodo

• viene eliminata, “muore”, quando l’esecuzione del metodo termina

Variabile statica

• Una variabile statica viene creata quando la JVM carica la classe per la prima volta ed eliminata quando la classe viene scaricata (si dice che “esiste sempre”).

• Si chiama anche variabile di classe perché non appartiene ad un oggetto ma è di tutta la classe (ce n’è un’unica copia).

• Viene inizializzata esplicitamente o con il default (non nel costruttore).

Specificatore di accesso

• Campi, metodi e classi hanno uno specificatore di accesso che può essere:

• private: visibilità solo all’interno della classe

• public: visibilità al di fuori della classe

• protected: visibilità ai metodi della classe, delle sue sottoclassi e delle classi dello stesso pacchetto

• nessuna specifica: visibilità di pacchetto

Ereditarietà

• È un meccanismo che consente di costruire una nuova classe che estende le funzionalità di un’altra classe: si possono utilizzare metodi e variabili di istanza della classe superiore, senzaaccedere (conoscere) al codice dell’altra classe (riusabilità del codice).

• Ogni classe deriva direttamente o non dalla superclasseuniversale Object.

Metodi nella sottoclasse

Un metodo della sottoclasse può:

• essere un nuovo metodo non presente nella superclasse

• essere un metodo ereditato dalla superclasse

• essere un metodo della superclasse sovrascrittonella sottoclasse

Cast: conversione forzata

• Tipi base.

• Si può eseguire l’assegnazione di una variabile di un tipo superiore ad una di tipo inferiore:

vartipoinf = (tipo inferiore)vartiposup

• L’assegnazione inversa è automatica.

Cast: conversione forzata

• Riferimenti.

• Si può eseguire l’assegnazione di un riferimento di un oggetto di tipo superclasse ad un riferimento di tipo sottoclasse:

tiposottoclasse = (sottoclasse)tiposuperclasse

• L’assegnazione inversa è automatica.

Polimorfismo

• È la proprietà in base alla quale il comportamento di un metodo può variare in relazione al tipo dell’oggetto che viene effettivamente usatocome parametro implicito del metodo.

• È la JVM che decide durante l’esecuzione quale metodo deve essere scelto: selezione posticipata.

• Si parla di sovraccarico quando è il compilatore che decide quale metodo dovrà essere invocato: selezione anticipata.

Interfaccia

• Rappresenta una proprietà astratta.

• Possiede solo le firme dei metodi.

• I suoi metodi sono automaticamente pubblici.

• Una classe che realizza un’interfaccia deve implementare tuttii suoi metodi.

• Quando più classi realizzano l’interfaccia si ha polimorfismo(ad esempio: nei TDA realizzati su array e lista concatenata, Comparable, . . .).

Eccezioni

• Sono situazioni di possibili errori che possono essere esterne al problema o dipendere da un cattivo utilizzo dell’algoritmo.

• Le situazioni di errore devono essere previste e gestite.

• Le eccezioni sono oggetti: la classe dell’eccezione può estendere Exception (a controllo obbligatorio) o RuntimeException.

• Le eccezioni possono essere catturate e si eseguono istruzioni alternative, oppure lanciate ed interrompono l’esecuzione del programma.

Memoria centrale: Stack e Heap

• Rappresentano parti diverse della memoria: Stack (tipi base e riferimenti), Heap (oggetti, il garbage collector mette in coda le aree liberate).

• Schema della disposizione degli indirizzi di memoria:

indirizzi di memoria crescenti

lunghezza cresce verso → ← cresce verso fissa la memoria alta la memoria bassa

Codice di programma

Java RuntimeStack

Memoria

libera Heap

Memoria centrale: Stack e Heap

• La memoria centrale è pertanto divisa in tre aree distinte o segmenti:

• il segmento statico che contiene il codice del programma e le costanti,

• lo Stack (run time stack) utilizzato per l’allocazione delle variabili locali create all’interno di un blocco al momento della sua attivazione,

• il segmento dinamico o Heap utilizzato per contenere gli oggetti creati dinamicamente e soggetto a garbage collection.

Algoritmi

Algoritmi

• Un algoritmo (deterministico) è un procedimento di soluzione costituito da un insieme di operazioni eseguibili tale che: esiste una prima operazione, dopo ogni operazione è individuata la successiva, esiste un’ultima operazione.

• La risoluzione avviene in due passi:

• analisi, definizione del problema e progettazione

• codifica, trasformazione in un linguaggio di programmazione

Strutture di controllo

• Con le seguenti strutture di controllo si può scrivere qualsiasi algoritmo:

• sequenza

• alternativa

• ciclo

• Queste strutture sono caratterizzate dall’avere un unico punto di ingresso e un unico punto di uscita.

Iterazione e Ricorsione

• La scomposizione in sottoproblemi può essere:

• iterativa:

• i sottoproblemi sono simili tra loro

• ricorsiva:

• almeno uno dei sottoproblemi è simile a quello iniziale, ma di dimensione inferiore

• In entrambe le scomposizioni si pone il problema della terminazione.

Divide et impera

• È una strategia generale per impostare algoritmi:

• suddividere l’insieme dei dati in un numero finito di sottoinsiemi sui quali si può operare ricorsivamente.

• Se la suddivisione in sottoinsiemi è bilanciata (sottoinsiemi di uguale dimensione) si ottengono algoritmi efficienti.

Complessità

• L’efficienza di un algoritmo si valuta in base all’utilizzo che esso fa delle risorse di calcolo:

memoria (spazio), CPU (tempo).

• Il tempo che un algoritmo impiega per risolvere un problema è una funzione crescente della dimensione n dei dati del problema (dimensione o taglia).

Complessità

• Se la dimensione varia, il tempo può essere stimato in maniera indipendente dal linguaggio, dal calcolatore e dalla scelta di dati, considerando il numero di operazioni eseguitedall’algoritmo.

• Per valutare il tempo vero dovremmo conoscere il tempo necessario per l’esecuzione di ogni singola istruzione: il numero di istruzioni macchina corrispondente ad una istruzione nel linguaggio ad alto livello dipende dal compilatore impiegato.