Che materia stai cercando?

Programmazione I - puntatore, algoritmi di ordinamento, tda Appunti scolastici Premium

appunti per l'esame di Programmazione I del professor Picariello, corso di laurea in ingegneria informatica. GLi argomenti trattati sono il puntatore, gli algoritmi di ordinamento, il concetto di TDA e le liste, la complessità computazionale, le classi, il polimorfismo e altro ancora.

Esame di Programmazione 1 docente Prof. A. Picariello

Anteprima

ESTRATTO DOCUMENTO

Un oggetto è ricorsivo se è possibile darne una definizione in termini di se

• stesso;il concetto della ricorsione si rifà all’induzione matematica.La ricrosione

ritorna molto utile perché permette di risolvere in problema complesso in n

sottoproblemi + semplici fino ad arrivare al caso elementare. Per sfruttara la

ricorsione dobbiamo prima individuare un caso base e poi trovare uno o più

casi induttivi. Un’induzione ben posta deve essere: non circolare,non

ambigua,completa. Un programma ricorsivo è un sottoprogramma che invoca

se stesso. Esistono vari tipi di ricorsione:mutua ritorsione(una funzione invoca

un’altra che a sua volta ne invoca ancora una);ricorsione lineare(quando vi è

solo una chiamata della funzione ricorsiva);ricorsione di coda(quando la

chiamata ricorsiva è l’ultima ad essere eseguita). E’ possibile passare dalla

forma ricorsiva alla forma iterativa ma non è vero il viceversa.

Il typedef serve per definire dei tipi mediante un identificatore . bisogna tenere

• presente che typedef NON DEFINISCE NUOVI TIPI!E’ molto comodo nella

implementazione perché permette di sostituire un tipo mediante poche

operazioni,e quando si vuole definire un tipo con dichirazione complessa

attraverso un identificatore semplice.

Algoritmi di ordinamento

Gli algoritmi di ordinamento sono molto utili per effettuare una ricerca o per

“ordinare” liste.

Tra i vari di ordinamento noi troviamo :

 Ordinamento per selezione(Selection sort);

Ordinamento per scambi(Bubbole sort);

Ordinamento per inserzione(Insertion sort);

 Quick sort.

 Il Selection sort opera tramite spostamento fisico: cioè prese due liste di

interi,prende in esame una generica sottolista a[i]…..a[n], si definisce

l’elemento minimo(min) e la sua posizione(jmin),viene effettuato lo scambio

tra a[i] e a[jmin] = min. tale procedimento verrà poi eseguito per tutte le

sottoliste ponendo i = 0,2,….,n-2.

 ISTRUZIONE:

void SelSort(T* V,const int n){

int p;

T min;

for(int k = 0;k < n;k++){

V[p] = V[k];

V[k] = min;

}

} Il Bubble Sort opera mediante spostamento fisico.Tale algoritmo fa un

confronto a tra coppie adiacenti e si scambiano gli elementi se essi non sono

ordinati.

ISTRUZIONE:

void BubbleSort(Vettore V, int n){

int flag = 1;

for(int i = 0;i < n && flag; i++){

flag = 0;

for (j = 0;j < n;j++)

if (V[j] <=V[j+1])

swap(V[j],V[j+1]);

}

}; L’Insertion Sort opera effettuando i seguenti passi:

1. ricerca del vettore i dove inserire elem;

2. shift tutti gli elementi V[j] di un posto per i < j < nelem;

3. incremento nelem di una unità;

4. inserzione di elem in V[i];

Implementando tale algoritmo daremo vita ad una lista.

ISTRUZIONE :

void InsertSort(char* V, const int n){

int k,j,i;

char temp;

for(i = 0; i < n; i++){

V[i] = temp;

j = 0;

while((V[j] < V[i]) && j<i)j++;

for (k = 0;k <= j;k--)V[k+1] = V[k];

V[j] = temp;

}

};

 Il Quick Sort opera in questo modo:

1. sceglie un elemento x dalla lista.

2. scorre la lista al contrario partendo dall’ultimo elemento e si ferma quando ha

trovato un elemento y<x.

3. scorre la lista partendo dal primo elemento e si ferma quando ha trovato un

elemento z > x.

4. Scambia z con y.

5. tale algoritmo andrà avanti fino a quando le due scansioni si incroceranno.

6. a questo punto si avranno 2 sottoliste a destra con tutti gli elementi >x e a

sinistra tutti gli elementi <x.

7. l’ordinamento della lista può poi essere eseguito mediante sottoprogramma

ricorsivo.

 ISTRUZIONE:

void separa(vettore V,const int primo,const int ultimo,int &i,int &j){

int x;

i = primo;

j = ultimo;

x = V[(primo + ultimo)/2]

do{

while(V[i] < x)i++;

while(V[j] > x)j++;

if (j <= i){

swap(V[j],V[i])

i++;

j--;

}

}while(j <= i)

}

void ordina(vettore V,const int primo,const int ultimo){

int s,d;

separa(V,primo,ultimo,s,d)

if (primo < s)ordina(V,primo,d);

if(ultimo > d)ordina(V,s,ultimo);

}

La fusione di liste consiste nelle creazione di una terza lista ordinata contenente gli

