Che materia stai cercando?

Informatica I - l'analisi teorica delle prestazioni di un programma

Appunti di Informatica I per il corso del professor Avanzini. Gli argomenti trattati sono i seguenti: l'analisi teorica delle prestazioni di un programma, il numero di operazioni primitive (o passi base) eseguite dall'algoritmo, la dimensione dei dati da elaborare, il valore dei dati da elaborare.

Esame di Informatica 1 docente Prof. F. Avanzini

Anteprima

ESTRATTO DOCUMENTO

Modello di costo: il tempo d’esecuzione di un algoritmo dipende in generale dai seguenti fattori:

operazioni primitive

1. Il numero di (o passi base) eseguite dall'algoritmo (ad es., istruzioni

macchina del processore)

dimensione dei dati da elaborare

2. (ad esempio, la lunghezza dell’array da ordinare)

valore dei dati da elaborare

3. Il (ad esempio, un array già ordinato, ordinato al contrario,

con valori casuali, ...)

Dato un algoritmo, vogliamo stimare una funzione T(n) che ne descrive il tempo di esecuzione T

unicamente in funzione della dimensione n dei suoi dati senza realizzare e compilare un algoritmo.

base)?

1. Cosa si intende per operazione primitiva (passo

tempo di esecuzione (circa) costante,

È una operazione che ha indipendente da valori e tipi

dei dati. (Esempio: assegnazione di valore ad una variabile, operazione aritmetica o logica

tra variabili e/o costanti numeriche e booleane, un accesso in lettura/scrittura ad un

elemento di un array). Un enunciato contenente una invocazione di un metodo non è

un'operazione primitiva.

selectionSort,

Nel caso di il tempo di esecuzione si stima contando il numero di accessi in

lettura/scrittura ad un elemento dell’array, in funzione della lunghezza nell'array (dimensione

dei dati del problema).

2. Cosa si intende per dimensione dei dati di un algoritmo?

A seconda del problema, la dimensione dell'input assume significati diversi:

La grandezza di un numero (ad esempio in problemi di calcolo)

 Il numero di elementi su cui lavorare (ad esempio in problemi di ordinamento)

 Il numero di bit che compongono un numero

 n

Indipendentemente dal tipo di dati, indichiamo sempre con la dimensione dell'input.

3. Come si tiene conto del valore dei dati?

Se l'algoritmo contiene cicli e decisioni, il numero di operazioni primitive dipende anche dal

valore dei dati, ma noi vogliamo T(n) come funzione solo di n. Di solito si stima T(n) per

caso peggiore”

eccesso, ovvero si cerca di ottenere una stima “di (Ad es. per un algoritmo

di ordinamento il caso peggiore è quello in cui l’array in input è ordinato alla rovescia).

caso migliore caso

Si possono anche fare stime di: (ad es. array in input già ordinato) o

medio (con ipotesi statistiche, ad es. array contenente numeri casuali)

Esempio

:

Esaminiamo il codice Java del metodo selectionSort:

• Conteggio degli accessi all’array nella prima iterazione del ciclo esterno (ovvero per i=0)

Per trovare l’elemento minore si fanno n accessi

 Per scambiare due elementi si fanno quattro accessi

 Caso peggiore: ipotizziamo che serva sempre lo scambio. In totale si fanno quindi

 (n+4) accessi

• Ora l'algoritmo deve ordinare la parte rimanente, cioè un array di (n-1) elementi

serviranno quindi ((n-1) + 4) accessi

 E così fino al passo con (n-(n-2))=2 elementi, incluso


PAGINE

2

PESO

257.38 KB

PUBBLICATO

+1 anno fa


DETTAGLI
Esame: Informatica 1
Corso di laurea: Corso di laurea in ingegneria dell'informazione
SSD:
Università: Padova - Unipd
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher enricopava di informazioni apprese con la frequenza delle lezioni di Informatica 1 e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Padova - Unipd o del prof Avanzini Federico.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Informatica 1

Informatica I - array bidimensionali e array paralleli
Appunto
Informatica I - la struttura dati Tabella hash con bucket
Appunto
Informatica I - Object Oriented Programming OOP e obiettivi e principi di design
Appunto
Informatica I - come realizzare una classe in java
Appunto