Complessità ciclomatica

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