Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

28 Giugno 2018 In vista del prossimo appello di Algoritmi e principi dell’informatica si propongono i seguenti esercizi da completare in 1 ora e 1 5 minuti. Esercizio 1 (punti 7 ) Si descrivano una MT a nastro singolo e una macchina RAM che riconoscono il linguaggio fatto da stringhe con lunghezza n divisibile per 3 su alfabeto {0, 1}, in cui l'ultimo carattere e quello in posizione 2n/3 sono uguali. Se ne valutino le complessità spaziali e temporali con tutti i criteri di costo applicabili. Esercizio 2 (Punti 9 ) Si consideri un insieme di N elementi diversi tra loro appartenenti a un insieme A . E’ definita una relazione d’ordine totale ‘10). 2) Valutare la complessità asintotica, in funzione di N , dell’algoritmo d escritto al punto 1. Si consideri ora, in aggiunta, un intero positivo k . 3) Descrivere in modo succinto ma preciso un algoritmo che stampi i migliori k elementi dell’insieme (si assuma anche che N > k ). 4) Valutare la complessità asintotica, in funzione di N e k , dell’algoritmo descritto al punto 3. Tracce di soluzioni Esercizio 1 La MT a nastro singolo fa una serie di n scansioni dell’intero nastro marcando da sinistra 2 caselle e da destra 1; la lunghezza è divisibile per 3 se l’ultima casella da destra marcata è adiacente all’ultima casella da sinistra, che identifica la p osizione 2n/3. A questo punto confronta il contenuto col carattere finale. T(n) = Θ (n 2 ), S(n) = n La RAM memorizza la stringa, calcolandone l a lunghezza con un contatore; control la che sia divisibile per 3; calcola la posizione 2n/3 e ne confronta il contenuto con quello dell’ultima . Costo costante: T(n) = Θ (n), S(n) = Θ (n) Costo logaritmico: T(n) = Θ (n log n), S(n) = Θ (n + log n) = Θ (n) Esercizio 2 Una prima semplice so luzione consiste nell’ordinare l’insieme degli N elementi secondo l’ordinamento indotto da