Ingegneria del software: 19 maggio 2005

Management

Metriche di produttività

Linee di codice (poco indicativo: stessa soluzione usando + righe è peggio)
Albrecht: punti funzione (per stimare non posso usare il codice che non ho ancora, ma la progettazione!).

Somma pesata di:

• Input/output del sistema
• Interazione dell’utente
• File usati internamente
• ecc.

Banker: punti oggetto come somma pesata di:

• Numero delle schermate da rapprentare
• Numero di report da costruire
• Numero di moduli 3GL da sviluppare

Halsted: Software Science
Sono dei metodi di misura alternativi al conto delle linee
Operandi: Una variabile o una costante
Operatore: un simbolo o una combinazione che influenza il valore di uno o più operandi
Indici quali (non ricordare!):Numero di operatori (E1) e operandi (E2) distinti
Numero di occorrenze di operatori (N1) e operandi (N2)
Numero di operandi concettuali in ingresso (F1) e uscita (F2)

Concetti:
Lunghezza: N = N1 + N2Stimatore di lunghezza: N’ = E1 log E1 + E2 log E2
Volume (grandezza fisica del programma) = N * log (E1 + E2)
Stimatore di difficoltà: E1 * N2 / (2 * E2)

In realtà è un metodo che lascia abbastanza il tempo che trova

McCabe (numero ciclomatico)Deriva dalla teoria dei grafi.
Vuole trovare una base per tutte le soluzioni possibili della visita del grafo dell’applicazione. Tante più sono le soluzioni che compongono questa base tanto più alta è la complessità dell’applicazione

Il numero ciclomatico è "e – n +2" dove e è il numero degli archi, n il numero dei nodi

ManagementPlanning obiettivi da raggiungere e risorse
Organizing decidere la struttura organizzativa, le responsabilità
Staffing reclutare e formare il personale
Controlling Controllo che il progetto vada come progettato

Planning
Stimare le forze
Stimare i tempi
Stimare i costi (variabile dipendente dalle prime 2)
I costi: personale tecnico, personale di supporto (segreterie, ecc.), risorse informatiche (hw e sw), materiale di consumo, struttura (affitto, bollette)

Fattori che influenzano i costi:
Numero di istruzioni da codificare
Capacità motivazioni, coordinamento del personale
Complessità dell’applicazione
Stabilità dei requisiti
Prestazioni e qualità richieste
Strumenti di sviluppo

Stime umane
Legge di Parkinson sul lavoro
Il costo dipende dalle risorse disponibile: il lavoro si espanderà fino ad occupare tutte le risorse disponibili

Price to win
Il costo è quanto più possibile il cliente è disposto a spendere
Molto usato.
Vantaggio: spesso si ottiene il lavoro (se gara)
Svantaggio: nessuna garanzia su ciò che verrà poi fatto
Non è male se posso rivedere i requisiti dopo aver preso il lavoro

Esperti esterni
E’ una prassi

Stima per analogia
Stima personale (per progetti passati) + fattori correttivi
E’ un metodo top-down

Dati d’azienda da raccogliere:
Produttività: LineeCodice/MeseUomo
Qualità: Errori/ LineeCodice
Costo unitario: CostoTotale/ LineeCodice

Oppure posso stimare sulla quantità di lavoro
Scompongo il progetto secondo una logica operativa (per fasi) e funzionale (per componenti)Quindi si stima il tempo per le singole fasi
Ancora bottom-up

Sistemi automatizzati:
Machine learning: Reti neurali, analogie, fuzzy logic
Boehm: simile a machine learning, ma si basa solo sul passato

Modello COCOMO

Tre modelli di formule
Base: dipende solo dalla stima delle linee di codice

Intermedio: 15 fattori correttivi legati a caratteristiche del progetto (legati al personale, alle macchine, legati al progetto), possibilità stima per componenti

Avanzato: non analizziamo

Ingegneria del software: 16 maggio 2005

Testing delle interfacce

