Asd_Teoria Flashcards
RECORD DI ATTIVAZIONE
-cos’è e cosa fa
-allocazione e deallocazione
-Return Address e Link Dinamico
-Struttura LIFO
Tipi di memoria
-Variabili globali e determinabili a tempo di compilazione
-Code Segment
-Data Segment
-Heap
-Stack
-Stack e ricorsione
Complessità computazionale
- L’efficienza deve intendersi non solo come tempo di esecuzione, ma anche come misura dell’utilizzo delle altre risorse del sistema
-Tre casi
Si definisce complessità computazionale di un algoritmo….
Si definisce complessità computazionale di un algoritmo l’ordine di grandezza della funzione T(n) che rappresenta il numero di istruzioni da eseguire in funzione della dimensione dei dati di ingresso, nel modello RAM.
C’è differenza tra ordinamento Interno ed estern?
E tra ordinamento sul posto e non?
-Interno: sequenza contenuta in memoria centrale
-Esterno: Sequenza contenuta in un file
———————————————————–
SUL_POSTO: la sequenza ordinata sostituisce quella iniziale occupando la medesima struttura dati, utilizzando al più strutture dati aggiuntive che occupano in memoria O(log(n))
NON_SUL_POSTO: Invece è richiesta la creazione di altre strutture dati di appoggio per memorizzare temporaneamente la sequenza
Selection Sort
L’algoritmo cerca il minimo dell’array e lo posiziona nella prima posizione dell’array, poi scegli il minimo tra i restanti e lo mette secondo e cosi via.
Semplice da implementare ma con complessità computazionale elevata.
L’algoritmo ha complessità quadratica rispetto al numero di elementi dell’array. Il numero di operazioni non dipende dal numero di elementi dell’array, quindi è la stessa per caso migliore e peggiore. O(n^2)
Insertion Sort
L’algoritmo si basa sull’inserimento dei dati in ordine.
Prima di inserire il dato questo viene confrontato con gli altri elementi, se necessario si effettua uno spostamento di questi e si inserisce il nuovo dato preservando l’ordine dell’array.
O(n^2)
BUbble sort
L’ordinamento a bolle è un algoritmo che verifica ogni coppia di elementi presente nell’array, con la relazione greater. e tende a spostare verso destra tutti gli elementi maggiori. O(n^2)
Merge Sort
Date due sequenze ordiate, vogliamo ottenere una nuova sequenza anch’essa ordinata di n+m elementi, che contenga tutti gli elementi di partenza delle due sequenze
- inizializza l’array c come array vuoto;
- confronta il primo elemento non utilizzato di a (a_i) con il primo elemento non utilizzato di b (b_j)
- Se a_i<b_j aggiungi a_i in coda all’array c, altrimenti aggiungi $b_j$. Cosi per tutti gli elementi. O(nlog(n))
Quick Sort
A differenza del merge sort, il quick sort mantiene la stessa efficienza nel caso medio, ma effettua l’ordinamento sul posto;
- Si considera l’array diviso in tre parti contigue: il pivot, gli elementi dell’insieme $a’ degli elementi esaminati che siano risultati minori del pivot, e l’insieme $a’’$ dei rimanenti elementi.
- per comodità scegliamo come pivot il primo elemento dell’array
- Inizialmente $a’ è un sottoarray vuoto, mentre a’’ è il sottoarray costituito da tutti gli elementi tranne il pivot
- Esaminiamo gli elementi di a’’ partendo dal primo elemento, se questo è minore del pivot lo spostiamo in a’
- A questo punto a sinistra del pivot ($in\space a’$) avremo tutti gli elementi minori di questo, e a destra i maggiori ($in\space a’’$). Effettuiamo i rispettivi scambi nei sottoarray e creiamo l’array totale.
Il caso medio di complessità è O(nlog(n)) come il best case. Quindi il Quick Sort ha la stessa complessità asintotica del merge sort nel caso migliore e medio.
Tuttavia se il pivot è il primo o l’ultimo elemento dell’array, (caso peggiore) l’algoritmo ha una complessità quadratica come gli altri algoritmi
Indicare e commentare il tempo di esecuzione nel caso ottimo della ricerca in una lista ordinata e nel caso pessimo della visita di tutti gli n elementi presenti in una tabella hash con indirizzamento aperto.
Per quanto rigurada la lista ordinata nel caso migliore abbiamo la complessità che è O(1) in quanto abbiamo solo confornti ed quindi istruzioni semplici.
Per la tabella hash invece nel caso peggiore abbiamo O(n) in quanto utilizziamo un ciclo per scorrere la tabella hash.
La distruzione di un BST prevede la visita di tutti i nodi, distruggendoli non appena visitati. Indicare se tale visita può essere realizzata nella modalità inorder, preorder e postorder, e per ogni modalità spiegare perché si o perché no.
La distruzione dell’albero può avvenire correnttamente con la postorder, in quanto questa effettua la visita prima ai figli, e dopo alle radici. Ciò permette di distruggere i figli e avere a disposizione il padre in modo da “risalire” l’albero e continuare sul resto. Così fin quando non viene distrutto completamente.
L’inorder non è possibile utilizzarla in quanto ci ritroveremo a deallocare delle radici, perdendo saltuariamente dei nodi, i quali rimarranno in memoria.
La Preorder invece è la più errata in quanto distrugge direttamente la radice dell’albero facendo rimanere in memoria il resto dell’albero.
Quale algoritmo di ordinamento è preferibile tra Merge Sort e Insertion Sort (nelle versioni studiate durante il corso) in termini di efficienza computazionale nel caso pessimo e in termini di occupazione di memoria? Argomentare brevemente la risposta (max 100 parole).
Tra i due in termini di efficienza, è migliore il Merge Sort in quanto ha nel caso peggiore una complessità di T(n) = 0(nlog(n)) mentre per quanto rigurada l’insertion Sort ha una complessità di 0(n^2). A differenza però che il secondo lavora in loco mentre il primo ha bisogno di array di appoggio.
Avendo un array ordinato di n interi, come potremmo effettuare una ricerca rapida? Indicare la tecnica che si potrebbe adottare e la relativa classe di complessità computazionale (max 50 parole).
Avendo un array ordinato possiamo utilizzare la ricerca binaria. Vado a metà dell’array e vedo se il numero presente è maggiore o minore di n. Se è maggiore scarto tutta la metà di sinistra, (viceversa se è minore) e proseguo allo stesso modo finchè non trovo n. classe comp. 0(log(n)).
Quali sono l’altezza minima e massima di un Albero Binario avente n>=0 nodi?
Altezza massima: n-1 in quanto posso avere alberi che hanno solo un figlio. (tipo lista)
Altezza minima: log2(n) altezza calcolabile con albero pieno