elementi delle prime due. Algoritmi di ricerca

 Ricerca lineare: consiste nello scorrere la lista finche l’elemento desiderato non

venga trovato o scorrere la lista fino alla fine nel momento in cui l’elemento

desiderato non è incluso nella lista.

ISTRUZIONE:

void lineSearch(vettore V,const int n,const int x,int &pos){

int found = 0;

for(i = 0;i < dim && !found;i++){

if(V[i] == x){

found = 1;

pos = 1;

}

return found;

}

 Ricerca binaria : consiste nel definire un elemento centrale dato

dall’operazione [(pos1+posn)/2],in base all’elemento da cercare procedere

verso destra o verso sinistra partendo dall’elemento x precedentemente

definito.

ISTRUZIONE :

void BinSearch(vettore V,const int dim,const int x.int &pos){

int found = 0;

int j,k,i;

k = (j+i)/2;

do {

if (V[i] == k){

found = 1;

pos = k;

}

else if(V[i] > k)

i = k+1;

else

j = k-1;

} while((!found) && (i < =j)

return found;

} COMPLESSITA’ COMPUTAZIONALE

Complessità temporale :calcolo richiesto per l’esecuzione del programma.

Complessità spaziale : memoria occupata dal programma.

La complessità computazionale risulta molto utile in ci permette di calcora i reltivi

costi delle funzioni e quindi ci aiuta a capire quanto sia efficiente il programma.

Esistono 5 tipi di complessità:

 Complessità costante: l’algoritmo esegue sempre lo stesso numero di

operazioni ,qualsiasi sia il numero di dati d’ingresso.

 Complessità lineare: algoritmi che eseguono un numero di operazioni

proporzionale ad n.

 Complessità n*logn: algoritmi ottimi.

n

 Complessità esponenziale k .

Un problema si definisce computazionalmente trattabile se esiste un algoritmo

efficiente che lo risolve.

Lo stream è un flusso che può essere associato a un disco o a un’altra periferica. In

tal modo sia il vantaggio della indipendenza della scrittura dei programmi, e della

portabilità dei programmi. TDA

Il concetto di TDA estende, quella che è l’idea di tipo di dato(insieme che può assumere

una variabile),includendo anche le operazioni possibile sul dato stesso.La struttura è

incapsulata dalle operazioni che si posso effettuare su di essa e senza le quali la struttura

stessa non potrebbe essere usata. Una modifica nel realizzazione del TDA non influenza

i moduli che ne fanno uso. I vantaggi del TDA consiste nel “proteggere” la struttura

incapsulata senza poterla alterare(information hiding) e nel non influenzare i moduli che

ne fanno uso in caso di modifica del TDA.

”non ci preoccupiamo (rifiutiamo di preoccuparsi) per come siamo fatto... ci

preoccupiamo per che cosa può offrire al mondo esterno!!!!”.

Le differenze tra tipo concreto e TDA sono le seguenti:

il tipo concreto è “limitato” ai vincoli imposti sulla definizione e dall’uso del tipo,mentre

il TDA esporta un’interfaccia,esporta un tipo,l’unico modo per accedere alla struttura

sono le operazioni che si possono effettuare su di essa,l’application domain del tipo è

definito tramite assiomi e precondizioni.La potenza del TDA consiste nel fatto che

possibile dominare problemi molto complessi.Il TDA introduce anche il concetto di

modulo che praticamente è atto a contenere l’interfaccia(il cosa deve fare) e il corpo

della funzione(il come).

Le prime due domande da porsi sono:

Come bisogna fare e come deve essere fatto!

L’incapsulamento consiste nel tenere riservate alcune entità. Tali entità potranno essere

usate mediante un’interfaccia che offrirà all’utente dei servizi.

L’astrazione fondamentale dei linguaggi a oggetti è l’astrazione sui dati.

In fase di progettazione software è bene utilizzare alcune tecniche per dominare la

complessità del problema che si ha di fronte.

I meccanismi di astrazione più diffusi sono:

ASTRAZIONE SUL CONTROLLO(sottoprogramma)

• ASTRAZIONE SUI DATI(consiste nell’astrarre gli oggetti che costituiscono il

• sistema,descritti in termini di strutture dati e delle operazioni possibili su di

essa). TDA LISTE

Lista non ordinata:

Inizializzazione (nelem = 0);

• Inserimento in testa(push);

• Inserimento in coda;

• Ricerca sequenziale;

• Eliminazione in testa(pop);

• Eliminazione di u elemento dato;

• Analisi dell’elemento in testa(top);

• Predicati isEmpty/isFull(nelem = 0/nelem = N);

Lista ordinata (bisogna usare algoritmi per garantire l’ordine):

PILA (LIFO):


PAGINE

12

PESO

429.20 KB

AUTORE

Menzo

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Menzo di informazioni apprese con la frequenza delle lezioni di Programmazione 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à Napoli Federico II - Unina o del prof Picariello Antonio.

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 Programmazione 1

Programmazione I - Esercizio
Esercitazione
Programmazione 1 - esercizi vari
Esercitazione
Programmazione I - Esercitazione
Esercitazione
Programmazione 1 - Esercitazione
Esercitazione