Quali interfacce (grafiche? a linea di comando? A condivisione di memoria? A passaggio di messaggi?)
Tipi d'errore
Sbaglio nell'uso dell'interfaccia
Fraintendimenti dell'interfaccia
Errori di tempistica o di sincronizzazione
Quali sottoinsiemi del dominio di ingresso verranno trattati allo stesso modo?
Definiamo Classi di equivalenza i "gruppi di input" che verranno trattati in maniera analoga nel programma, così possiamo scegliere solo un rappresentante per ogni classe anziché testare tutta la classe
Si cerca di individuare dati di test che possano rivelare eventuali errori (es. numero negativi o zero)
Nel caso un dato sia un valore specifico provare sia con una classe valida che una non valida (es. password)
Gli errori tendono ad annidarsi ai limiti del dominio (ad esempio per 0, l'ultimo elemento di un array, ecc.)

Category PartitionE' un modo di dividere in classi di equivalenza

1. Analisi delle specifiche (individuare l'unità minima testabile e raggrupparle in categorie: ad esempio un parametro, lo stato di un particolare file (non presente, sola lettura, ecc.))


2. Partizionare le categorie in "scelte" (ad esempio sul dato parametro provare casi accettabili, stringhe vuote, casi non accettabili come stringhe troppo lunghe; oppure sull'ambiente: file non valido, ecc.)


3. Determinare eventuali vincoli fra le scelte (Fare tutte le combinazioni significative delle scelte dei test; trovare dei vincoli fra le scelte per limitare il numero di combinazioni. Ad es. un file non valido potrebbe invalidare tutte gli altri input)


4. Scrivere test e documentazione (Cercare di generare automaticamente i test in base alle scelte e ai vincoli

Approccio combinatorio: al posto di scegliere tutte le possibili combinazioni tra i test (contanto i vincoli) potrei prenderne solo alcune a caso

Software inspection
E’ una tecnica manuale (fatta da persone)
Moderatore: coordina i meeting, sceglie i partecipanti, controlla i processi
Readers, testers: sono quelli che al meeting leggono ad alta voce il codice (interpretandolo), cercano i difetti
Autore: l’autore del codice, risponde ad eventuali dubbi

Indicativamente 5/6 personeFasi:
Pianificazione (moderatore pianifica e sceglie le persone),
overview (per fornire il background e assegnare i ruoli),
preparation (attività X la comprensione del codice da parte dei partecipanti),
inspection (attività centrale: la lettura del codice e individuazione degli errori),
rework (l’autore corregge gli errori).

L’ispezione Goal: trovare il maggior numero di difetti
Massimo 2 sessioni al giorno da massimo 2 ore (molto pesante).
Trovare i difetti, ma non correggerli (non servono 5 programmatori per correggere gli errori)
Il moderatore regola che non si perda tempo (potevi farlo così, potevi farlo cosà)
C’è una checklist di cose da controllare SEMPRE (aggiornate e modificate per l’azienda)
Incentivi sociali: non dare punizioni, se mai darle dopo questa fase.

Active Design Review (variazione da software inspection)
Scegliere revisori con adeguata esperienza
L’autore fa domande al revisore (checklist) (per evitare che i revisori siano passivi)
Ci sono dei tool di supporto (controlli banali: tipo formattazione, riferimenti (checklists, standard con esempi, aiuti alla comprensione del codice (reenginering, ecc.), annotazioni e comunicazioni, guida al processo e rinforzo)
Posso usarlo anche su programmi incompleti e non funzionanti
In realtà è un processo piuttosto rigoroso…

Limiti:
Test solo di singole parti del codice
Non incrementale (non posso riproporlo automaticamente ad una nuova versione del software)

Vantaggi di avere un gruppo di testing (che faccia solo testing)
Maggiore specializzazione
Conoscenza di tecniche/strumenti
Distacco dal codice (pensa a cose diverse da chi l’ha scritto)
Indipendenza dalla valutazione

Svantaggi:
Si perde la capacità di scrivere codice
Minore conoscenza dei requisiti
Possibile pressione psicologica negativa sul team di sviluppo
Difficile stabilire le responsabilità (di chi scrive e sbaglia o di chi testa e non trova?)
Better testing-worst quality (“tanto poi loro correggono…”)
Alternativa: rotazione del personale

Modelli statistici
Ci sono studi sulla presenza di errori a seconda di alcune metriche del codice (lunghezza dei moduli, numero di uscite dal modulo, ecc.) quindi posso tentare di predire la distribuzione degli errori (però è solo una cosa statistica)
In alcuni casi al posto di ultra-testare un modulo “pericoloso” lo si fa riscrivere…

Ingegneria del software: 12 maggio 2005

Copertura delle definizioni
Voglio trovare dei valori tali che per ogni definizione (assegnamento) di una variabile voglio che ci sia almeno un uso all'interno di un caso di test

Copertura degli usi
Come copertura delle definizioni, ma applicato a tutte le variabili in gioco /non solo una)
(include la copertura delle definizioni)

In ambiente object oriented
Nei linguaggi OO é leggermente diverso il testing: l'unità da testare non é più la procedura, ma la classe in quanto i metodi spesso dipendono dallo stato dell'oggetto.
Ereditarietà: i metodi già testati nella classe base vanno ritestati (anche se non ridefiniti) perché cambia il contesto (chiaro che posso sottoporre agli stessi test).
Classi astratte: non ha senso testarle (devo testare le ereditate)
Dynamic late binding: difficile capire quale metodo di quale classe sarà eseguito (un metodo chiamato su una classe o sulla sua base potrebbe essere diverso)

Testing di una classe
Le classi andrebbero testate atomicamente... Ma come risolvere i problemi delle relazioni fra classi?! Andrebbero create delle classi Stub (mock objects): delle classi fasulle di cui scriviamo un funzionamento base-base e di cui garantiamo il funzionamento per l'input che deve essere sottoposto dal test

Basandoci sullo State Diagram
Posso voler testare tutti gli stati
Posso voler testare tutti gli archi
Coprire tutte le coppie di archi in/out

Problemi:
Potrebbe mancare il diagramma degli stati (ci sono tool che fanno il reverse engineering, però non é "l'idea", ma la sua rappresentazione pratica che potrebbe essere sbagliata)

Cos'altro possiamo fare?!
Beebugging: Inserire apposta degli errori (funziona solo se il tester e il dev sono persone diverse) Quasi una gara tra tester e dev.
Analisi mutazionale: Creo dei programmi simili a quello che devo fare, ma con piccole differenze (errori), li faccio testare. Scopo dei tester trovare quello giusto! (MOLTO DISPENDIOSO). Operatori mutanti: E' una funzione che dato in ingresso il programma crea dei Mutanti.

Test funzionale (Black box)
Non c'é conoscenza del codice
I dati di test possono essere ricavati dalle specifiche (requisiti funzionali)
Permette di trovare errori non sintetizzabili con criteri strutturali (es: funzioni scorrette o mancanti, errori di interfaccia, errori di prestazioni)
Potrebbe anche essere l'unico approccio possibile, maanche avendo il codice ci vuole sempre

Ingegneria del software: 9 maggio 2005

Test strutturale: White Box
Copertura dei comandi
E' praticamente impossibile coprire il 100% del codice (ad esempio non verranno eseguite le parti che sollevano eccezioni per input scorretto)
Copertura delle decisioni
Certo é che in alcuni casi di input pur essendo coperti tutti i comandi potrebbe non essere coperto tutto "l'albero delle decisioni". Ad esempio: c'é un if con una condizione: ci entro e quindi ne copro il codice, ma se non ci fossi entrato la procedura poteva avere un comportamento diverso.

Per questo si parla di copertura delle decisioni
Una copertura totale delle decisioni prevede l'esecuzione di ogni arco del grafo di controllo del programma
La copertura dei comandi é un sottoinsieme della copertura delle decisioni

Copertura delle condizioni
Un test soddisfa il criterio di copertura delle condizioni se e solo ogni singola condizione che compare nelle decisioni del programma assume valore sia vero che falso per diversi casi t di T
La coperura delle decisioni non é un sovrainsieme di quella delle decisioni, pertanto il test perfetto le dovrebbe comprendere tutte e due

Copertura delle condizioni composte
Provare a rendere vere/false tutte le singole parti delle condizioni composte
Problema: il numero di casi da esaminare sta crescendo velocemente (esponenziale).

Condizioni Decisioni Modificate
Se io ho 2 condizioni in OR ad esempio non serve che io testi 4 casi, bastano:
falso falso, vero falso, falso vero
Il caso vero vero é già coperto dal secondo e dal terzo
Seguendo i casi in questa maniera la crescita dei test segue n+1 (lineare!)
Problema: "e i cicli?"
Potrei eseguirli 1 volta, 2 volte, fino ad infinito (ovviamente non applicabile)

N-copertura dei cicli
Posso decidere di coprirli N volte
ATTENZIONE coprirli N volte non vuole dire fare N loop nel ciclo, ma N!
Ovvero: entro ed esco dopo 1 ciclo, entro ed esco dopo 2, ecc. fino a N

Problema: come scegliere N?!

Precondizioni = Condizioni all'arrivo
Postcondizioni = Condizioni all'uscita del ciclo
Invarianti = Condizioni sempre valide

N=0 equivale ad un if con le precondizioni false
N=1 equivale ad avere un if con precondizioni vere
N=2 l'invariante e le condizioni di uscita implicano le postcondizioni (???)

N > 2 da questo punto di vista non mi dice più niente (anche se potrebbe essere significativo come qualsiasi altro valore)

Un altro criterio:
Contare il codice non a linee, ma a locchi (3 linee consecutive senza salti condizionali verranno sempre eseguite)
Contare anche il codice contenuto in funzioni? Anche se esterne?

Testing strutturale: analisi Data Flow (Analisi DF)
...non effettuato dinamicamente durante l'esecuzione
Si basa sull'analisi del codice senza eseguirlo (non soffre del problema di esplosione del numero di casi da analizzare)
esempio: puntatore non analizzato
Da qui arrivano la maggior parte degli errori di compilazione in linguaggi moderni (Java, C#)
Cerca da un analisi statica di prevedere possibili errori legati ai dati che si scateneranno in fase dinamica.

Analisi delle operazioni che possono essere effettuate sui dati:
Definizione: assegnamento di un valore ad una variabile
Uso: lettura del valore (p-uso: per condizioni, c-uso: nel calcolo di un valore)
Annullamento: se al termine di un'esecuzione il valore della variabile non é più significativo (appena dichiarata, quando esce dallo scope (potrebbe essere ancora puntata in C))

Così posso costruire delle espressioni regolari che rappresentano l'uso di una certa variabila ll'interno delle varie linee di codice
Es:

(1) void swap (*int x1, *int x2) {
(2) int x;
(3) x2=x;
(4) x2=x1;
(5) x1=x;
(6) }

La variabile x: auua (annullata in riga 2, usata in riga 3; usata in riga 5, annullata in riga 6
La variabile x1: aduda (annullata in 1, definita in 1; usata in 4, definita in 5, annullata in 6)
La variabile x2: addda (annullata in 1, definita in 1; definita in 3, definita in 4, annullata in 6)

Indizi di anomalie rilevabili:
x usata 2 volte senza essere definita
x1 viene definita una seconda volta senza mai essere usata
x2 viene definita 3 volte senza essere mai usata

Non sono errori sicuri ed in alcuni casi potrebbero essere comportamenti voluti (non uso io il valore di una variabile, ma imposto un registro hw, ecc. ecc.)
Alcuni linguaggi segnalano warning, altri segnano come errore (magari obbligando a fare in un altra maniera nel caso che il comportamento fosse voluto)

Ingegneria del software: 5 maggio 2005

VERIFICA E CONVALIDA
Convalida
Confronto del software con le idee del committente
Verifica
Confronto del software con le specifiche formali. Le specifiche formali non sono (devono essere) ambigue.
(Verifica della corretteza del programma)
Sono punti di vista "volubili": é impossibile controllare tutto il software e l'utente ha sempre le idee poco chiare...
Quindi questo confronti vanno fatti durante tutto il ciclo di vita del software (non solo dopo la produzione)

I possibili problemi:
Malfunzionamento o guasto (failure)
Il programma da un risultato sbagliato (é un effetto esterno percepito dall'utente)
Es. Arian 5 (ESA 1996) viene lanciato e dopo 40 secondi esplode (percezione dell'utente)

Difetto o anomalia (fault)
E' legato al codice (non percepito dall'utente). Può originare un malfunzionamento
Può non manifestarmi come malfunzionamento se: (doppia anomalia: una elimina l'altra, si presenta su un input che non viene mai fornito)
Es. Il software di guida del satellite convertiva la velocità orizzontale da un double ad uno short e il programma é andato in overflow

Errore (error)
E' la causa di un anomalia
In genere si tratta di un errore umano (battitura, piuttosto che concettuale, padronanza del linguaggio, ecc.), ma può anche essere un bug nel compilatore
Es. Una parte di software era erditato dal lancio di Arian 4 in cui non succedeva mai che la velocità orizzontale soperasse i 16 bit signed (anzi c'era già un bel magine)

Considerazioni:
Non si era testato con la VERA traiettoria che il satellite doveva eseguire (tali dati non erano nemmeno stati forniti come specifiche)
Il meccanismo di protezione dalle eccezioni era focalizzato su errori HW e non SW

Tecniche di analisi del sw
Tecniche statiche (applicati al codice)
Metodi formali di correttezza
Analisi dataflow (analisi complessa dei dati e vedere come si incastrano tra loro)
Modelli statistici

Tecniche dinamiche (basate sull'esecuzione del programma)
Testing
Debugging

Principi
Sensitività: E' meglio fallire sempre che solo qualche volta (un bug che si manifesta solo in particolari condizioni é difficile da trovare)
Ridondanza: Rendere le intenzioni esplicite (usare più tecniche di convalida e verifica)
Partizionamento: Divide et impera (isolare il punto che da problemi)
Restrizione: semplificare il problema (es: usare un linguaggio fortemente tipizzato, evitare i puntatori, dichiarazione esplicita delle variabili, ecc.)
Feedback: regolazione del processo produttivo (non ripetere gli stessi errori)

Come evitare gli errori:
Prove formali: ricerca di anomalie (es. controllo delle specifiche formali)
Testing: rilevare malfunzionamenti. Tecnica ottimistica: faccio tante prove...
Debugging: Conoscendo un problema cerco l'anomalia che lo genera

DEF: Correttezza di un programma
P(d) indica l'esecuzione del programma su input d
Il programma é corretto solo se é corretto l'output di P(d) per ogni d che appartiene al dominio

Un test (T) é un sottoinsieme del dominio (D). Un elemento del test t é detto caso di test
Esecuzione del test: esecuzione del programma per tutti i t € T
Il programma passa (o supera) il test se il risultato per ogni t é corretto! Il test ha successo se viene rilevato un nuovo problema.

Criterio di selezione dei dati per il test:
Affidabilità: il criterio di scelta dei test é affidabile se per ogni t in T il passaggio del test implica che passerà per tutti gli altri t. Ovvero un elemento del test "controlla" l'altro: saputo il risultato per t so già quale deve essere il risultato per t1.
Validità: Qualora il programma non sia corretto esiste un test che ha successo (non passa)

Se un test é affidabile e valido e il test viene passato ciò implica che il programma sia corretto

Quando trovo un bug e lo correggo non posso garantire che il programma sia corretto... Oltre al fatto che potrebbero esserci altri errori, il cambiamento che ho effettuato ha alterato il programma così come era stato testato...

Selezione dei test: Approccio White Box
White Box prevede che ho accesso al codice sorgente e ne posso indagare la struttura
In genere gli errori si annidano nel codice che viene eseguito poco (negli angoli, come la polvere!). Per questo sono nati i costrutti di gestione delle eccezioni!

Un caso di test si può considerare efficace quando:
- Esegue il comando che contiene l'errore
- L'esecuzione del comando che contiene l'errore deve portare ad uno stato scorretto
- L'output scorretto deve propagarsi fino all'uscita del codice in esame in modo da essere visibile

Il nostro test deve quindi coprire tutte le righe del programma

Ingegneria del software: 2 maggio 2005

Primi 10 minuti per chiarire le TBN (Time Basic Nets)
Altri 10 minuti a chiarire WTS e MWTS
Altri 10 minuti per un esercizio

Semantica forte (STS)
Una transizione DEVE scattare appena viene abilitata!
Molto più diffusa: sistemi deterministici
Se una transizione sta scattando il gettone con il timestamp più alto deve essere nel suo preset (nessun gettone può essere arrivato dopo!)
Una rete MWTS diventa a semantica forte se allo scatto di una transizione non c'é una transizione abilitata che ha un tempo di abilitazione maggiore.

Semantica mista (MTS)
Semantica forte o debole non é più definita nella rete, ma bensì sulla singola transizione.
In genere si mette una W dentro il rettangolo della transizione

E' possibile rappresentare il tempo come un qualunque altro dato di una rete ad alto livello?!
Definisco un dettaglio dei gettoni chronos, delle regole per lo scatto e delle
WTS Non ho problemi.
MWTS Problema: devo conoscere il timestamp dell'ultimo gettone della rete. Fattibile.
STS Possibile, ma dovrei mettere tutte le informazioni in un unico gettone (SCHIFEZZA!)

HLTPN (High Level Timed Petri Nets)
Uniscono le TBN alle High Level. Ereditano le regole temporali dalle TBN
Possibili interazioni: aspetti funzionali con aspetti temporali e viceversa
Problemi: un singolo scatto può generare infinite marcature (a seconda del tempo di scatto (ipotizzando che i tempi siano nei Reali))
Rappresentazione simbolica degli stati: (introduce imprecisioni)
Coppia di funzioni [m,C] ([mu, C]) dove m é la marcatura simbolica: associa degli identificatori simbolici ai posti e C sono delle equazioni che rappresentano le relazioni tra gli identificatori simbolici.
Sostanzialmente gli stati vengono raggruppati temporalmente

Ingegneria del software: 28 aprile 2005

T-invarianti
E' la stessa cosa dei P-invarianti...
Cs = 0
s deve essere una sequenza ammissibile
Reti P/T significa Posto/Transizione!

Reti di alto livello: si assegna un contenuto ad ogni gettone
Reti temporizzate: si assegnano dei valori di tempo ai gettoni (per sistemi real-time)
HLTPN Reti di Petri ad alto livello temporizzate: (ci lavora il prof. Bellettini) insieme delle 2 precedenti
Reti stocastiche: ragionano sul tempo medio

Modello temporizzato
Aggiungo un ritardo ai gettoni (appena metto il gettone devo aspettare un certo tempo per poterlo togliere). Diciamo che lo stato "ha un tempo".
Oppure un ritardo alle transizioni
Oppure faccio un sistema dinamico sulle transizioni con la possibilità di un ritardo variabile (averne più di uno, variabile a seconda dei gettoni in ingresso, avere un tempo relativo ai posti)

Time Basic Nets (TBN o TB)
Scelta di semplicità
Tempi sulle transizioni... (se avessi i tempi sui posti basterebbe splittare i posti e metterci una transizione con quel tempo in mezzo)
Mettendo il tempo sulle transizioni (ma anche sui posti) non é chiaro quale sia l'azione che si sta svolgendo. Posso allora sviluppare la rete aggiungendo un posto ed una transazione e mettendo su quest'ultima il tempo d'attesa. In tal caso la presenza di un gettone sul posto aggiunto mi indica che "sta scattando quella transizione"

Multiple firing time
Ovvero definire tempo minimo e massimo di scatto

Variable firing time
Il tempo di scatto é funzione del timestamp e del numero di gettoni (HTLPN) (posso definire anche gli estremi dei tempi di scatto)

Tempo di scatto assoluto vs relativo
Relativo: dipende sempre dall'istante/gettoni presenti (più semplice l'analisi); assoluto: può essere costante (scatt ad una certa ora)

Le TBN (Time Basic Nets) usano:
Tempo sulle transizioni
Tempi di scatto assoluti
Molteplici insiemi di tempi di scatto
Scelta dinamica del tempo di scatto (tra quelli dell'insieme)
Praticamente ogni gettone ha un suo timestamp ("data di nascita") pertanto non sono più tutti identici. In generale i gettoni portano con se delle informazioni che li differenziano (anche se potrebbero esserci 2 gettoni con le stesse informazioni e quindi indistinguibili)
Le transizioni hanno 2 funzioni dei tempi: tempo minimo per lo scatto e tempo massimo (deve scattare all'interno nell'intervallo fra i due tempi o non scattare più!), entrambe prendono come variabili i timestamp dei gettoni in ingresso. In più c'é il tempo di abilitazione: ovvero quando una transizione é abilitata: é un tempo maggiore uguale al gettone con timestamp più alto che userò (é detto enabling time)!
Il tempo di scatto di una transizione non potrà essere minore del tempo di abilitazione (se i gettoni necessari arrivano in t = X la transizione non potrascattare prima di X)

Semantica debole WTS (Weak Time Semantic)
Problema: potrebbe scattare una transizione che finisce prima di uno dei gettoni che sono presenti nella marcatura iniziale (ad esempio se qui sopra usassi la tupla di gettoni 3 e 4 e il gettone 5 fosse in realtà 20). Questo NON va bene!
Non é detto che una transizione scatti solo perché é abilitata (la fiamma del bruciatore dovrebbe partire dopo 3 secondi, ma se c'é vento potrebbe non partire!)
Posso costruire una semantica che forzi l'inizio di certe transizioni
Monotonicità rispetto alla marcatura iniziale
Ogni scatto deve finire in un tempo maggiore uguale a quello del "gettone più recente" che c'é nella marcatura iniziale.
Non posso avere inifiti scatti in un tempo finito! (attenzione agli scatti che impiegano tempo zero!)

Semantica Monotona Debole (MWTS)
Ha anche:
Monotonicità rispetto alla sequenza di scatto
Ovvero non possono scattare prima sequenze che vengono attivate da sequenze che scattano dopo (OVVIO) Posso avere scatti simultanei (in realtà lo sembrano se i miei quanti di tempo sono relativamente grandi)
La differenza non é piccola: l'analisi della rete non é più locale (devo controllare tutta la rete per capire quale transizione deve scattare prima)

Posso sempre costruire una sequenza MWTS per una WTS: basta permutare gli scatti (non é vero l'inverso).

MUST: guardare esercizio dal 23:00 della lezione del 2 maggio. Dura poco più di 5 minuti.

Ingegneria del software: 21 aprile 2005

Primi 10 minuti:
Non c'é modo di capire dall'albero se una rete é viva: esistono reti morte che possono avere lo stesso grafo di reti vive
Es.: Nel grafico dell'altra volta bastava aggiungere un arco da P3 a T4: potenzialmente si possono esaurire quindi i P3 quindi uno stato di (0;1;0) che é preso in considerazione nell'albero come (0;1;w), ma in realtà é un deadlock!

Alberi di raggiungibilità
Un albero che contempla tutte i possibili stati di tutti i posti nelle varie maracature possibili. Si può fare solo per le reti limitate!

Estensione: priorità
Svantaggio: si perde la località di decisione della abilitazione di una transizione

Rappresentazione matriciale
Devo assegnare un indice ad ogni posto ed un indice ad ogni transizione
Creo due matrici:
i (input)
Metto in ascissa le transizioni ed in ordinata i posti. Se esiste un arco tra posto e transizione nella corrisponde casella ne metto il peso (altrimenti 0)

o (output)
Metto in ascissa le transizioni ed in ordinata i posti. Se esiste un arco tra transizione e posto nella corrisponde casella ne metto il peso (altrimenti 0)
Il vettore m (marcatura)
E' un vettore colonna di dimensione P
Ovvero quanti gettoni ci sono nel posto con quello stesso indice
Se un vettore marcatura "copre" una colonna del vettore i allora può scattare la transazione corrispondente
Vettore Marcatura dopo scatto di transizione:
La nuova marcatura si otterrà da: Vettore m - vettore colonna della transazione in matrice i + vettore colonna della transazione corrispondente nella matrice o. In effetti conviene (informaticamente) calcolare già la matrice c come o-i (o perde di interesse).
Possiamo anche creare una matrice per una sequenza di scatti: sommo tutti i c delle transizioni coinvolte (o meglio moltiplico per un vettore riga che specifica il numero di volte che scatta ogni transizione).
Si chiamano reti pure le reti in cui preset e postset di ogni transizione non hanno intersezioni (agiscono su posti separati)

INVARIANTI
P-Invarianti
Relativi alla marcatura
Simile a trovare reti conservatice (o strettamente conservative)
Vettore h (pesi associati a dei posti) tale che moltiplicato per una qualsiasi marcatura raggiungibile M il prodotto h m deve essere costante
Quindi hm = hm1
m = m1 + Cs (s é una sequenza di scatti ammissibile)
hm = hm + hCs
hCs = 0
hC = 0
Devo trovare le soluzioni di questo sistema: di solito 0 o infinite. Se infinite voglio trovare le basi delle soluzioni (le soluzioni sono vettori, questi vettori possono combinarsi in infiniti modi: io voglio le basi linearmente indipendenti di tutte queste infinite soluzioni).
Che significato hanno queste soluzioni?! Queste soluzioni mi danno la configurazione di gettoni ... INSOMMA BOH! (é spiegato nell'ultima mezz'ora (anzi ultimi 10 minuti per l'interpretazione dei risultati)!)

Ingegneria del software: 14 aprile 2005

Consigliato seguire esercitazione primi 10 minuti
Possibili estensione delle reti di Petri
Fissare il numero massimo di token ammissibili in un posto.
Posso farlo senza bisogno di nuove regole: aggiungo un "posto complementare", lo collego alle transizioni del posto originale invertendo gli archi. Metto nel complementare tanti gettoni quanti sono i posti massimi meno il numero di gettoni che ci sono già nel posto ordinario.

Archi inibitori
La transazione scatta se NON ci sono gettoni nel posto collegato con l'arco inibitore. (arco con pallino bianco)

Anche in questo caso posso ricondurre ad una rete di Petri standard (a patto che il numero di posti sia limitato). Basta che creo un P1 complementare con 1 gettone e collego questo P1 complementare con doppio arco a T0 (ci dovrà essere 1 gettone in P1Comp, ma potrà essercene al massimo 1 tra P1 e P1comp!).
Un esempio del problema di sincronizzazione lettori/scrittori con gli archi inibitori:


Tentare di togliere il peso degli archi:
Archi uscenti: posso introdurre un "posto globale" che ha una connessione a doppio senso con qualsiasi transizione eccetto che con la transizione interessata. Creo un posto ed una transizione "bis" e collego l'arco di ritorno al posto globale dalla transizione bis (figura). In tal caso l'unica transizione che potrà scattare dopo T0 e proprio T0bis!!!

Archi entranti:
E' molto più complesso... Il problema non é fare scattare con 2 gettoni, ma fare in modo che non scatti prima che ci siano 2 gettoni!!! Questo é un esempio (ma non automatizzabile con 3 o 4 o N gettoni!!!) (quindi ben venga il formalismo dei pesi degli archi)

Reti condizioni eventi (C/E)
Archi peso 1
Posti capacità 1
I posti si comportano da variabili booleane
Esiste sempre un'equivalente C/E di una rete P/T purché sia limitata: basta estenderla

Reti conservative
Una rete P/T con marcatura M si dice conservativa rispetto ad una funzione di pesi P se per ogni marcatura M1 raggiungibile da M la sommatoria di tutti i gettoni non varia!

Copribilità
Relazione tra marcature
M copre M1 se e solo se per ogni posto P il numero di gettoni é sempre maggiore-uguale in M1 che in M
M1 é copribile da M se esiste una marcatura (M2) raggiungibile da M che copre M1. Ovvero la copribilità non deve essere per forza diretta!
Definita M la marcatura minima (con il minimo numero di token) per attivare la transizione t allora t é morta solo se M non é raggiungibile dalla marcatura corrente
Se M copre M1 allora tutte le transizioni abilitate in M1 lo sono anche in M (più potrebbero esserlo delle altre!)

Albero di copertura
Ovvero ridurre una rete infita in un albero (e grafo) (quindi finito)!
...nel caso in cui abbia una marcatura che copre se stessa (si può ripresentare simile, ma con uno o più posti incrementati) posso mettere w (omega: significa infinito) nel posto della marcatura che viene incrementato...

Proprietà degli alberi di copertura:

• Una rete di Petri é: limitata se w (omega) non compare in nessun nodo dell'albero di copertura
• Una rete di Petri é: binaria se compaiono solo 0 e 1
• Una transizione é morta (0-live) se non compare nell'albero di copertura
• Condizione necessaria affinché una marcatura M sia raggiungibile é che esista un nodo etichettato con una marcatura che copre M
• Non c'é modo di capire dall'albero se una rete é viva (dimostrato nei primi 10 minuti della lezione del 21 aprile: esistono reti morte che possono avere lo stesso grafo di reti vive (bastava aggiungere un arco da P3 a T4: potenzialmente si possono esaurire quindi i P3 (quindi uno stato di (0;1;0) che é preso in considerazione nell'albero come (0;1;w), ma in realtà é un deadlock!)

Ingegneria del software: 11 aprile 2005

Reti di Petri
In un certo senso evoluzione delle macchine a stati finiti, ma gli stati vengono visti come composizione di stati "atomici" e quindi le transizioni mutano solo parte dello stato.
http://www.daimi.au.dk/PetriNets

Hanno a disposizione una rappresentazione grafica intuitiva
Le unità delle reti di Petri sono:
Posti, Transizioni, Gettoni (e archi orientati). I gettoni vengono inseriti nei posti, gli archi connettono posti a transizioni (e vice versa). Un posto può essere attaccato ad una sola transizione, ma una transizione può essere attaccata a più posti.

Le reti di Petri sono la 5upla:
<P,T,F,W,m0>
dove:
P Insieme dei posti
T Insieme delle transizioni
F Relazioni di flusso (gli archi orientati)
W Funzione che associa un peso ad ogni flusso (non presente in tutte le versioni delle reti di Petri. Interi maggiori di zero)
m0 Numero iniziale di gettoni. Ogni posto ha dei gettoni (intero >= 0).

Pre(a) ovvero Preset(a) é un percorso predeterminato che porta al nodo a
Post(a) insieme dei nodi collegati con un flusso che partono da a
Comportamento dinamico
Si basa sull identificare quali sono le transizioni abilitate a scattare
Sono transizioni abilitate a scattare quelle il cui peso dei gettoni del posto é maggiore del peso dell'arco che congiunge con la transizione
La transizione t é abilitata nella marcatura M: M[t>
Lo scatto di una transizione t dalla marcatura M produce una nuova marcatura M'
Quando scatta una transizione per ogni posto in ingresso tolgo un numero di gettoni pari al peso dell'arco che conduce alla transizione e aggiungo il numero di gettoni pari agli archi in uscita che raggiungo posti che prima non erano presenti.

Nell'immagine: sulla sinistra un automa a stati finiti, sulla destra la corrispondente rete di Petri

Il peso degli archi non é specificato perché é banalmente 1

Alcuni dettagli: i gettoni NON si spostano vengono distrutti e ricreati.
Le reti di Petri sono NON-deterministiche (in alcuni casi più di una transizione potrebbe scattare e ne scatterà casualmente una delle tante che possono scattare.
Si consiglia di guardare 15 minuti di lezione dal minuto 20:00 della lezione corrispondente

Relazioni tra le transizioni (t1 e t2 nella marcatura M)
Sequenza (t1 e t2 sono in sequenza (nella marcatura M) se t1 é abilitato in M, t2 NON lo é, ma viene abilitato dallo scatto di t1 in M. In parole povere se t1 é attivabile e poi lo é t2)
Conflitto:
Strutturale: quando esiste un intersezione non vuota tra Pre(t1) e Pre(t2) ovvero quando hanno dei posti (precedenti) in comune.
Effettivo: se c'é un conflitto strutturale e il numero di gettoni nei posti comuni é sufficiente a fare scattare solo una qualsiasi delle transizioni, ma non entrambe (come strutturale, ma in più ci sono i gettoni)
Rilassata: t1 e t2 possono scattare in M, ma t1, t2 non é una sequenza ammissibile in M. Ovvero come l'effettivo, ma asimmetrico (potrebbe esserci un arco che permette l'attivazione in un senso)
Concorrenza: (quando non sono in conflitto)
Strutturale: quando l'intersezione fra i preset é nulla
Effettiva: Quando c'é intersezione fra i preset, ma ci sono abbastanza gettoni perché partano entrambe le transizioni (probabilmente in una transizione successiva ci sarà conflitto effettivo)

Insieme di raggiungibilità di una rete a partire da una certa marcatura M é il più piccolo insieme di marcature raggiungibili dalla marcatura M senza bisogno di aggiungere alcun token (il sistema si deve evolvere con i token già presenti nella marcatura M). Non é detto che sia identificabile (più che altro non é detto che sia finito).
Se la rete é limitata allora posso costruirne sempre un automa a stati finiti
Gradi di vitalità di una transizione
grado 0) la transizione é MORTA: se in qualunque caso é impossibile che dalla marcatura corrente verrà a scattare la transizione t in oggetto.
grado 1) Esiste almeno una marcatura raggiungibile in cui é abilitata
grado 2) Esiste almeno una sequenza ammissibile in cui posso fare scattare la transizione N (per qualsiasi N) volte
grado 3) Esiste una sequenza ammissibile in cui scatta infinite volte
grado 4) (é viva) in qualunque marcatura raggiungibile esiste una sequenza ammissibile in cui scatta.
Una rete si dice viva se tutte le sue marcature sono vive (tutte di grado 4).

Nell'esempio:
T0 é di grado 0, T1 di 1, T2 di 2, T3 di 3 e T4 di 4.
Perché T2 é di grado 2?
In effetti io posso fare scattare T3 N volte (quindi caricare P2 con N gettoni), ma poi faccio scattare T1 e non posso più tornare indietro (quindi un numero finito grande a piacere, ma non infinito!)!

Ingegneria del software: 8 aprile 2005

Programmazione orientata agli aspetti (by Monga)
L'ingegneria del software per risolvere un problema:
Scompone il problema in parti più piccole (analisi)
Ricompone la soluzione finale dalle soluzioni parziali (sintesi)

In realtà non in tutti i casi si può procedere così. Ad esempio se ci sono due parte che vengono eseguite in parallelo NON si può svilupparle in maniera completamente separata perché la parte di sincronizzazione fra le due deve essere pensata "insieme".

Spaghetti programmaing (codice intrecciato)
Code tangling
Un componente tenta di risolvere più problematiche

Code scattering
Il codice per la soluzione di un problema é diviso tra più componenti.

Es.
Nel mio codice inserisco ovunque delle printf di debug...
...nella singola procedura avrò del code tangling: anziché occuparsi di una cosa sola si occupa di 2 (anche il debugging)
...il componente "debug" invece é in code scattering: diffuso avunque nel codice e non concentrato in un singolo punto!

Miglioramenti linguistici hanno lenito la spaghetti programmaing (ad esempio l'introduzione delle istruzioni di ciclo hanno eliminato le difficoltà di seguire i goto
La programmazione orientata agli aspetti cerca soluzioni linguistiche per la semplificazione del codice

Costrutti speciali per isolare gli aspetti (aspects)
Costrutti per identificare i punti di integrazione (join points)
Aspetti vengono poi "intrecciati da un motore opportuno (weaving)
Il weaving potrebbe essere fatto dal compilatore,

AspectJ: é un Java orientato agli aspetti...
AspectSimpleTracing{
pointcut traced();
call (void Display.update()) (void Display.repaint(...));
before(): traced() {
println ("Entering: " + thisJoinPoint);
}
void println{//istruzioni per stampa sullo stream desiderato}
}
L'esempio qui sopra definisce un pointcut: i pointcut sono dei punti dove il compilatore di aspectJ inietterà chiamare al codice desiderato. In questo caso, tramite le istruzioni "before..." viene stabilito che prima delle chiamate a Display.update e Display.repaint viene chiamata la funzione println passando il joinpoint (oggetto con informazioni sul punto di join (immagino linea, stack trace)) corrente.
Non sono sicuro, ma credo che il pointcut rappresenti il joinpoint, mentre l'aspect é il fatto di dovere fare del tracing prima dei pointcut.

Potrei anche voler alterare dei parametri (ad esempio a repaint cambiare il colore)
In generale esiste un linguaggio per la definizione dei pointcut che permette di definire l'intercettazione di chiamate, origine delle chiamate, destinazione, argomenti, ecc.
Un altro esempio: potrei sincronizzare metodi che accedono ad un file: uso around (al posto di before) e con la parola chiave proceed chiamo il metodo.

Alcune considerazioni: non crea problemi di sicurezza (tipo ereditarietà), limite: é in fase di compilazione. Problema principale: difficile stabilire i punti in cui "si toccano" la programmazione classica e quella aspect oriented (difficile trovare i problemi)

HyperJ
Il software viene considerato un insieme di "concern units" (soluzioni atomiche a piccoli problemi).
HyperJ aiuta a comporre queste concern units.
Le concern units vengono composte in slices
Le slices vengono composte in hyperslices (slices composte da slices) e in hypermodules (l'equivalente delle classi)
...credo che praticamente si tratti di scrivere metodi e poi costruire le classi dichiarandole come composizione dei metodi scritti (potrei prendere uno slice e metterlo in più classi)!