Università degli Studi di Roma – Tor Vergata
Facoltà di Ingegneria – Corso di Laurea in Ingegneria Medica
Algoritmi Algoritmi
Rev.1.0 of 2012-04-26
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 2 of XX _
Classi di problemi Problemi
Risolvibili
Non Risolvibili
Non si conosce il metodo per ottenere la soluzione oppure le soluzioni sono infinite
Trattabili
Hanno una soluzione certa raggiungibile
Intrattabili
Hanno una soluzione certa ma irraggiungibile Deve essere definito Il livello di approssimazione
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 3 of XX _
Strategie di risoluzione dei problemi
Tecniche top-down
E’ una tecnica che partendo dalla formulazione del problema (progetto) lo decompone successivamente in
parti sempre più dettagliate per definirne in modo sempre più preciso
le modalità di risoluzione
Tecniche botton-up
E una tecnica che viene intrapresa quando si hanno a
disposizione delle parti già progettate che si vogliono utilizzare e/o riadattare su un nuovo progetto tipicamente nella
programmazione ad oggetti oppure quando sia necessario effettuare delle prove di validazione su elementi di base prima di procedere con il progetto completo
Livello 4 Livello 2 Livello 1
Livello 3
BOTTON UP
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 4 of XX _
Risoluzione Top-Down
Formulazione generale del problema
Sottoproblema 1 Sottoproblema 2 Sottoproblema 3
Risoluzione
elementare Sottoproblema 2.1
Risoluzione elementare
Sottoproblema 2.2 Sottoproblema 3.1
Sottoproblema 3.1.1
Risoluzione elementare Risoluzione elementare
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 5 of XX _
Risoluzione Top-Down
Sistema Archivio dati elettrocardiografici
paziente
Progettazione Sistemi da acquisizione
Progettazione
interfaccia utente Elaborazione dati
Definizione segnale d’ingresso e del convertitore A/D
Interfaccia settaggio
Software settaggio parametri registrazione
Interfaccia grafica visione linea dati elaborati
Routine di calcolo
Lista singole routine Software di gestione
grafica
Progettazione Salvataggio dati
Rilettura dati
Algoritmi di compressione
Software di gestione DAC Comunicazione
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 6 of XX _
Risoluzione Top-Down
Realizzazione di un dispositivo per Laser terapia
Definizione delle specifiche Individuazione normative applicabili
Progettazione Elettronica (sicurezze elettriche, ottiche)
come da standard
Progettazione Software (analisi dei moduli e supervisore)
Progettazione Contenitore (design, usabilità)
Progettazione Sistema emissione
Progettazione Sistemi controllo
Progettazione interfaccia uomo macchina
Progettazione software Rilevazione dati Elaborazione dati
Progettazione Componenti meccaniche
Progettazione Alimentazione (sicurezza elettrica)
Limiti di emissione (Sicurezza del
trattamento)
Progettazione software di interfaccia (Errori umani nell’inserimento dati)
Progettazione moduli Acquisizione Elaborazione Memorizzazione (congruenza dei dati)
Progettazione Assemblaggi (Assistenza tecnica)
Idea
Normative di legge cogenti applicabili standard da prendere in considerazione
Lista delle norme applicabili ANALISI DEI RISCHI
Definizione d’uso Lista delle specifiche terapeutiche Lista delle specifiche fisico-elettriche Non basta
l’idea !!!!
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 7 of XX _
Risoluzione Botton Up
Ho un dispositivo che genera luce laser per altre applicazioni con certe
specifiche
Posso utilizzarlo in un atro ambito ? Per laser terapia per esempio ?
Ho già le schede elettroniche di pilotaggio e controllo cosa devo verificare - adattare
modificare per renderlo conforme ? (sicurezze elettriche, ottiche)
come da standard)
Ho già una interfaccia utente Ho già un contenitore con le componenti elettroniche
Modifiche da apportare all’interfaccia utente
Ho già un sistema software Rilevazione dati
Elaborazione dati Eventuali modifiche
Revisione del software Adattamenti modifiche
Revisione adattamento e modifica per la nuova
applicazione Revisione degli
Assemblaggi
Idea
Normative di legge cogenti applicabili standard da prendere in considerazione
Lista delle norme applicabili ANALISI DEI RISCHI
Definizione d’uso Lista delle specifiche terapeutiche Lista delle specifiche fisico-elettriche Non basta
l’idea !!!!
Università degli Studi di Roma – Tor Vergata
Facoltà di Ingegneria – Corso di Laurea in Ingegneria Medica
Strutture di dati
Strutture di dati
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 9 of XX _
Strutture di dati
Tipicamente le modalità con cui si organizzano i dati (strutture di dati) sono riconducibili a 4
diverse classi di base:
Strutture statiche
Array (Vettori o Matrici) Record
20 24 30 27 23 29
15/06/2010 07/03/2011 20/07/2012 Data esame
27 000159
Luigi Rossi
25 000365
Ermanno Bianchi
28 000425
Giovanni Verdi
Voto Matricola
Studente nome Studente
cognome
dato 1 campo 1
dato 2 campo 2
dato 3 campo 3
dato 4 campo 4
dato 5 campo 5
dato 6 campo 6
dato 7 campo 7
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 10 of XX _
Strutture di dati Strutture dinamiche
Liste (tre identificatori E, t, R L )
E elementi t radice, R
Lrelazioni binarie
Alberi (tre identificatori N, r, R A
N nodi r radice, R
Arelazioni binarie Dato 1 link Dato 2 link ………. link Dato N link
head end
k a
j
p r
b
f h
c d
e
s
radice
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 11 of XX _
Strutture di dati Grafi orientati e non orientati
(due identificatori V, R G)
V vertici o nodi, R
Grelazioni binarie
q r
e
c g b
a
d
Grafo orientato
Nei grafi si rappresentano con :
Liste di adiacenza Matrice di adiacenza Matrice di incidenza
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 12 of XX _
Liste di adiacenza
a b link r link g / /
r / / q link
e link c link
b c link
q / / c link
b link a link
r / / link
g link e link
d link b link
c d link r / /
g / / e link
c link d e link
d / / c link
b link e g link
d / / c link
a link g q link
r / / b link
q r link
q r
e c g b
a
d
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 13 of XX _
Matrice di adiacenza
q r
e
c g b
a
d
r q g e d c b a
r q g e d c b a
0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0
0 0 1 0 0 0 0 0
0 0 1 1 1 0 0 0
1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 Grafo orientato
Matrice di adiacenza Grafo orientato
m
i,j=1 se esiste l’arco orientato i a j m
i,j=0 se non esiste
È una matrice V x V rappresenta la presenya di un arco tra i nodi
Grafo non orientato orientato m
i,j=1 se esiste l’arco i a j o da j ad i m
i,j=0 se non esiste
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 14 of XX _
Matrice dell incidenze
q r
e
c g b
a
d
0 0 0 1 -1 0 0 0 11
0 0 0 1 0 0 -1 0 10
0 0 0 -1 0 1 0 0 9
0 0 0 0 0 -1 1 0 8
0 0 0 0 -1
1 0 0 12
r q g e d c b a
13 7
6 5 4 3 2 1
0 0
0 1 1 -1 0 -1
0 0
0 0 0 0 1 1
-1 -1
-1 0 0 0 0 0
0 0
0 0 0 0 0 0
1 0
0 0 0 0 0 0
0 1
0 0 -1 0 0 0
0 0
0 0 0 1 -1 0
0 0
1 -1 0 0 0 0
Grafo orientato
Matrice di incidenza 6
12 7 4 1 5
2
3
8 9 10
11
13
Grafo orientato
m
i,j=1 se esiste l’arco uscente i a j m
i,j= -1 se esiste l’arco entrante j a i m
i,j= 0 se non esiste arco
È una matrice V x R rappresenta la presenya di un arco tra i nodi
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 15 of XX _
Strutture di dati
q r
e
c g b
a
d
r q g e d c b a
r q g e d c b a
0 1 0 0 0 1 1 1
1 0 0 0 0 0 1 0
0 0 0 0 1 1 0 1
0 0 0 0 1 1 1 0
0 0 1 1 0 1 0 1
1 0 1 1 1 0 1 0
1 1 0 1 0 1 0 0
1 0 1 0 0 0 0 0 Grafo non orientato
Matrice di adiacenza
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 16 of XX _
Grafi ricerca minimo percorso
r q g e d c b a
r q g e d c b a
0 1 0 0 0 1 1 1
1 0 0 0 0 0 1 0
0 0 0 0 1 1 0 1
0 0 0 0 1 1 1 0
0 0 1 1 0 1 0 1
1 0 1 1 1 0 1 0
1 1 0 1 0 1 0 0
1 0 1 0 1 0 0 0
q r
e c g b
a
d
Visite dei percorsi
r q g e d c b a
a
1 0 1 0 1 0 0 0
Si cerca la via con meno nodi che colleghi a ad e
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 17 of XX _
Grafi ricerca minimo percorso
q r
e c g b
a
d
r q g e d c b a
r q g e d c b a
0 1 0 0 0 1 1 1
1 0 0 0 0 0 1 0
0 0 0 0 1 1 0 1
0 0 0 0 1 1 1 0
0 0 1 1 0 1 0 1
1 0 1 1 1 0 1 0
1 1 0 1 0 1 0 0
1 0 1 0 1 0 0 0
0 1 0 0 0 1 1 1 r
r q g e d c b a
a
1 0 1 0 1 0 0 0
Visite dei percorsi
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 18 of XX _
Grafi ricerca minimo percorso
q r
e c g b
a
d
r q g e d c b a
r q g e d c b a
0 1 0 0 0 1 1 1
1 0 0 0 0 0 1 0
0 0 0 0 1 1 0 1
0 0 0 0 1 1 1 0
0 0 1 1 0 1 0 1
1 0 1 1 1 0 1 0
1 1 0 1 0 1 0 0
1 0 1 0 1 0 0 0
1 0 0 0 0 0 1 0 q
0 1 0 0 0 1 1 1 r
r q g e d c b a
a
1 0 1 0 1 0 0 0
Visite dei percorsi
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 19 of XX _
Grafi ricerca minimo percorso
q r
e c g b
a
d
r q g e d c b a
r q g e d c b a
0 1 0 0 0 1 1 1
1 0 0 0 0 0 1 0
0 0 0 0 1 1 0 1
0 0 0 0 1 1 1 0
0 0 1 1 0 1 0 1
1 0 1 1 1 0 1 0
1 1 0 1 0 1 0 0
1 0 1 0 1 0 0 0
1 1 0 1 0 1 0 0 b
1 0 0 0 0 0 1 0 q
0 1 0 0 0 1 1 1 r
r q g e d c b a
a
1 0 1 0 1 0 0 0
Visite dei percorsi
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 20 of XX _
Grafi ricerca minimo percorso
q r
e c g b
a
d
r q g e d c b a
r q g e d c b a
0 1 0 0 0 1 1 1
1 0 0 0 0 0 1 0
0 0 0 0 1 1 0 1
0 0 0 0 1 1 1 0
0 0 1 1 0 1 0 1
1 0 1 1 1 0 1 0
1 1 0 1 0 1 0 0
1 0 1 0 1 0 0 0
0 0 0 0 1 1 1 0 e
1 1 0 1 0 1 0 0 b
1 0 0 0 0 0 1 0 q
0 1 0 0 0 1 1 1 r
r q g e d c b a
a
1 0 1 0 1 0 0 0
Visite dei percorsi
È il percorso minimo ? Non posso dirlo devo provare altri percorsi possibili
Posso calcolare il peso ? Si
Dato che i percorsi hanno peso 1 il peso totale è Somma dei pesi di ogni singolo arco = 4
Sarebbe diverso se avessi potuto assegnare ad ogni singolo
arco un peso in funzione di qualche particolare caratteristica
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 21 of XX _
Grafi ricerca minimo percorso
q r
e c g b
a
d
r q g e d c b a
r q g e d c b a
0 1 0 0 0 1 1 1
1 0 0 0 0 0 1 0
0 0 0 0 1 1 0 1
0 0 0 0 1 1 1 0
0 0 1 1 0 1 0 1
1 0 1 1 1 0 1 0
1 1 0 1 0 1 0 0
1 0 1 0 1 0 0 0
0 0 0 0 1 1 1 0 e
1 1 0 1 0 1 0 0 b
1 0 0 0 0 0 1 0 q
0 1 0 0 0 1 1 1 r
r q g e d c b a
a
1 0 1 0 1 0 0 0
Visite dei percorsi
0 1 0 0 0 e
1 0 1 1 0 b
0 1 0 1 0 q
0 1 1 0 1 r
e b q r a
a
0 0 0 1 0
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 22 of XX _
Grafi ricerca minimo percorso
q r
e c g b
a
d
r q g e d c b a
r q g e d c b a
0 1 0 0 0 1 1 1
1 0 0 0 0 0 1 0
0 0 0 0 1 1 0 1
0 0 0 0 1 1 1 0
0 0 1 1 0 1 0 1
1 0 1 1 1 0 1 0
1 1 0 1 0 1 0 0
1 0 1 0 1 0 0 0
0 1 0 0 e
e b r a
b r a
1 0 0
0 1 0
1 0 1
0 1 0
0 1 0 0 e
1 0 1 0 c
0 1 0 1 g
e c g a
a
0 0 1 0
0 1 1 1 0 e
1 0 1 0 0 b
1 1 0 1 0 c
1 0 1 0 1 d
e b c d a
a
0 0 0 1 0 1
0 1 d
e d a
e a
0 0
1 1
0 Visite dei percorsi 0
Peso 3 Peso 3
Peso 4
Peso 2 percorso minino
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 23 of XX _
Strutture di dati I dati che devono essere memorizzati durante
l’elaborazione delle informazioni possono essere classificati in tre diversi modi:
Variabile semplice
sono utilizzate normalmente come supporto alla programmazione (costanti, costanti funzionali,
indici correnti, indicatori di stato flag, depositi tempor.)
Vettore (n) n indice
sono sequenze di dati dello stesso tipo (elenco di nomi, elenco di voti, elenco di record,
Matrice (n,m), matrice (i,j,k) n,m,i,j,k indici sono organizzazioni di dati complessi multidimensionali (valori per elaborazione grafica bi/tri/multi dimensionale)
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 24 of XX _
Strutture di dati vettori
Quando si hanno dati dello stesso tipo che devono essere aggregati e variamente organizzati si
definisce l’oggetto array (vettore)
Un vettore è una sequenza di elementi definiti dal nome, dalle caratteristiche univoche di tutti gli elementi e da un indice che identifica la posizione di ogni singolo elemento
Es. Voti d’esame di un gruppo di 100 studenti
valore
21
…
…
…
… 24 26 30 22 28 25 19 18 20 24 30 27 23 29
indice
100
…
…
…
…
14
13
12
11
10
9
8
7
6
5
4
3
2
1
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 25 of XX _
Trattamento dati vettore
Calcolare la media dei voti ottenuti dagli studenti
P1 definire variabili n n° di elementi, i contatore, z risultato P2 inserire il numero di voti da sommare su n
P3 definire un vettore dati V(n) di n elementi P4 inizializzare il contatore i=0
P5 inserire uno ad uno in 100 passi iterativamente i singoli voti P6 inizializzare la variabile z=0 per somma di tutti i valori P7 re-inizializzare la variabile i=0
P8 eseguire una iterazione di 100 passi effettuando la somma dei singoli voti
P9 eseguire l’operazione z = z diviso n P10 stampa il risultato
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 26 of XX _
Calcolare la media dei voti di n studenti
Inizio
Fine Leggi n
crea V(n)
Stampa z 0 ž n 0 ž i
0
ž
zNO SI
i = n
i + 1 ž i leggi V(i)
NO SI
i = n 0 ž i
i + 1 ž i z + V(i) ž z
z / n ž z algoritmo 1
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 27 of XX _
Calcolare la media dei voti di n studenti
Inizio
Fine Leggi n
crea V(n)
Stampa z 0 ž n 0 ž i
0
ž
zNO SI
i = n
i + 1 ž i leggi V(i) z + V(i) ž z
z / n ž z algoritmo 2
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 28 of XX _
Strutture di dati 2
Es. Valore della glicemia di un soggetto preso con una successione del tipo
ore 8, 14, 20 per 30 giorni (90 valori) Calcolare la media totale dei valori
Calcolare la media riferita all’orario di campionam.
Si supponga di avere già a disposizione il vettore
valore
190
…
…
…
… 166 140 180 197 149 212 163 150 196 207 139 207 230 141
indice
90
…
…
…
…
14
13
12
11
10
9
8
7
6
5
4
3
2
1
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 29 of XX _
Trattamento dati Calcolare la media e le medie delle ore
P1 definire variabili n n° elem., i,j cont, medie mt, m1,m2,m3 P2 definire un vettore G (n) di n elementi per la lettura
P3 inizializzare il contatore i=0 e j=0
P4 inizializzare la variabile mt=0 per la media totale
P5 iniz. a 0 le variabili m1, m2, m3 per calcolo medie orarie P6 eseguire una iterazione che legga i valori ed effettui le
operazioni sommando tutti i valori ed i valori orari P7 ………... Pk P
keseguire l’operazione mt = mt diviso n media totale della
glicemia
P
k+1eseguire l’operazione n = n diviso 3
P
k+2eseguire le tre operazioni m1=m1/n m2=m2/n m3=m3/n P
k+3stampare i risultati mt, m1, m2, m3
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 30 of XX _
Calcolare la media dei voti di n studenti
Inizio
Fine Leggi n
j j
G
→ +
→ +
→ +
1 mt (i) mt
G(i) leggi
i 1 i
3 0
2 0
1 0 0 0 0 0
m m m mt j i n
→
→
→
→
→
→
→
NO
n SI
i >
>3 j
NO SI
→j 1
=1 j
NO SI
1 ) ( 1
G(i) leggi
m i G
m+ →
=2 j
NO SI
2 ) ( 2
G(i) leggi
m i G
m + →
NO SI
=3 j 3 ) ( 3
G(i) leggi
m i G
m + →
3 / 3
2 / 2
1 / 1
3 /
/
m n m
m n m
m n m
n n
mt n mt
→
→
→
→
→
m3
stampa m2
stampa m1
stampa mt
stampa
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 31 of XX _
Strutture di dati Normalmente le tabelle non sono formate da un solo dato ma da più dati relativi allo stesso identificatore Tabelle a due o più ingressi
15/06/2010 07/03/2011 20/07/2012 Data esame
27 000159
Luigi Rossi
25 000365
Ermanno Bianchi
28 000425
Giovanni Verdi
Voto Matricola
Studente nome Studente
cognome
In questi casi si parla più specificatamente di database ed i singoli campi vengono indicati con il nome di item o field mentre il gruppo di item costituisce un record Matricola è un item o field
del record che contiene
Stud. cognome, stud. nome, matricola, data esame, voto
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 32 of XX _
Strutture di dati
L’organizzazione dei vettori e dei record può essere di tipo diverso
Strutture statiche
è una struttura che non può essere modificata può solo essere riempita e/o corretta e/o ordinata
Strutture dinamiche
è una struttura nella quale si può intervenire per aggiungere / cancellare / modificare i dati in modo che i dati abbiano sempre una loro specifica caratteristica es. ordinati
alfabeticamente sul cognome
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 33 of XX _
Dato 1 link Dato 2 link Dato 3 link ………. link
Nuovo dato
link
Dato N link head
end
Strutture dati dinamiche
Dato 1 link Dato 2 link Dato 3 link ………. link Dato N link
head end
Dato 1 link Dato 2 link Dato 3 link ………. link
Nuovo dato
link
Dato N link head
end
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 34 of XX _
...
DATO n+k+3
Strutture di deposito temporaneo
DATO n+k+2
…………
…………
DATO n+2 DATO n+1 DATO n
…………
DATO n+k
LIFO Last In First Out DATO n+k+1
DATO n+k+3 DATO n+k+1
DATO n+k+2
DATO n+k+2 DATO n+k+1
Struttura a stack
Tipicamente viene utilizzata quando
si richiamano delle subroutine
esterne alla struttura principale e si
vogliono passare i dati alla stessa
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 35 of XX _
…………
DATO n+3 DATO n+2 DATO n+1
…………
DATO n+k
DATO n DATO n+k+1
Strutture di deposito temporaneo
Elemento inserito
Coda nello stack di k elementi
Elemento prelevato
FIFO First In First Out
Tipicamente viene utilizzata quando la velocità di arrivo dati è superiore alla velocità con la quale vengono elaborati o ritrasmessi (dispositivi di ingresso uscita, tastiera, modem, stampante, server di rete)
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 36 of XX _
…………
DATO n+3 DATO n+2 DATO n+1
…………
DATO n+k
DATO n DATO n+k+1
Strutture di deposito temporaneo
…………
DATO n+4 DATO n+3 DATO n+2
…………
DATO n+k+1
DATO n+1
DATO n+k+2 Elemento inserito
Coda nello stack di k elementi
Elemento prelevato
FIFO First In First Out
Informatica - Ingegneria Medica -2012 - Franco Del Bolgia Slide 37 of XX _
