Paniere con risposte aperte - Algoritmi e strutture dati (2023/2024)

Lezione 015

1. Quale situazione rappresenta il caso migliore dell’operazione di ricerca in una lista?

 Lista ordinata

2. E’ possibile utilizzare una struttura dati array per realizzare un tipo di dato astratto lista?

Come?

 Si può utilizzare sia una array che un array dinamico che abbia una strategia di

crescita (incrementale o con raddoppio). Con l’array lo spazio occupato sarà O(n),

l’indicizzazione costante (get e set) e l’aggiunta di un elemento o la rimozione O(n).

 Possiamo descrivere le operazioni set(i,e) add(i,e) remove(i).

3. Cosa è una lista posizionale?

 E’ un tipo di dato astratto che realizza un contenitore di posizioni, ciascuna delle

quali memorizza una posizione.

4. Quale situazione rappresenta il caso peggiore dell’operazione di ricerca in una lista?

 Ordinata al contrario.

5. Si definisca una lista come ADT (tipo di dato astratto)

 Una lista prevede size, isEmpty, get(i), set(i,e), add(i,e), remove(i). Si può pensare

come ad una Pila o Coda dove tuttavia gli elementi si possono inserire e rimuovere

da posizioni arbitrarie. Non è una struttura necessariamente ordinata.

lOMoARcPSD|145 081 44

Lezione 016

1. Quali sono le proprietà che deve soddisfare una buona funzione di hash? Perché?

 La funzione di hash è “buona” se minimizza le collisioni. Minimizzare le collisioni

implica avere migliori performance in operazione di get, put e remove.

2. Cosa è una collisione in una hash table? Quanti modi conosci per risolvere tali collisioni?

 Si verifica una collisione quando la funzione di hash per chiavi diversa restituisce lo

stesso valore e quindi indice. Vi sono due tecniche per gestire le collisioni: tecniche

di indirizzamento aperto e tecniche di concatenazione separata.

 Con la prima qualora si verifichi una collisione si cerca una diversa posizione

utilizzando scansione lineare, quadratica o con una doppia funzione di hash. Nella

seconda invece si struttura ogni bucket come una lista.

3. Si parli delle tabelle di Hash.

 Le tabelle di hash sono una struttura dati che implementa l’ADT MAP. Tramite una

funzione di HASH si associa ad ogni chiave un valore intero che a sua volta viene

associato ad una posizione [0,N-1]. La funzione è una funzione di funzione che

opera come detto una codifica ed una compressione. La funzione di hash deve

minimizzare le collisioni (stesso indice associato a chiavi diverse). Le collisioni

vengono gestite con due tecniche: tecnica di indirizzamento aperto (utilizzando

scansioni lineari, quadratiche o doppie funzioni di hash) e tecniche di

concatenazione separata.

4. Un docente utilizza il numero di matricola (5 cifre decimali) come chiavi in una tabella di

hash per memorizzare i suoi 200 studenti. Qual è il fattore di carico della tabella (espresso

in percentuale)?

 Il fattore di carico è 0,002 che corrisponde allo 0,2%

5. Quali sono le tecniche più comuni di gestione delle collisioni in tabelle hash?

 Due tecniche: tecnica dell’indirizzamento aperto e tecnica di concatenazione

separata.

6. Cosa è il tipo di dato astratto Mappa? A che serve?

 Il tipo di dato astratto Mappa (MAP) è appositamente progettato per essere in

grado di archiviare e recuperare dei valori sulla base di chiavi di ricerca che li

identificano univocamente. Le chiavi devono essere univoche. Sono utilizzate in

molte applicazioni pratiche (DNS o dizionari)

lOMoARcPSD|145 081 44

Lezione 017

1. Quante foglie possono esserci al più in un albero binario di n nodi?

 Al più possono esserci (n+1)/2 foglie

2. Si definisca il tipo di dato astratto Albero

 E’ un ADT che memorizza gli elementi in maniera gerarchica. Si compone di nodi

che hanno una relazione genitore e figlio con l’eccezione della Root o Radice che sta

in cima e non ha genitori. SE un nodo non ha figli viene definito foglia (o esterno).

Un albero in cui ogni foglia ha al più 2 figli viene definito binario. Se ha 0 o 2 figli

viene definito binario proprio. Profondità di un nodo numero di antenati. Altezza

dell’albero massima profondità dei suoi nodi. Livello gruppo di foglie con la stessa

profondità.

3. Cos’è un albero binario?

 Per albero binario si intende un albero in cui ogni foglia abbia al massimo due figli.

Se le foglie dell’albero binario hanno 0 o 2 figli si parla di albero binario proprio.

 In un albero binario il numero di foglie è al massimo (n+1)/2 dove n sono i nodi

dell’albero.

4. Come realizzeresti un albero binario (a livello di struttura dati)

 Lo realizzerei con delle liste concatenate dove ogni elemento fa riferimento ad un

elemento padre, ad un elemento figlio sx ed un elemento figlio destro oltre

ovviamente al dato stesso. Da qui ne definirei proprio l’implementazione della

classe foglia e della classe albero che di fatto punta alla foglia root.

lOMoARcPSD|145 081 44

Lezione 018

1. Definire il concetto di tipo di dato astratto. Esemplificare

 Un tipo di dato astratto (ADT) è un modello di struttura dati che specifica:

i. Le caratteristiche degli oggetti di quel tipo

ii. Le operazioni che possono essere eseguiti su tali tipi

 E’ astratto perché non specifica come verrà concretamente implementato questo

