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 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 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 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 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 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 Nella ricerca binaria, la procedura ricorsiva: lavora su sottoinsiemi dell'array Nell'analisi di un algorimo è 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 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 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 bo