ITIS C. Zuccante Classe 5a ISA 9/4/2013 Carisi Matteo N° slide = 11 • • • • • • • • Introduzione Complessità ciclomatica Definizione algebrica Proprietà Formule alternative Esempio 1 Esempio 2 Riferimenti Carisi Matteo Complessità ciclomatica 1 In generale le metriche sono degli standard di misura. Nell’ingegneria del software le metriche vengono usate per quantificare e qualificare e sono di tre tipi: 1. Metriche di Prodotto 2. Metriche di Processo 3. Metriche di Qualità Carisi Matteo Complessità ciclomatica 2 Essa è stata proposta da Thomas McCabe nel 1976 ed è usata per valutare la complessità di un algoritmo in un metodo ed è interamente basata sulla struttura del grafo che rappresenta l’algoritmo. Corrisponde al numero di casi di prova necessari per verificare ogni possibile esito di ogni ramo di decisione all’interno del sottoprogramma. Carisi Matteo Complessità ciclomatica 3 Il numero ciclomatico v(G) = E – N + 2·P No archi No componenti connesse No nodi (per una sola unità di programma P è pari ad 1) v(G)=E-N+P Carisi Matteo Complessità ciclomatica 4 • v(G) ≥ 1; • v(G) = numero massimo di percorsi linearmente indipendenti in G; • L’inserimento o l’eliminazione di espressioni in G non influenza v(G); • G ha un solo percorso solo se v(G) = 1; • Inserendo un nuovo arco in G, v(G) aumenta di 1; • v(G) dipende solo dalla struttura decisionale di G; Carisi Matteo Complessità ciclomatica 5 La complessità ciclomatica è stata definita in termini di programmi/ sottoprogrammi con un singolo punto di ingresso e di uscita. Esistono varie altre formule per il calcolo di questa tra cui: v(G) = n° decisioni + 1 Se ci sono più punti di uscita -> v(G)= n° decisioni n° punti di uscita +2 Minore è la complessità e maggiore è la facilità di esecuzione dei test. Carisi Matteo Complessità ciclomatica 6 #include <vector> int main(int argc, char *argv[]) { vector<int> vector; for( int i = 0; i < 10; i++ ) { int num = (int) rand() % 10 +1; vector.push_back( num ); } int quanti_pari = 0, quanti_dispari = 0; for(int i=0 ; i<vector.size() ; i++) { if (vector[i]%2 == 0) quanti_pari++; else quanti_dispari++; } cout<< "Pari: " << quanti_pari << "Dispari: " << quanti_dispari; system("PAUSE"); return 0; } Carisi Matteo Complessità ciclomatica 7 1 /*1*/ vector<int> vector; int quanti_pari = 0, quanti_dispari = 0; int i = 0; /*2*/ while (i < vector.size()) { /*3*/ if (vector[i]%2 == 0) /*4*/ quanti_pari++; /*5*/ else quanti_dispari++; /*6*/ i++;} /*7*/ cout<< "Pari: " << quanti_pari << "Dispari: " << quanti_dispari; Il grafo ha: • 7 nodi • 8 archi, che devono essere tutti coperti • complessità ciclomatica pari a E-N+2 = 8 - 7 + 2 = 3 i >= vector.size 2 i < vector.size 3 dispari pari 4 5 6 7 Carisi Matteo Complessità ciclomatica 8 #include <vector> int main(int argc, char *argv[]) { vector<int> vector; for( int i = 0; i < 10; i++ ) { int num = (int) rand() % 10 +1; vector.push_back( num ); } int ricerca=1; int tot = 0; if (vector.size() > 0) for (int i = 0; i < vector.size(); i++) { if (vector[i] == ricerca) tot = tot + 1; } else tot = -1; cout<< tot; system("PAUSE"); return 0; } Carisi Matteo Complessità ciclomatica 9 1 /* 1 */ int tot = 0; /* 2 */ if (vector.size() > 0) { /* 3 */ int i = 0; /* 4 */ while (i< vector.size()) { /* 5 */ if(vector[i]==ricerca) /* 6 */ tot++; /* 7 */ i++;} /* 8 */ else tot= -1; /* 9 */ cout<<tot; 2 vector.size() <= 0 vector.size() > 0 3 i >= vector.size() 4 i < vector.size() 5 Vector[i]==ricerca Vector[i]!= ricerca Il grafo ha: • 9 nodi • 11 archi, che devono essere tutti coperti • complessità ciclomatica pari a 11 - 9 + 2 = 4 6 7 8 9 Carisi Matteo Complessità ciclomatica 10 • MetricheDelSoftware-F029.pdf (http://www.jugsardegna.org/vqwiki/jsp/Wiki?action=action_view_attachment&attachment=MetricheDelSoftware-F029.pdf) • 03_B_ExBianca.pdf (http://www.dis.uniroma1.it/~santucci/IS_ord_2008/MaterialeCorso/03_B_ExBianca.pdf) • Anna Rita Fasolino - Metriche Software (http://www.federica.unina.it/ingegneria/ingegneria-software-ii/metriche-software-parte-seconda/) • Wikipedia (http://it.wikipedia.org/wiki/Complessit%C3%A0_ciclomatica) • Misurazione del software (http://www.math.unipd.it/~conte/lezioni/B8.pdf) Carisi Matteo Complessità ciclomatica 11