API 2018 06 28

Pagina 1

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 15 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 ‘<’ su A. Dati due elementi qualunque e1 e e2, diciamo che e1 è migliore di e2, se e1 < e2. Si vogliono determinare i migliori elementi dell’insieme. 1) Descrivere in modo succinto ma preciso un algoritmo che stampi i migliori 10 elementi dell’insieme (si assuma anche che N>10). 2) Valutare la complessità asintotica, in funzione di N, dell’algoritmo descritto 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 posizione 2n/3. A questo punto confronta il contenuto col carattere finale. T(n) = Θ(n2), S(n) = n La RAM memorizza la stringa, calcolandone la lunghezza con un contatore; controlla che sia divisibile per 3; calcola la…