Informatica 3: Novità

Lo spostamento dall'aula T.0.1 alla T.2.1 per il lunedi' e' confermato.

G.

Ho pubblicato i voti dell'ultimo appello sul Poliself. Avete tempo fino al 25/7 (mattina) per rifiutare il voto. Potete passare martedi' 22 alle 15 per la visione dei compiti.

C'e' un non iscritto (Lippolis) a cui non ho potuto registrare il voto.

Soluzione per gli esercizi 2, 3 e 5

Il testo chiede di determinare l'output del seguente programma Python:

def f(x,y):
        return x+y*2
 
def g(x,y=[1]):
        return x>y
 
a=[1,2]
b=['a','b']
 
print g(f(a,b))
print f(b,a)
print g(f(a,b),f(b,a))
 
def h(y):
        def f(x):
                return x+y
        return f
 
f=h(a)
print f(b)

La risposta corretta e':

 True
 ['a', 'b', 1, 2, 1, 2]
 False
 ['a', 'b', 1, 2]

Bisogna infatti ricordare che l'operazione di confronto si applica fra liste di qualunque lunghezza, e l'operatore * applicato ad una lista ed un numero intero n restituisce una nuova lista pari alla lista originale replicata n volte. Per seconda parte, la funzione f=h(x) esegue la somma (o la concatenazione, nel caso delle liste) fra x e l'argomento di f.

Gli ultimi due casi si risolvono applicando il teorema maestro. Il primo si svolge considerando che T(n) = T(n-3) + lg n = lg n + lg n-3 + lg n-6 … = Θ(n lg n).

Se l'albero, per essere valido, deve avere in ogni nodo un'etichetta pari alla somma delle etichette nei sottoalberi, allora e' anche vero che in ogni nodo l'etichetta deve essere pari al doppio della somma delle etichette dei figli (a meno che i figli non siano foglie). Di conseguenza, si puo' scrivere una soluzione (in Python) in questo modo:

def check(node):
        if node.isLeaf() :
                return True
        sum = 0
        for c in node.children :
                if c.isLeaf() :
                        sum+=c.value
                else :
                        sum+=c.value*2
        if sum != node.value :
                return False
        return reduce(lambda x, y: x and y, [ check(c) for c in node.children ], 1)

La complessita' di questa soluzione e' O(n) nel numero dei nodi.

Ecco una soluzione semplice del secondo esercizio:

def dup(l):
  l2=[]
  for i in l :
    l2.append(i)
    l2.append(i)
  return l2

Ci sono altri modi per esprimere lo stesso concetto, ad esempio:

def dup(l):
  return reduce(lambda x,y : x+y, [ [i]*2 for i in l ])

Questa seconda soluzione impiega una comprehension per generare, ad esempio, da [ 1, 2, 'c' ] la lista [ [1, 1] , [2,, 2], ['c', 'c'] ] che contiene la lista delle copie degli elementi. La funzione reduce applica sequenzialmente l'operazione di concatenazione agli elementi della lista prodotta, portando al risultato voluto. Notate che in questa soluzione, il ciclo viene sostituito da tipiche operazioni della programmazione funzionale.

Ecco una terza possibile soluzione:

def dup(l):
  if len(l)==0 : return []
  else : return [l[0]]*2 + dup(l[1:])

Questa soluzione rimpiazza invece il ciclo con una ricorsione. Naturalmente, si puo' scegliere un modo diverso di realizzare la ricorsione, ad esempio con una tecnica divide et impera:

def dup(l):
  if len(l)>1 :
    return dup(l[:len(l)/2])+dup(l[len(l)/2:])
  else : return l*2

Ho messo i risultati in bacheca (I-M, all'interno del DEI). Tutti quelli che non compaiono non hanno superato l'esame.

Potete passare a vedere il compito venerdi' mattina alle 10. Venerdi' pomeriggio registro.

• Molti di voi hanno sbagliato l'esercizio sul BST, usando alberi di tipo diverso.
• Gli algoritmi di ordinamento piu' semplici, come quello proposto nel compito, sono tutti O(n²). Alcuni hanno ottenuto complessita' improbabili.
• L'ambiente globale non ha un indirizzo di ritorno, dato che non e' una chiamata a funzione.
• Quasi tutte le soluzioni proposte per l'ultimo esercizio violavano uno dei due requisiti, in particolare il calcolo in O(1).

Il compito era strutturato in questo modo:

• Tre esercizi semplici, su tre argomenti fondamentali (alberi, struttura della pila delle chiamate, complessita' e algoritmi di ricerca).
• Due esercizi piu' difficili, uno su Python, uno sull'ideazione di algoritmi. Mediamente, chi ha un voto dal 18 in su' ha preso un 3.5-4 punti (su 7) sull'esercizio relativo a Python. L'ultimo esercizio e' andato decisamente male, e solo una correzione molto clemente ha portato ad una media appena inferiore a 2 su 5.

Notate che il compito era progettato per verificare la comprensione di tutti i principali argomenti del corso, ad eccezione di parallelismo e programmazione orientata agli oggetti. L'esercizio su Python mi serve, oltre a verificare la comprensione dei meccanismi di passaggio parametri, anche a verificare che abbiate provato a ri-codificare gli algoritmi visti a lezione (o almeno testarli!) – dato che, per dire, la concatenazione di liste compare in quicksort.