Informatica 3: Novità

Il compito del 14/2 avra' inizio alle ore 9:00, e durata pari a 1:45. Quindi, tolti i tempi tecnici di disposizione, distribuzione compiti e ritiro degli stessi, si finira' per le 11.

Nella lezione del 17/12 abbiamo visto gli ultimi due argomenti del corso, tabelle di hash e codifica di Huffman.

Per quanto riguarda le tabelle di hash, abbiamo visto le principali strutture (chaining e open addressing) e funzioni di hash (resto della divisione e metodo moltiplicativo).

Huffman code

from treeh import BinNode, IntlNode, LeafNode, preorder, postorder
 
def Huffman(chars, freq):
	Q = zip(freq,chars)
	Q.sort()
	while len(Q)>1 :
		print Q
		cx,x=Q.pop(0)
		cy,y=Q.pop(0)
		if not issubclass(type(x),BinNode) :
			x=LeafNode((cx,x))
		if not issubclass(type(y),BinNode) :
			y=LeafNode((cy,y))
		data=y.data[0]+x.data[0], y.data[1]+'+'+x.data[1]
		z=IntlNode(data,y,x)
		Q.append((cx+cy,z))
		Q.sort()
	return Q.pop(0)
 
 
 
def action(n):
	'''Prints the tree in Graphviz DOT language
	'''
	print id(n), '[ label="', n.data, '"];'
	try : 
		x = `id(n)`+' -> '+`id(n.left)`+';'
	except AttributeError, e : pass
	try : 
		x = `id(n)`+' -> '+`id(n.right)`+';'
	except AttributeError, e : pass
 
 
if __name__ == '__main__' :
	C=[ 'z', 'k', 'f', 'c', 'u', 'd', 'l', 'e' ]
	f=[  2,   7 ,  24,  32,  37,  42,  42, 120 ]
	T=Huffman(C,f)
 
	postorder(T,action)

Tree implementation

#!/usr/bin/python
 
class BinNode(object):
	def __init__(self,content=None):
		self.data=content
		self.left=None
		self.right=None
 
	def __getitem__(self,side):
		if side in [ 0, 'left', 'l' ] :
			return self.left
		elif side in [ 1, 'right', 'r' ] :
			return self.right
		raise KeyError, side
 
	def __setitem__(self,side,item):
		if not isinstance(item,BinNode) :
			raise TypeError, item
		if side in [ 0, 'left', 'l' ] :
			self.left = item
		elif side in [ 1, 'right', 'r' ] :
			self.right = item
		else :
			raise KeyError, side
 
	def isLeaf(self):
		return self.left and self.right
 
 
class LeafNode(BinNode):
	def __init__(self,content):
		#if not isinstance(content,int) : 
		#	raise TypeError, 'LeafNode accepts only integers'
		self.data=content
 
	def __getitem__(self,side):
		raise TypeError, 'No children in leaf nodes!'
 
	def __setitem__(self,side,child):
		raise TypeError, 'No children in leaf nodes!'
 
	def isLeaf(self):
		return True
 
class IntlNode(BinNode):
	def __init__(self,content,left=None,right=None):
		#if content not in [ '*', '+', '-', '/' ] : 
		#	raise TypeError, 'IntlNode accepts only arithmetic operators as strings'
		BinNode.__init__(self,content)
		self.left=left
		self.right=right
 
	def isLeaf(self):
		return False
 
 
def preorder(node,action,direction=['l','r']):
	'''Preorder, defaults to left to right; 
	action must be a function specific for the elements'''
	action(node)
	if not node.isLeaf() : 
		preorder(node[direction[0]],action,direction)
		preorder(node[direction[1]],action,direction)
 
def postorder(node,action,direction=['l','r']):
	'''Preorder, defaults to left to right; 
	action must be a function specific for the elements'''
	if not node.isLeaf() : 
		preorder(node[direction[0]],action,direction)
		preorder(node[direction[1]],action,direction)
	action(node)
 
def inorder(node,action,direction=['l','r']):
	'''Preorder, defaults to left to right; 
	action must be a function specific for the elements'''
	if node.isLeaf() : 
		action(node)
		return
	else :
		inorder(node[direction[0]],action,direction)
		action(node)
		inorder(node[direction[1]],action,direction)
 
 
if __name__ == '__main__' :
	def action(node):
		print node.data,
 
	root = IntlNode('*')
	root['l'] = IntlNode('+')
	root['r'] = IntlNode('/')
	root['r']['r'] = LeafNode(2)
	root['r']['l'] = LeafNode(3)
	root['l']['r'] = LeafNode(4)
	root['l']['l'] = LeafNode(5)
	preorder(root,action)
	print ''
	inorder(root,action)
	print ''
	postorder(root,action)

{{teaching:info3:huffman.tgz}|Qui}} trovate i file sorgenti con il codice relativo alla codifica di Huffman.

Materiale relativo all'esercitazione sui B-Tree:

• Indexing Trees
• Introduzione ai B-Tree
• Esercizi sui B-Tree

In questa lezione abbiamo affrontato i principali metodi di risoluzione delle serie e delle equazioni alle ricorrenze che si trovano nell'analisi di complessità degli algoritmi.

Oltre alla risoluzione delle serie aritmetiche e geometriche, abbiamo visto tre metodi di risoluzione di impiego generale:

• Induzione
• Metodi di shifting
• Teorema maestro

Una dispensa che copre gli argomenti trattati in questa lezione si trova sul sito del corso di Algoritmi e Strutture Dati.

Nella prima parte della lezione del 10/12, abbiamo introdotto il concetto di grafo, e alcuni concetti accessori:

• Vertice
• Lato/arco
• Cammino (semplice o meno)
• Ciclo (semplice o meno)
• Distanza fra vertici
• Cammino minimo fra due vertici

Abbiamo visto alcune fra le principali proprietà dei grafi, in particolare la disuguaglianza triangolare per le distanze in grafi i cui lati abbiano pesi non negativi.

Per finire, abbiamo trattato i principali algoritmi relativi al calcolo delle distanze e dei cammini minimi, e del minimum spanning tree di un grafo:

• Algoritmo di Dijkstra e Prim-Jernik-Dijkstra
• Algoritmo di Floyd
• Algoritmo di Kruskal
• Visita depth-first
• Visita breadth-first
• Ordinamento topologico (solo per grafi diretti aciclici)