Materie: | Appunti |
Categoria: | Informatica |
Voto: | 2.5 (2) |
Download: | 419 |
Data: | 05.12.2001 |
Numero di pagine: | 11 |
Formato di file: | .txt (File di testo) |
Download
Anteprima
algoritmi-strutture-dati_1.zip (Dimensione: 6.8 Kb)
trucheck.it_algoritmi-e-strutture-dati.txt 17.79 Kb
readme.txt 59 Bytes
Testo
NOTE: Appunti liberi di informatica, scritti ed elaborati da BoMiNg, il contenuto del seguente file ha lo scopo di rendere chiaro e comprensibile, se bene in minima parte, la struttura di un algoritmo e di tutte le sue potenzialitа, attraverso questa breve introduzione si vuole dare un piccolo contributo a quanti si avvivinano per la prima volta al concetto di algoritmo, ovvero allla risoluzione logica di problemi computazionali.
per maggiori informazioni, chiarimenti o richiesta di altro materiale vi prego di scrivere al seguente indirizzo: [email protected].
ALGORITMI E STRUTTURE DATI
? STRUTTURE DATI
- Concetto di variabile globale e locale
- Tipo di dato
- Tipi di dati primitivi
- Tipi di dati predefiniti
- Strutture dati (costruttori)
o RECORD
o ARRAY
o SET
- Struttura dati dinamica
- Lista lineare
- Ordinamento di una lista lineare
? PROGRAMMAZIONE
- Costrutti di dati iterativi
° FOR
° WHILE
- Procedure e funzione
- Concetto di passaggio parametri ad una procedura e funzione
- Concetto di ricorsione
? ALGORITMI
- Concetto di algoritmi di ordinamento basato sulla struttura dati Array
- Insertion sort
- Merge sort
STRUTTURE DATI
Concetto di algoritmo
Il termine algoritmo significa procedimento di calcolo, con questo termine si intende la descrizione precisa di una sequenza di azioni che devono essere effettuate per giungere alla risoluzione di un problema computazionale.
Concetto di variabile locale e globale
Si dice locale qualsiasi variabile residente nella memoria dinamica (stack), la quale viene chiamata dalla procedura o funzione, hanno la durata del ciclo che le utilizza, la loro struttura varia durante l'esecuzione del programma.
Si dice globale qualsiasi variabile definita nel programma principale, risiedono nella memoria statica, la loro durata и pari alla durata del programma.
Tipo di dato
Un tipo di dato determina l'insieme dei valori al quale appartiene una costante, o i valori che una variabile o costante possono assumere, o che una funzione o un operatore possono produrre.Un tipo di dato definisce un insieme di valori:
- in fase dichiarativa serve a determinare le caratteristiche di una variabile
- in fase compilativa serve a controllare la compatibilitа e la legalitа dei costrutti
Serve al compilatore per allocare la memoria necessaria a rappresentare l'oggetto associato alla variabile. Dal punto di vista dell'elaboratore i dati verranno rappresentati comunque sottoforma di espressione binaria a prescindere che si tratti di linguaggio ad alto o basso livello. Il numero di valori distinti che appartiene ad un determinato tipo di dato viene chiamato cardinalitа.
Classificazione dei tipi di dato:
Tipo scalare semplice
- reale
- scalare ordinale
enumerativo
intero
carattere
booleano
- strutturato
record
file
array
set
- puntatore
Tipi di dati primitivi
I tipi di dato primitivi vengono definiti dal programmatore ad esempio in un programma relativo alla geometria piana si potrebbe introdurre un tipo di dato primitivo detto figura, i cui valori potrebbero essere indicati con gli identificatori (rettangolo, quadrato, ellisse) questi tipi di dato non sono strutturati,
es:
type figura = (rettangolo, quadrato, ellisse)
una volta definito il tipo di dato, bisogna definire anche il proprio identificatore in questo caso f identificherа il tipo di dato figura:
var f figura
e si potranno eseguire le seguenti operazioni di assegnamento:
f:= rettangolo
la cardinalitа di figura и : card(figura)
Tipi di dato predefiniti
I tipi di dato predefiniti sono quei tipi direttamente disponibili sulla maggior parte degli elaboratori, essi comprendono i valoro logici, numeri interi, insieme di caratteri, ecc.: boolean, integer, char, real.
Le operazioni effettuate su dati di questo tipo rispecchiano in pieno le usuali leggi dell'aritmetica, inoltre la computazione verrebbe interrotta se un risultato non rispecchiasse il valore del sottoinsieme rappresentato.
Strutture dati (costruttori)
Ai tipi di dato strutturati appartengono gli ARRAY, il tipo STRING(array di variabili char), i RECORD, le variabili di tipo SET, i FILES.
- ARRAY (vettori a 1 o piщ dimensioni)
L'array и la struttura dati piщ conosciuta, и una struttura dati omogenea, и formata da componenti dello stesso tipo detto tipo di base, viene anche detto struttura ad accesso casuale. Tutte le componenti possono essere selezionate a caso, essendo egualmente accessibili. Il valore della struttura viene scansionato attraverso la presenza degli indici, che selezionano i componenti.Un array и un insieme di elementi appartenenti tutti ad uno stesso tipo, es:
Var A: array[1,….100] of integer dove la descrizione degli elementi(1,…100) appartengono tutti allo stesso tipo(interi). Per scorrere l'array esiste un insieme ordinato di variabili, anch'esse tutte dello stesso tipo che permettono la scansione e l'identificazione di ciascun elemento, esse vengono individuate attraverso il nome dell'array e la posizione o le coordinate della variabile dentro l'array, es: A[1],A[100]. Il valore dell'indice puт essere rappresentato da una qualsiasi espressione che dia come risultato un valore compreso fra 1 e 100, es: j, A[J].
- RECORD
I record o (prodotto cartesiano) sono un tipo di variabile strutturato costituito da un insieme di variabili di tipo diverso fra loro (gli elementi costituiscono i vari campi del record), и possibile accedere al record per intero o individualmente ai suoi elementi componenti chiamati(fieds) cioи campi. Il record permette di definire un dato T costituito dall'unione di altri tipi di dati T1,T2,….quindi il record forma un'unica struttura dati e di un nome per ogni singola informazione che permette di identificare tale informazione o campo all'interno del record. Un esempio di record puт essere il nominativo di ogni singola persona inserita all'interno di un elenco telefonico: con il termine generale NOMINATIVO ci si riferisce al record formato da tutte le informazioni contenute in una riga dell'elenco telefonico, mentre i diversi campi del record contengono le informazioni: cognome, via, telefono, ecc….
Esempio di definizione della struttura di un record in Pascal:
type NOMINATIVO = record
COGNOME: array [1..25] of char;
NOME: array [1..25] of char;
NUMEROCIVICO: integer;
N. TELEFONICO: integer;
- SET
Il set puт essere definito attraverso il seguente schema:
type T = set of T°
I possibili valori di una variabile di tipo set sono insieme di elementi di T°, ed l'insieme di tutti i sotto elementi di T° viene detto insieme delle parti di T°.Le variabili di tipo set permettono di definire un tipo di dato T costituito dall'insieme delle parti di un altro tipo di dato, gli elementi di tipo set sono il tipo di elementi che costituiscono un determinato insieme. Un insieme set viene rappresentato racchiudendo all'interno di parentesi quadre l'elenco di oggetti dello stesso tipo ordinale separati da virgola. Se l'elenco contiene elementi aventi valore ordinale consecutivo si puт utilizzare la notazione dei "subrange" (due espressioni separate da due punti).
Struttura dati dinamica
Una struttura dati si dice dinamica se permette di rappresentare insiemi dinamici, cioи insiemi la cui caridinalitа varia durante l'esecuzione del programma e dipende dall'utilizzo che ne facciamo. Quindi possiamo incrementare la cardinalitа di una struttura dati dinamica all'interno del programma e quindi non c'и bisogno di dichiarare all'inizio la sua grandezza, il suo contrario sono le strutture dati statiche ovvero l'array.
Lista lineare
La lista lineare и un insieme ordinato di n elementi, tutti dello stesso tipo, ogni elemento ha un predecessore e un successore, molto importante и la relazione di precedenza, cioи per accedere ad un elemento si deve accedere a tutti quelli che lo precedono, la sua forma puт essere modificata nel corso del programma.
Ordinamento di una lista lineare
PROGRAMMAZIONE
Costrutti di dati iterativi
- FOR
Il costrutto FOR и adatto per situazioni in cui una istruzione o una serie di istruzioni debbano essere ripetute n volte, ove n deve essere noto prima che il ciclo abbia inizio. L'azione dell'istruzione for и di assegnare ciascuno di questi valori, uno alla volta, alla variabile di controllo ed eseguire, dopo ogni assegnazione, l'istruzione che si trova dopo il simbolo DO. Nell'interpretare la definizione dell'istruzione FOR, sono da sottolineare i seguenti punti
a. i valori iniziali e finali determinati rispettivamente dall'espressione iniziale e finale vengono valutati soltanto una volta, all'entrata dell'istruzione for.
b. Se l'istruzione seguente il do viene eseguita, ciascun valore della sequenza definita dei valori iniziali e finale deve essere compatibile per assegnazione con il tipo di della variabile di controllo.
c. Il valore della variabile di controllo viene modificato implicitamente ad ogni ciclo della ripetizione.
d. Dopo la conclusione di un'istruzione FOR il valore della variabile di controllo non и definito, e nei programmi non si dovrebbe fare alcuna assunzione sul suo valore
- WHILE
La struttura WHILE и un costrutto iterativo per impieghi generali in cui il test di uscita dal ciclo viene collocato in testa alla struttura stessa. L'espressione viene valutata ripetutamente e, se rimane vera, l'istruzione viene eseguita di seguito alla valutazione dell'espressione, la ripetizione termina non appena il valore diventa falso.
Forma sintattica:
WHILEDO
Finchи l'espressione booleana assume valore vero, l'istruzione viene seguita altrimenti si interrompe ed esce fuori dal ciclo. In modo analogo alla struttura iterativa FOR, si rende necessario l'uso di una coppia begin/end per consentire l'esecuzione di piщ di una istruzione all'interno di un ciclo WHILE.
Procedure e funzione
La procedura и un mezzo per suddividere il programma in uno o piщ blocchi cosi da renderne la lettura e l'intervento qualora esso sia necessario piщ chiaro ed immediato. La procedura и come un blocco che aiuta il lettore a vedere in modo piщ chiaro il programma, rendendogli piщ semplice la comprensione. Un'istruzione procedura chiama la procedura denotata dall'identificatore, il suo effetto и l'esecuzione dell' istruzione immediatamente seguente l'istruzione di procedura.
La funzione si comporta come la procedura a differenza del fatto che essa restituisce sempre un valore, tipicamente il valore di ritorno di una funzione rappresenta il risultato di calcoli basati su valori passati alla funzione nella fase di esecuzione del programma.
Concetto di passaggio parametri ad una procedura e funzione
Il passaggio di parametri fra il programma ed una procedura puт avvenire in due modi:
- per valore(senza l'uso del VAR)
- per indirizzo(con l'uso del VAR)
quando in fase di esecuzione di un programma viene passato ad una procedura o funzione un parametro per valore, sullo stack viene trasferita una copia del parametro(non il parametro stesso); in effetti questa copia diviene a tutti gli effetti una variabile locale del ciclo chiamato.
Quando invece viene passato un indirizzo o riferimento, sullo stack viene trasferito l'indirizzo del parametro, ciт significa che le modifiche subite dalle variabili, si ripercuotono sul valore originario della variabile. Solamente le variabili possono essere assunte come parametri VAR, solo per loro infatti ha senso parlare di indirizzo di memoria. Le limitazioni sulle dimensioni dello stack possono rendere piщ vantaggioso il passaggio di parametri per indirizzo rispetto al passaggio di parametri per valore.
Concetto di ricorsione
Un oggetto viene detto ricorsivo se esso comprende parzialmente se stesso, la ricorsione и frequente in matematica e nella vita di ogni giorno. E' consentito ad una procedura o funzione di chiamare se stessa; questo processo viene chiamato ricorsione, e permette la creazione di algoritmi piщ semplici e soprattutto piщ compatti. Esempi in cui possono essere utilizzati metodi ricorsivi:
a. la funzione fattoriale
b. il calcolo del MCD(fra due numeri x,y, di cui x>y)
c. la potenza
d. la costruzione della tavola pitagorica
- direttamente ricorsiva se una procedura P contiene un riferimento esplicito a se stessa;
- indirettamente ricorsiva se P contiene un riferimento ad un'altra procedura Q, che contiene un riferimento diretto o indiretto alla procedura P;
In poche parole и un metodo di elaborazione il cui valore della funzione и calcolato facendo uso di altri valori che vanno di nuovo calcolati con la stessa funzione, ricorsivamente, questa termina quando il valore da calcolare assume un valore costante e noto, nell'ambito della programmazione sono detti ricorsivi i sottoprogrammi che richiamano se stessi. Da notare l'eleganza e la compattezza in termini di chiarezza e fattibilitа di un algoritmo scritto con metodi ricorsivi.
ALGORITMI
Concetto di algoritmi di ordinamento basati sulla struttura dati array
Un algoritmo di ordinamento restituisce come output una sequenza ordinata di valori partendo da un array contenente valori sparsi e quindi disordinati. L'ordinamento и una operazione fondamentale in informatica, infatti sono stati sviluppati un gran numero di algoritmi di ordinamento necessari a calcolare la soluzione. La scelta del migliore algoritmo non и cosa facile innanzitutto bisogna analizzare la struttura dati o array che dobbiamo ordinare, nel caso abbiamo una grande quantitа di valori opteremo per un algoritmo come il mergesort che ha un tempo computazionale pari ad nLogn ciт significa che questo algoritmo impiegherа un tempo piщ che ragionevole a completare l'operazione affidatagli poichй adotterа un sistema di ricorsione che implicherа un sistema di suddivisione in piщ sottoproblemi che daranno la soluzione finale, mentre se utilizzeremmo un algoritmo scorretto potrebbe non fermarsi per qualche istanza del programma o potrebbe fermarsi con una risposta diversa da quella prevista.Anche se i metodi sofisticati richiedono meno operazioni, esse sono solitamente piщ complesse nei dettagli; di conseguenza, i metodi diretti sono piщ rapidi per n abbastanza piccolo e non devono essere usati per n grande.
Insertion sort (metodi primitivi diretti)
Innanzitutto dobbiamo dire che questo algoritmo risulta efficiente al contrario del mergesort sopra citato qualora si debba ordinare un piccolo o ragionevole quantitativo di elementi. L'insertionsort funziona pressappoco nello stesso modo usato da molte persone per ordinare una mano di ramino, partendo dalla seconda carta in mano o elemento analizzato, questo algoritmi attua il confronto del valore con il precedente, se risulta minore dell'antecedente prende il suo posto facendo scorrere di una posizione il precedente poi esamina un'altra carta in questo caso elemento e via via fino a raggiungere l'estremitа dell'array e completare cosi l'operazione dandoci un output finale, considerato come l'array ordinato.il suo tempo computazionale и n2(al quadrato).
Merge sort ( metodi avanzati o logaritmici)
L' algoritmo preso in considerazione и utilizzato per lo stesso scopo del insertion sort e quindi si tratta sempre di operazioni di ordinamento, in particolare questo algoritmo fa uso della funzione divide-et-impera:
- divide gli n elementi della sequenza da ordinare in due sottosequenze di n/2 elementi ciascuna
- impera , ordina, usando ricorsivamente il merge sort, le due sottosequenze
- combina, fonde le due sottosequenze per produrre come risposta la sequenza ordinata.
Tornando all'esempio usato con il insertionsort si ricorre all'esempio del giocatore di carte, si prenda in considerazione due mazzi di carte in questo caso dividiamo l'array in due sotto array iniziando con l'arrai di destra si suddivide a due a due fino ad arrivare all'analisi del singolo elemento da qui inizia la ricorsione del merge sort che attua l'analisi e il confronto fra questi elementi fino ad riordinarli, poi analizza il secondo sottoarray e cosi facendo lo confronta alla fine con il sotto array ordinato in precedenza per il confronto finale usa un vettore di appoggio il quale и di supporto e memorizza i valori ordinati per poi restituirli all'array principale disposti ordinatamente, alla fine abbiamo come output il risultato dell'ordinamento. Da notare che il tempo computazionale del merge sort и nLogn.
Il tempo computazionale del mergesort puт essere definito come somma del tempo computazionale del mergesort e del merge:
1. la profonditа della ricorsione del mergesort и dell'oedine - O(Lgn)
2. mentre il merge и dell'ordine di grandezza - On - essendo una procedura linare.La somma toale и dell'ordine di - O(nLogn)
ESEMPI DI PROGRAMMAZIONE:
Ipotizziamo di avere una lista con 5 elementi: A[6,9,3,5,1], vogliamo ora effettuare una scansione di tale lista e poi ordinarla in ordine decrescente, quindi utilizzeremo la procedura scansione, ordina e la funzione estrazione per estrarre momentaneamente il valore e poi riposizionarlo nella posizione da noi definita. Utilizzeremo il linguaggio TP:
PROCEDURA ORDINA( VAR START:PUN, N:INTEGER)
Var i: integer
Inizio, e: pun
Begin
New(inizio)
inizioА.next:=nil
for i:= 1 to n
e:= estrazione(start)
SCANSIONE(inizio, e)
Start:=inzio
End
FUNCTION ESTRAZIONE(START:PUN):PUN
Var
Q:pun
Begin
New(q)
qА.inf:=startА.inf
qА.next:=nil
start:=startА.next
ESTRAZIONE:=q
PROCEDURA SCANSIONE(VAR INIZIO:PUN, E:PUN)
Var a,d :pun
Begin
d:=inizio; a:=dА.next;
if a=nil then dА.next:=e;
else
Begin
While (aА.inf>eА.inf) and (aА.nextnil) do
Begin
d.=a; a:=aА.next;
End
If (aА.inf < eА.inf) then
End
Begin
dА.next:=e;
eА.next:=a;
End
else aА.next:=e;
End
End
FATTORIALE RICORSIVO
FUNCTIONFATT(N:INTEGER):INTEGER
Begin
If(n=0) then fatt(n):=1
else
fatt(n):=fatt(n-1)n;
end