Podcast
Questions and Answers
Qual è il risultato della funzione E MPTY(S) quando S.N è uguale a 0?
Qual è il risultato della funzione E MPTY(S) quando S.N è uguale a 0?
La funzione TOP(S) restituisce un valore corretto anche se la struttura S è vuota.
La funzione TOP(S) restituisce un valore corretto anche se la struttura S è vuota.
False
Cosa restituisce la funzione POP(S) quando la lista è vuota?
Cosa restituisce la funzione POP(S) quando la lista è vuota?
Genera un errore di underflow
La complessità temporale delle operazioni è __________.
La complessità temporale delle operazioni è __________.
Signup and view all the answers
Abbina le seguenti funzioni con il loro comportamento:
Abbina le seguenti funzioni con il loro comportamento:
Signup and view all the answers
Quale operazione modifica il numero di elementi nella lista?
Quale operazione modifica il numero di elementi nella lista?
Signup and view all the answers
Il comando S.N ← S.N − 1 viene usato esclusivamente in E MPTY(S).
Il comando S.N ← S.N − 1 viene usato esclusivamente in E MPTY(S).
Signup and view all the answers
Quale struttura dati utilizza l'implementazione descritta?
Quale struttura dati utilizza l'implementazione descritta?
Signup and view all the answers
Quale delle seguenti affermazioni descrive meglio un Tipo di Dato Astratto (ADT)?
Quale delle seguenti affermazioni descrive meglio un Tipo di Dato Astratto (ADT)?
Signup and view all the answers
In una pila, i dati vengono estratti nello stesso ordine in cui sono stati inseriti.
In una pila, i dati vengono estratti nello stesso ordine in cui sono stati inseriti.
Signup and view all the answers
Quale nome viene dato all'operazione per inserire un elemento in una pila?
Quale nome viene dato all'operazione per inserire un elemento in una pila?
Signup and view all the answers
L'operazione di estrazione di un elemento dalla pila è chiamata ______.
L'operazione di estrazione di un elemento dalla pila è chiamata ______.
Signup and view all the answers
Abbina i termini con le loro definizioni:
Abbina i termini con le loro definizioni:
Signup and view all the answers
Quale struttura dati segue il principio LIFO (Last In, First Out)?
Quale struttura dati segue il principio LIFO (Last In, First Out)?
Signup and view all the answers
Un'implementazione concreta di un ADT richiede sempre una collezione di dati.
Un'implementazione concreta di un ADT richiede sempre una collezione di dati.
Signup and view all the answers
Qual è la relazione tra un tipo astratto e una struttura concreta?
Qual è la relazione tra un tipo astratto e una struttura concreta?
Signup and view all the answers
Quale operazione estrarrà il numero 9 dalla coda?
Quale operazione estrarrà il numero 9 dalla coda?
Signup and view all the answers
L'operazione 'dequeue()' restituisce il primo elemento inserito nella coda.
L'operazione 'dequeue()' restituisce il primo elemento inserito nella coda.
Signup and view all the answers
Quali sono i primi tre numeri nella coda dopo l'esecuzione delle operazioni?
Quali sono i primi tre numeri nella coda dopo l'esecuzione delle operazioni?
Signup and view all the answers
L'operazione di inserimento in una coda è chiamata ______.
L'operazione di inserimento in una coda è chiamata ______.
Signup and view all the answers
Dopo l'operazione 'dequeue(), dequeue(), queue(1)', qual è il primo elemento nella coda?
Dopo l'operazione 'dequeue(), dequeue(), queue(1)', qual è il primo elemento nella coda?
Signup and view all the answers
L'operazione 'enqueue(2)' inserisce il numero 2 come ultimo nella coda.
L'operazione 'enqueue(2)' inserisce il numero 2 come ultimo nella coda.
Signup and view all the answers
Quanti elementi rimangono nella coda alla fine delle operazioni?
Quanti elementi rimangono nella coda alla fine delle operazioni?
Signup and view all the answers
Abbina le operazioni alle loro descrizioni:
Abbina le operazioni alle loro descrizioni:
Signup and view all the answers
Le pile e le code sono esempi di tipi di dato astratti.
Le pile e le code sono esempi di tipi di dato astratti.
Signup and view all the answers
Nome di un operatore booleano.
Nome di un operatore booleano.
Signup and view all the answers
Un tipo di dato __________ è rappresentato dai valori 0, 1, 2, ...
Un tipo di dato __________ è rappresentato dai valori 0, 1, 2, ...
Signup and view all the answers
Abbina i seguenti tipi di dato con le loro descrizioni:
Abbina i seguenti tipi di dato con le loro descrizioni:
Signup and view all the answers
Quale operazione è associata al tipo booleano?
Quale operazione è associata al tipo booleano?
Signup and view all the answers
Il tipo di dato astratto (ADT) è sempre associato a un linguaggio di programmazione tipato.
Il tipo di dato astratto (ADT) è sempre associato a un linguaggio di programmazione tipato.
Signup and view all the answers
Cosa significa ADT?
Cosa significa ADT?
Signup and view all the answers
Quale operazione richiede di spostare gli elementi rimanenti quando si estrae un elemento dalla coda?
Quale operazione richiede di spostare gli elementi rimanenti quando si estrae un elemento dalla coda?
Signup and view all the answers
La struttura dati coda richiede sempre operazioni di spostamento in O(1).
La struttura dati coda richiede sempre operazioni di spostamento in O(1).
Signup and view all the answers
Qual è la funzione di 'head' in una coda implementata tramite array?
Qual è la funzione di 'head' in una coda implementata tramite array?
Signup and view all the answers
Quando si implementa una coda usando un array, si utilizza un array in modo ______.
Quando si implementa una coda usando un array, si utilizza un array in modo ______.
Signup and view all the answers
Abbina le operazioni di coda con il loro effetto:
Abbina le operazioni di coda con il loro effetto:
Signup and view all the answers
Quale delle seguenti operazioni di coda è corretta secondo l'implementazione data?
Quale delle seguenti operazioni di coda è corretta secondo l'implementazione data?
Signup and view all the answers
L'array utilizzato per la coda non necessita di tenere traccia delle posizioni di head e tail.
L'array utilizzato per la coda non necessita di tenere traccia delle posizioni di head e tail.
Signup and view all the answers
Dopo le operazioni queue(3), queue(5), dequeue(), che elemento rimane in testa alla coda?
Dopo le operazioni queue(3), queue(5), dequeue(), che elemento rimane in testa alla coda?
Signup and view all the answers
Qual è la condizione per determinare se una coda è piena durante l'operazione E NQUEUE?
Qual è la condizione per determinare se una coda è piena durante l'operazione E NQUEUE?
Signup and view all the answers
L'operazione F RONT restituisce il valore in testa alla coda senza alcuna verifica.
L'operazione F RONT restituisce il valore in testa alla coda senza alcuna verifica.
Signup and view all the answers
Cosa restituisce la funzione S IZE(Q) quando Q.tail è maggiore o Uguale a Q.head?
Cosa restituisce la funzione S IZE(Q) quando Q.tail è maggiore o Uguale a Q.head?
Signup and view all the answers
La funzione D EQUEUE restituisce ___ dalla coda e avanza il puntatore in testa.
La funzione D EQUEUE restituisce ___ dalla coda e avanza il puntatore in testa.
Signup and view all the answers
Abbina le operazioni di coda con la loro descrizione:
Abbina le operazioni di coda con la loro descrizione:
Signup and view all the answers
Cosa succede se si tenta di fare D EQUEUE su una coda vuota?
Cosa succede se si tenta di fare D EQUEUE su una coda vuota?
Signup and view all the answers
Il metodo N EXT C ELL aumenta l'indice di un elemento nella coda.
Il metodo N EXT C ELL aumenta l'indice di un elemento nella coda.
Signup and view all the answers
Quale errore può verificarsi durante l'operazione E NQUEUE?
Quale errore può verificarsi durante l'operazione E NQUEUE?
Signup and view all the answers
Study Notes
Introduzione
- Il corso si intitola "Algoritmi e strutture dati" e fa parte del corso di Laurea in Informatica.
- I docenti sono Ugo de'Liguoro e András Horváth.
Indice
- Tipo di dato astratto (ADT)
- Pile (stack)
- Code (queue)
Sommario
- Obiettivo: introdurre il concetto di tipo di dato astratto (ADT), specificare pile e code come ADT e definire diverse implementazioni.
1. Tipi di dati
- I linguaggi di programmazione tipati forniscono tipi predefiniti.
- Ogni tipo di dato è associato a un insieme di valori e operatori.
- Esempi: unsigned int (0, 1, 2, ... con operazioni +, -, ...) e boolean (T, F con operazioni ¬, ^, ...).
- Ogni operatore funziona secondo certe regole.
- Quando si usano tipi predefiniti del linguaggio, non si considera come vengono effettuate le operazioni.
- Si possono introdurre nuovi tipi di dati e implementare operazioni per i nuovi tipi.
1. Tipo di dato astratto (ADT)
- Un tipo di dato è astratto se è descritto prescindendo dalla sua concreta implementazione.
- La descrizione riguarda:
- La collezione di dati: da quali tipi di dati si costruisce la struttura del nuovo tipo (senza specificare la costruzione).
- Le operazioni: che cosa devono fare le operazioni definite sul nuovo tipo (senza indicare come lo devono fare).
- La complessità: eventuali vincoli sulla complessità delle operazioni.
- Una descrizione delle operazioni con le pre e post-condizioni che costituisce una sorta di assiomatizzazione del tipo.
- Un'implementazione concreta di un ADT è una struttura dati per memorizzare la collezione di dati e una collezione di procedure per realizzare le operazioni.
- La relazione tra tipo astratto e struttura concreta è analoga a quella tra problema algoritmico e algoritmo.
2. Pile (stack)
- I dati vengono estratti in ordine inverso rispetto all'inserimento.
- Terminologia:
- push: inserire un elemento nella pila.
- pop: estrarre un elemento dalla pila.
- top: restituisce l'elemento in cima alla pila.
- Esempio di operazioni: push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop(), push(6).
- Pila risultante (dall'alto): 6, 8, 1, 3
2. Pila come ADT
- Collezione dati: elementi di qualunque tipo T di dati.
- Operazioni:
- void PUSH(Stack S, T t): inserisce l'elemento t nella pila S.
- T POP(Stack S): estrae l'elemento in cima alla pila S e lo restituisce.
- T TOP(Stack S): restituisce l'elemento in cima alla pila S senza rimuoverlo.
- bool EMPTY(Stack S): restituisce true se la pila S è vuota, false altrimenti.
- int SIZE(Stack S): restituisce il numero di elementi nella pila S.
- Assiomi:
- SIZE(S), EMPTY(S), PUSH(S, t) sono sempre definiti.
- POP(S), TOP(S) sono definiti se e solo se EMPTY(S) restituisce falso.
- EMPTY(S), SIZE(S) e TOP(S) non modificano la pila S.
- EMPTY(S) restituisce Vero se e solo se SIZE(S) restituisce 0.
- La sequenza PUSH(S, t), POP(S) restituisce t e non modifica la pila S.
- La sequenza PUSH(S, t), TOP(S) restituisce t.
- PUSH(S, t) incrementa SIZE(S) di 1.
- POP(S) decrementa SIZE(S) di 1.
2. Implementazione concreta con array
- Utilizzo di un array statico di M celle per implementare la pila.
- Grazie al meccanismo LIFO (Last In, First Out), gli elementi occupano le prime posizioni dell'array.
- Quando ci sono N elementi, il prossimo elemento da estrarre è nella posizione N.
- PUSH(S, t) è definito se SIZE(S) < M.
2. Implementazione concreta con lista
- Utilizzo di una lista semplice con sentinella per evitare controlli.
- Q.head indica l'elemento da estrarre.
- Q.tail indica l'ultimo elemento inserito.
- Q.head == nil rappresenta una coda vuota.
- Operazioni:
- ENQUEUE(Q, t): inserisce l'elemento t in coda.
- SIZE(Q): restituisce il numero di elementi presenti nella coda.
- EMPTY(Q): restituisce Vero se la coda è vuota, Falso altrimenti.
- FRONT(Q): restituisce l'elemento in testa alla coda (senza rimuoverlo).
- DEQUEUE(Q): estrae l'elemento in testa alla coda e lo restituisce.
3. Code (queue)
- I dati vengono estratti nello stesso ordine in cui sono stati inseriti.
- Terminologia: - enqueue: inserire un elemento nella coda. - dequeue: estrarre un elemento dalla coda. - front: restituisce il primo elemento nella coda.
- Esempio di operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4).
3. Coda come ADT
- Collezione Dati: Elementi di qualunque tipo (T) di dati.
- Operazioni: void ENQUEUE(Queue Q, T t), T DEQUEUE(Queue Q), T FRONT(Queue Q), bool EMPTY(Queue Q), int SIZE(Queue Q).
- Assiomi:
- SIZE(Q), EMPTY(Q), ENQUEUE(Q, t) sono sempre definiti.
- DEQUEUE(Q) e FRONT(Q) sono definiti se e solo se EMPTY(Q) restituisce falso.
- EMPTY(Q), SIZE(Q), FRONT(Q) non modificano la coda Q.
- Se SIZE(Q) = N e viene effettuata ENQUEUE(Q, t), allora dopo N esecuzioni di DEQUEUE(Q) si ottiene FRONT(Q)=t.
- Se FRONT(Q) = t, allora DEQUEUE (Q) estrae t dalla coda.
- ENQUEUE(Q, t) incrementa SIZE(Q) di 1.
- DEQUEUE(Q) decrementa SIZE(Q) di 1.
3. Implementazione concreta con array
- Utilizzo di un array statico di M celle.
- Implementazione circolare di head e tail per evitare lo spostamento di elementi.
- SIZE(Q): restituisce il numero di elementi in coda.
- EMPTY(Q): restituisce True se la coda è vuota, False altrimenti (Q.head == Q.tail).
3. Implementazione concreta con lista
- Utilizzo di una lista semplice con un puntatore all'ultimo elemento per ottimizzare ENQUEUE.
- Q.head indica l'elemento da estrarre.
- Q.tail indica l'ultimo elemento inserito.
- Come si controlla se la coda è vuota?
- Q.head == nil (o null).
- ENQUEUE(Q, t): inserisce un elemento in testa.
- DEQUEUE(Q): estrae un elemento da coda.
3. Confronto delle implementazioni
- La complessità temporale di tutte le operazioni è O(1) in entrambe le implementazioni (array circolare e lista).
- La complessità spaziale dell'array è O(M), proporzionale al numero massimo di elementi. La complessità spaziale della lista è O(N) dove N è il numero attuale di elementi (c'è l'overhead dovuto ai puntatori).
- Nell'array, si deve stabilire in anticipo la dimensione massima M, mentre nelle liste non c'è questo vincolo.
3. Utilizzo della struttura dati coda
- Buffer
- Visita in ampiezza di grafi
- Simulazione
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Metti alla prova le tue conoscenze sulle strutture dati, in particolare sulle pile e i tipi di dato astratti. Rispondi a domande riguardanti le funzioni E MPTY, TOP e POP, e comprendi il comportamento delle operazioni su una pila. Scopri quanto sei esperto su questo argomento fondamentale in informatica.