tipo!

2. Chiarire la differenza tra tipo di dato astratto e struttura dati. Esemplificare.

 Farei un esempio di ADT Pila e struttura dati che la implementa tramite array

3. Che legami ci sono tra problemi-algoritmi-programmi?

 Problema è dare una risposta ad una domanda. La risposta al problema in genere

prevede l’elaborazione di un dato di input che porta ad avere un dato di output. Si

può identificare come un task da eseguire.

 L’algoritmo è la descrizione rigorosa delle azioni da compiere per risolvere un

problema di qualsiasi genere.

 Programma è un testo (cioè sequenza di istruzioni) scritto in accordo alla sintassi e

semantica di un linguaggio di programmazione.

4. Cosa si intende per programmi

 Testo (ossia sequenza di istruzioni) scritto in accordo con la sintassi e la semantica

di un linguaggio di programmazione

5. Cosa si intende per problema?

 Problema è dare una risposta ad una domanda. La rispsota al problema prevede

l’elaborazione di un dato di input che porta ad ottenere un dato di output.

6. Cosa si intende per algoritmo?

 L’algoritmo è la descrizione rigorosa delle azioni da compiere per risolvere un

problema. lOMoARcPSD|145 081 44

Lezione 019

1. A cosa serve l’analisi algoritmica?

 L’analisi algoritmica intende studiare le specifiche di un algoritmo per trarre

conclusioni sulle prestazioni della sua implementazione. L’analisi permette di

confrontare quindi gli indici di performance di differenti approcci al problema e

stabilire se la soluzione rispetta i vincoli sulle risorse necessarie prima di codificarlo.

2. Cosa misuriamo generalmente quando parliamo di complessità di un algoritmo?

 Misuriamo il numero di istruzioni elementari in linguaggio macchina per pesare in

maniera indipendente dalle prestazioni della macchina la complessità

3. Chiarire la differenza tra problema (computazionale) e istanza di un problema

(computazionale). Esemplificare

 I problemi possono essere visti come funzioni che mettono in relazione degli

ingressi o dati di input e delle uscite o dati di output. Una specifica configurazione

dei dati di input invece è una istanza del problema.

lOMoARcPSD|145 081 44

Lezione 020

1. Si definisca formalmente la notazione O-grande (big Oh)

 Date due funzioni f(n) e g(n), si dice che f(n) è O(g(n)) se esistono le costanti

positive c ed n0 tali che f(n)<=c*(g(n)) per ogni n>n0

2. Perché la complessità di un problema e il costo computazionale di un algoritmo vengono

misurate usando la notazione asintotica?

 Ci permettono di stabilire come la complessità aumenta all’aumentare dei dati di

ingresso e quindi stabilire se la scelta dell’algoritmo risulta corretta in base alle

stime dei dati che saranno utilizzati

3. Cosa si intende per analisi asintotica?

 L’analisi asintotica misura l’efficienza di un algoritmo (o di una sua

implementazione come programma) al crescere della dimensione dei dati di input

4. Quanti confronti sono sufficienti nel caso peggiore per trovare l’elemento più piccolo in

una sequenza di n elementi?

 N-1 confronti

5. In quanto tempo è possibile selezionare contemporaneamente il minimo, il mediano ed il

massimo di una sequenza di n elementi?

 In un tempo O(n). supponiamo che per ogni valor si faccia 3 confornti avrò O(3n) ->

O(n)

6. Si definisca formalmente Omega-Grande

 Siano f(n) e g(n) funzioni che mappano interi positivi su reali positivi. Diciamo che

f(n) e Omega(g(n)) se esiste c0 e n0>=1 tali che f(n)>=c*g(n)

 Consente di dire se una funzione è asintoticamente “maggiore o uguale di”

7. Si definisca formalmente Theta-Grande

 F(n) è Theta(g(n)) se f(n) è O(g(n)) e f(n) è Omega(g(n))

 Ci permette di dire se due funzioni crescono alla stessa velocità

8. Qual è la complessità dell’algoritmo di ricerca sequenziale, in funzione del numero di

elementi n?

 O(n)

9. Qual è la complessità dell’algoritmo di ricerca binaria, in funzione del numero di elementi

n?  O(log n) lOMoARcPSD|145 081 44

Lezione 021

7. Come misuriamo l’efficienza di un algoritmo?

 In base alla quantità di risorse (tempo, spazio) richieste dalla sua esecuzione.

8. Come si fa a stabilire se l’algoritmo A è effettivamente più veloce dell’algoritmo B?

 E’ sufficiente analizzare il tempo di esecuzione asintotico dei due algoritmi

9. Perché è utile la notazione asintotica?

 Perché ci permette di stimare gli ordini di grandezza delle funzioni che vogliamo

calcolare.

 L’analisi asintotica invece misura l’efficienza di un algoritmo al crescere della

dimensione dei dati di ingresso.

10. Quanti confronti esegue la ricerca sequenziale nel caso medio?

 (n+1)/2 lOMoARcPSD|145 081 44

Lezione 022

1. Quali vantaggi introduce la ricorsione?

 E’ un costrutto molto elegante e semplice da capire oltre che implementare.

Permette di scrivere in poche righe di codice algoritmi per la risoluzione di problemi

anche molto complessi.

2. Quali svantaggi introduce la ricorsione?

 In genere le prestazioni sono il grande svantaggio dei metodi ricorsivi che utilizzano

una grande quantità di memoria.

3. Quali sono gli algoritmi più efficienti, quelli ri