Tutte le domande/risposte per l'esame Algoritmi e strutture dati

Domande e risposte

Algoritmi e strutture dati

Cos'è un problema: qualcosa che siamo chiamati a risolvere

Cos'è una istanza: un particolare input ad un problema

Cos'è un algoritmo: una sequenza di istruzioni che istruiscono sull'esecuzione di un determinato compito

Chi è l'esecutore dell'algoritmo: chi esegue l'algoritmo e conosce il linguaggio con il quale è stato scritto

La seguente frase è "ambigua": il numero è grande

La pragmatica indica: lo studio del miglior modo per esprimere un concetto

Il determinismo indica: stesso risultato indipendentemente dall'esecutore

Strutture fondamentali degli algoritmi

Nella selezione: esiste una condizione da valutare e due possibili gruppi di istruzioni da eseguire

L'assegnazione: modifica il valore di una variabile

Qualunque algoritmo può essere implementato usando le sole seguenti strutture: sequenza, ciclo e selezione

Nella tesi di Church-Turing: tutti i linguaggi sufficientemente espressivi sono ugualmente espressivi

Comandi di input e output

La sequenza delle operazioni è rappresentata da: frecce

Un comando di output: valuta un'espressione e poi visualizza il risultato sullo schermo

Un comando di input: legge un input ed immagazzina tale valore in una variabile

Strutture di controllo

Nella selezione, in funzione del valore della condizione, si sceglie un blocco oppure l'altro: sempre

Nell'assegnazione: si modifica il valore di una variabile

While {condizione} do {corpo} end while: indica una iterazione

Funzioni e pseudocodice

Fun(arg1, arg2 …): indica una funzione

Il seguente pseudocodice (a, b) <- (b, a): indica uno scambio del valore delle variabili

Il seguente pseudocodice arr[{espr}]: indica un valore specifico all'interno dell'array

Ricerche negli array

Nella ricerca sequenziale di un elemento in un array di n elementi: la complessità è proporzionale ad n

Nella ricerca sequenziale di un elemento in un array di n elementi: l'ordinamento non ha un impatto sulla complessità della ricerca sequenziale

Nella ricerca binaria: l'array deve essere ordinato

Nella ricerca binaria: la complessità è logaritmica

Nella ricerca binaria: l'algoritmo è ricorsivo

Concetti di analisi degli algoritmi

Nella ricerca binaria, la procedura ricorsiva: lavora su sottoinsiemi dell'array

Nell'analisi di un algoritmo è importante considerare correttezza, completezza e: complessità

Un algoritmo è corretto quando: restituisce sempre una risposta corretta

Fornire la complessità dell'algoritmo corretto: significa dare almeno un tetto alla complessità del problema risolto dall'algoritmo

Problemi e soluzioni

Se l'algoritmo trovato non è il migliore per risolvere quel problema: non avremo risposto alla domanda "qual è la complessità del mio problema"

Il dato di ingresso soddisfa una certa proprietà: È un tipo di problema decisionale

Un problema di ottimizzazione: cerca una soluzione a costo minimo

Stabilire se un grafo è connesso: È un problema decisionale

Tecniche di programmazione

Nella programmazione dinamica: la soluzione viene costruita a partire da un insieme di sotto-problemi potenzialmente ripetuti

Prova a fare qualcosa, se non funziona disfala e prova a farne un'altra: È tipico del Backtrack

L'approccio bottom-up è tipico di: programmazione dinamica

La scelta migliore nell'immediata è tipica di: tecnica greedy

Combina: È una fase del divide et impera

La ricorsione: È tipica del divide et impera

Esempi e complessità

Nella torre di Hanoi con 4 dischi il numero di mosse necessarie è: 15

Una delle seguenti non è una operazione elementare: iterazione

La complessità asintotica: stima quanto aumenta il tempo di calcolo al crescere della dimensione n dell'input

Notazioni asintotiche

La notazione Theta rappresenta: un limite stretto

La notazione asintotica O: vale per ogni n maggiore o uguale ad un certo valore n con 0

Una funzione polinomiale è: O(n²)

Una funzione polinomiale è: Ω(n²)

La notazione asintotica Omega: vale per ogni n maggiore o uguale ad un certo valore n con 0

Nel logaritmo, O(n) ed Ω(n): non coincidono

Se una funzione è sia O(g(n)) che Ω(g(n)): allora è θ(g(n))

Proprietà dei limiti asintotici

La notazione asintotica Theta ammette che esistano 2 costanti c1 e c2: per ogni n maggiore o uguale ad un certo valore n con 0

La notazione asintotica O: rappresenta un limite inferiore asintotico

Il limite superiore di una espressione polinomiale è: di ordine n^k

Il limite inferiore di una espressione polinomiale è: di ordine n^k

Se il limite per n tendente all'infinito di f(n)/g(n) è 0: f(n) è O grande di g(n)

Se il limite per n tendente all'infinito di f(n)/g(n) è infinito: f(n) è Omega grande di g(n)

Se il limite per n tendente all'infinito di f(n)/g(n) è un numero finito: f(n) è Theta grande di g(n)

Complessità e diagrammi di flusso

La seguente non è una proprietà dei limiti asintotici: Sottrattiva

La 'o' piccola implica la 'O' grande: sempre

O(n·log n) è detta: complessità pseudolineare

Quale tra le seguenti ha una complessità maggiore al crescere di n: esponenziale

Diagrammi di flusso e iterazioni

Nei diagrammi di flusso, il simbolo del rombo è usato per: selezione

Nella selezione sono possibili: vero e falso

Nell'iterazione sono possibili esclusivamente: mentre, fai, per

Nella ripetizione "mentre" è solo possibile specificare