diff --git a/lab4/chainageAvantAvecFiltrage.py b/lab4/chainageAvantAvecFiltrage.py
new file mode 100755
index 0000000..9e7e020
--- /dev/null
+++ b/lab4/chainageAvantAvecFiltrage.py
@@ -0,0 +1,166 @@
+import match
+
+##La variable globale utilsee pour signifier un ECHEC
+echec='ECHEC'
+
+##Base des faits
+##Syntax des faits [['fait1'....],...,['faitn']]
+faits = []
+
+##Base des regles
+## Syntaxe d'une regles [['condition1',...,'conditionn'],'consequence']
+regles = []
+
+## initialise les 2 bases
+def initDBs():
+    videFaits()
+    videRegles()
+
+
+## FAITS
+## vide la base des faits
+    ##faits[:] iter sur tous les elements de faits 
+def videFaits():
+    del faits[:]
+        
+
+## affiche la base des faits
+def afficheFaits():
+    for x in faits:
+        print x
+        
+
+
+## Ajoute un fait a la base des faits <=> pas deja present dans faits
+## @param fait un fait SOUS form d'une liste []        
+def ajouteFait(fait):
+    faits.append(fait)
+
+#################################################################################    
+
+## REGLES
+## vide la base des regles
+    ##faits[:] iter sur tous les elements de faits 
+def videRegles():
+    del regles[:]
+        
+#########################################################    
+
+## affiche la base des faits
+def afficheRegles():
+    for x in regles:
+        print x
+        
+#########################################################        
+        
+## Ajoute une regles a la base des regles
+## @param regle ajoute le regle a liste        
+def ajouteRegle(regle):
+    regles.append(regle)
+
+## retourne les conditions d'une regle
+## @param regle la regle
+## @ret la condition de la regle (regle[0])
+def conditionsRegle(regle):
+    return regle[0]
+
+## retourne la consequence d'une regle
+## @param regle la regle
+## @ret la consequence de la regle (regle[1])
+def consequenceRegle(regle):
+    return regle[1]
+
+## verifie que le fait verifie le liste de conditions d'une regle
+## et retourne la liste d'environemnt reuissie due au substituions ET la liste des conditions restante non verifier par fait
+## @param fait le fait ['a', ...,'b']
+## @pram conditions les condition d'une regle ['cond1',....,'condn']
+## @ret [[{environement1}, ...,{environementn}],[[cond_restant_1_1,...,cond_restant_1_k]],[cond_restant_n_1,...,cond_restant_n_k]]]
+def faitSatisfaitUneCondition(fait, conditions):
+	envs = []
+	rests = []
+	for c in conditions:
+		rc = match.match(fait, c)
+		if rc != echec:
+			envs.append(rc)
+			rl = conditions[:]
+			rl.remove(c)
+			rests.append(rl)
+	return [envs, rests]
+
+## verife la validite de la condition en esseyant toues les substituions par les faits de la base
+## @param condition la condition a verifier
+## @param liste_environements [{...},...,{...}]
+## @param faitsDB la liste des faits [[],...,[]]
+## @ret la liste des environement possibles [{},...,{}], vide si aucun
+def satisfaitUneCondition (condition, listeEnvironements):
+	r = []
+	for f in faits:
+		for e in listeEnvironements:
+			rc = match.match(f, condition, e)
+			#if rc == echec:
+			#	rc = {}
+			# XXX: personal idea
+			if rc != echec:
+				r.append(rc)
+	return r
+
+## Verifie qu'une liste de conditions peut etre verifier par les environements existants
+## @param conditions la liste de condition a verifier [[],...,[]] 
+## @param environement {...}
+## @param faitsDB la liste des faits [[],...,[]]
+## @ret la liste des environement possibles [{},...,{}]; [] si aucun
+def satisfaitConditions(conditions,environement):
+	envlist = [environement]
+	for c in conditions:
+		if envlist == []:
+			return envlist
+		envlist = satisfaitUneCondition(c, envlist)
+	return envlist
+
+## instantie la consequence d'une regle et retourne une liste de nouveau fait par environemt
+## @param proposition la proposition
+## @param listeEnvironements la liste des environements [{},....,{}]
+## @ret une liste de nouveau faits ['fait1',...,'fait2']
+def instantieVariables(proposition, listeEnvironements):
+	r = []
+	for e in listeEnvironements:
+		r.append(match.substitueVariables(proposition, e))
+	return r
+
+## fait le chainage avant avec filtrage
+## @param regles les regles a verifer
+## @param faits_initiaux les faits initiaux
+## @ret la liste des faits deduits
+def chainageAvantAvecFiltrage(regles, faits_initiaux):
+	Q = faits[:]
+
+	while Q:
+		q = Q[0]
+		Q = Q[1:]
+		if q not in faits:
+			ajouteFait(q)
+			afficheFait(q)
+		for r in regles:
+			c = conditionsRegle(r)
+			es = match.filtrage(q, c)
+			if es != echec:
+				for e in es:
+					e2 = satisfaitConditions(c, e)
+					n = instantieVariables(consequenceRegle(r), e2)
+					if n not in faits:
+						Q.append(n)
+
+
+#execfile("testFaitSatisfaitUneCondition.py")
+#execfile("testSatisfaitUneCondition.py")
+#execfile("testSatisfaitConditions.py")
+#execfile("testInstantieVariables.py")
+execfile("impots2.py")
+chainageAvantAvecFiltrage(regles,faits)
+
+diff = faits[:]
+for item in diff:
+	if item in result:
+		diff.remove(item)
+
+print diff
diff --git a/lab4/impots2.py b/lab4/impots2.py
new file mode 100755
index 0000000..c1e796f
--- /dev/null
+++ b/lab4/impots2.py
@@ -0,0 +1,76 @@
+
+
+##initialise la DB
+print "|+| Chargement du fichier impots2" 
+initDBs()
+
+##ajoute des faits
+print "\tAjout des faits",
+ajouteFait(['add','0','0','0','0'])
+ajouteFait(['add','100','100','0','0'])
+ajouteFait(['add','100','0','100','0'])
+ajouteFait(['add','200','100','100','0'])
+ajouteFait(['add','200','0','200','0'])
+ajouteFait(['add','300','100','200','0'])
+ajouteFait(['add','50','0','0','50'])
+ajouteFait(['add','150','100','0','50'])
+ajouteFait(['add','150','0','100','50'])
+ajouteFait(['add','250','100','100','50'])
+ajouteFait(['add','250','0','200','50'])
+ajouteFait(['add','350','100','200','50'])
+ajouteFait(['add','100','0','0','100'])
+ajouteFait(['add','200','100','0','100'])
+ajouteFait(['add','200','0','100','100'])
+ajouteFait(['add','300','100','100','100'])
+ajouteFait(['add','300','0','200','100'])
+ajouteFait(['add','400','100','200','100'])
+
+##Paul
+ajouteFait(['bas-salaire', 'Paul'])
+ajouteFait(['loyer', 'Paul'] )
+ajouteFait(['enfants', 'Paul'])
+ajouteFait(['long-trajet', 'Paul'])
+
+##Marc
+ajouteFait(['moyen-salaire', 'Marc'])
+ajouteFait(['loyer', 'Marc'] )
+ajouteFait(['enfants', 'Marc'])
+ajouteFait(['long-trajet', 'Marc'])
+
+##Jean
+ajouteFait(['haut-salaire', 'Jean'])
+ajouteFait(['pas-de-loyer', 'Jean'] )
+ajouteFait(['pas-d-enfants', 'Jean'])
+ajouteFait(['long-trajet', 'Jean'])
+
+print "\tOK"
+##afficheFaits()
+
+##ajoute des regles
+print "\tAjout des regles",
+
+##Reduction enfants
+ajouteRegle([[['pas-d-enfants', '?x']],['reduc-enfant', '0','?x']])
+ajouteRegle([[['enfants', '?x']],['reduc-enfant', '100','?x']])
+
+##Reduction loyer
+ajouteRegle([[['bas-salaire', '?x'],['loyer', '?x']],['reduc-loyer', '200', '?x']])
+ajouteRegle([[['moyen-salaire', '?x'],['loyer', '?x']],['reduc-loyer', '100', '?x']])
+ajouteRegle([[['haut-salaire', '?x'],['loyer', '?x']],['reduc-loyer', '0', '?x']])
+ajouteRegle([[['bas-salaire', '?x'],['loyer', '?x']],['reduc-loyer', '200', '?x']])
+ajouteRegle([[['pas-de-loyer', '?x']],['reduc-enfant', '0','?x']])
+
+##Reduction transport
+ajouteRegle([[['petit-trajet', '?x']],['reduc-trajet', '0', '?x']])
+ajouteRegle([[['reduc-enfant', '0','?x'],['long-trajet', '?x']],['reduc-trajet', '100', '?x']])
+ajouteRegle([[['reduc-loyer', '0','?x'],['long-trajet', '?x']],['reduc-trajet', '100', '?x']])
+ajouteRegle([[['reduc-enfant', '100','?x'],['reduc-loyer', '100', '?x'],['long-trajet', '?x']],['reduc-trajet', '50', '?x']])
+ajouteRegle([[['reduc-enfant', '100','?x'],['reduc-loyer', '200', '?x'],['long-trajet', '?x']],['reduc-trajet', '0', '?x']])
+
+##Reduction totale
+ajouteRegle([[['reduc-enfant', '?a','?x'],['reduc-loyer', '?b', '?x'],['reduc-trajet','?c', '?x'],['add','?res','?a','?b','?c'] ],['reduc', '?res', '?x']])
+print "\tOK"
+#afficheRegles()
+
+##result
+result = [['add', '0', '0', '0', '0'], ['add', '100', '100', '0', '0'], ['add', '100', '0', '100', '0'], ['add', '200', '100', '100', '0'], ['add', '200', '0', '200', '0'], ['add', '300', '100', '200', '0'], ['add', '50', '0', '0', '50'], ['add', '150', '100', '0', '50'], ['add', '150', '0', '100', '50'], ['add', '250', '100', '100', '50'], ['add', '250', '0', '200', '50'], ['add', '350', '100', '200', '50'], ['add', '100', '0', '0', '100'], ['add', '200', '100', '0', '100'], ['add', '200', '0', '100', '100'], ['add', '300', '100', '100', '100'], ['add', '300', '0', '200', '100'], ['add', '400', '100', '200', '100'], ['bas-salaire', 'Paul'], ['loyer', 'Paul'], ['enfants', 'Paul'], ['long-trajet', 'Paul'], ['moyen-salaire', 'Marc'], ['loyer', 'Marc'], ['enfants', 'Marc'], ['long-trajet', 'Marc'], ['haut-salaire', 'Jean'], ['pas-de-loyer', 'Jean'], ['pas-d-enfants', 'Jean'], ['long-trajet', 'Jean'], [['reduc-loyer', '200', 'Paul']], [['reduc-enfant', '100', 'Paul']], [['reduc-loyer', '100', 'Marc']], [['reduc-enfant', '100', 'Marc']], [['reduc-enfant', '0', 'Jean']]]
diff --git a/lab4/match.py b/lab4/match.py
new file mode 100755
index 0000000..ef62202
--- /dev/null
+++ b/lab4/match.py
@@ -0,0 +1,189 @@
+# -*- encoding:iso-8859-15  -*-
+#################################################################################
+#################################################################################
+
+##La variable globale utilsee pour signifier un ECHEC
+echec='ECHEC'
+
+################################################################################
+## retourne True si le symbole est une liste (cad: [])
+## @param x le symbole a tester
+## @ret True <=> x est une liste
+################################################################################
+def testeListe(x):
+    return type(x)==type([])
+################################################################################
+
+################################################################################
+## retourne True si le symbole est une liste vide (cad: [])
+## @param x le symbole a tester
+## @ret True <=> x est une liste vide
+################################################################################
+def testeListeVide(x):
+    return (type(x)==type([]) and len(x)==0)
+################################################################################
+
+###############################################################################
+##retourne True si le symbole est un atome (i.e.: ' ')
+## @param x le symbole a tester
+## @ret True <=> x est un atome
+#################################################################################
+################################################################################
+def testeAtome(x):
+    return type(x)==type('')
+################################################################################
+
+################################################################################
+## retourne True si le symbole est une variable; i.e.:commence par ?
+## @param x le symbole � tester
+## @ret True <=> x est une variable
+## '?toto' => True
+## 'toto' => False
+################################################################################
+def testeVariable(x):
+    return (testeAtome(x) and x[0]=='?')
+################################################################################
+
+################################################################################
+## retourne le symbol x dans une liste
+## @param x le symbole 
+## @ret [x]
+################################################################################
+def retourneListe(x):
+    return [x]
+###############################################################################
+
+################################################################################
+## retourne True si le symbole est une substitution
+## @param x le symbole � tester
+## @ret True <=> x est une substitution
+################################################################################
+def testeSub(x):
+    return type(x)==type({})
+################################################################################
+
+###############################################################################
+## construit et retourne une substitution entre une variable et une expression
+## @param variable la variable
+## @param datum pr�position sans variable
+## @ret une substitution {variable:datum}
+################################################################################
+def construitSub(variable, datum):
+	return {variable: datum}
+################################################################################
+
+###############################################################################
+## retourne la variable d'une substitution
+## @param substitution la substitution
+## @ret la variable de la substitution
+################################################################################
+def retourneVariable(sub):
+	return sub.keys()[0]
+################################################################################
+
+###############################################################################
+## retourne la valeur d'une substitution
+## @param substitution la substitution
+## @ret la valeur de la substitution
+################################################################################
+def retourneValeur(sub):
+	return sub.values()[0]
+################################################################################
+
+###############################################################################
+## retourne la substitution associee a une variable, c�d: {variable:definition_de_la_variable}
+## @param variable la variable
+## @param substitutions la liste des substitutions
+## @ret la substitution associee � la variable si elle existe dans substituions, sinon retourne False
+################################################################################
+def trouveSub(variable, subs):
+	if testeSub(subs) and subs.has_key(variable):
+		return {variable: subs[variable]}
+	else:
+		return False
+################################################################################
+
+###############################################################################
+## construit l'union de deux substitutions
+## @param substitution1 la premiere substitution
+## @param substitution2 la deuxieme substitution
+## @ret substitution1 UNION substitution2; echec if substitution1 ou substitution2 ne sont pas des substitutions
+###############################################################################
+def unionSub(sub1,sub2):
+	if testeSub(sub1) and testeSub(sub2):
+		sub1.update(sub2)
+		return sub1
+	else:
+		return echec
+################################################################################ 
+    
+###############################################################################
+## retourne la proposition avec les variables remplacees par leurs valeurs
+## @param pattern la proposition (contient des variables, atomes,... sous forme [' ',' ', ' '] OU ' ' ou ['[]'...])
+## @param substitutions la liste des substitutions {a:b, c:d,...}
+## @ret la proposition avec les variables remplacees par leur valeurs
+################################################################################
+def substitueVariables(pattern , subs):
+	if testeListe(pattern):
+		return [substitueVariables(x, subs) for x in pattern]
+	else:
+		z = trouveSub(pattern, subs)
+		#return subs.get(pattern, pattern)
+		if z:
+			return retourneValeur(z)
+		else:
+			return pattern
+################################################################################    
+
+################################################################################
+## filtrage
+## @param datum la propopsition SANS variable
+## @param pattern la proposition AVEC variables
+## @ret les substitution  <=> le filtrage a reussi: {'?x':'a',...}, 'ECHEC' sinon
+################################################################################
+def filtrage(datum,pattern):
+	if pattern == [] and datum == []:
+		return {}
+	if pattern == [] or datum == []:
+		return echec
+	if testeAtome(pattern):
+		if pattern == datum:
+			return {}
+		else:
+			if testeVariable(pattern):
+				return {pattern: datum}
+			else:
+				return echec
+	else:
+		if testeAtome(datum):
+			return echec
+	
+	f1 = datum[0]
+	t1 = datum[1:]
+	f2 = pattern[0]
+	t2 = pattern[1:]
+	z1 = filtrage(f1, f2)
+	if z1 == echec:
+		return echec
+	g1 = t1
+	g2 = substitueVariables(t2, z1)
+	z2 = filtrage(g1, g2)
+	if z2 == echec:
+		return echec
+	return unionSub(z1, z2)
+
+################################################################################ 
+
+#################################################################################
+## fait le pattern macthing
+## @param datum un datum
+## @param pattern une proposition pouvant contenir des variables
+## @param environement un environement {}, valeur par defaut={}
+## @ret filtrage(proposition,datum) si OK else FAIL
+#################################################################################        
+def match(datum,pattern, env={}):
+	fs = filtrage(substitueVariables(datum, env), substitueVariables(pattern, env))
+	if fs == echec:
+		return echec
+	return unionSub(fs, env)
+################################################################################
diff --git a/lab4/match.pyc b/lab4/match.pyc
new file mode 100644
index 0000000..331eb64
--- /dev/null
+++ b/lab4/match.pyc
Binary files differ
diff --git a/lab4/matchTemplate.pyc b/lab4/matchTemplate.pyc
new file mode 100644
index 0000000..e08ac59
--- /dev/null
+++ b/lab4/matchTemplate.pyc
Binary files differ
diff --git a/lab4/testFaitSatisfaitUneCondition.py b/lab4/testFaitSatisfaitUneCondition.py
new file mode 100755
index 0000000..ec83fdd
--- /dev/null
+++ b/lab4/testFaitSatisfaitUneCondition.py
@@ -0,0 +1,4 @@
+print "test faitSatisfaitUneCondition"
+print faitSatisfaitUneCondition(['pere','jean','paul'],[['pere','?x','?y'],['pere','?y','?z']])
+print faitSatisfaitUneCondition(['pere','jean','paul'],[['fils','?x','?y'],['pere','?y','?z'],['mere','?x','?y']])
+print faitSatisfaitUneCondition(['tonton','jean','paul'],[['fils','?x','?y'],['pere','?y','?z'],['mere','?x','?y']])
diff --git a/lab4/testFiltrage.py b/lab4/testFiltrage.py
new file mode 100755
index 0000000..49f9378
--- /dev/null
+++ b/lab4/testFiltrage.py
@@ -0,0 +1,34 @@
+print "Test fonction filtrage(daum,pattern)"
+j=filtrage('vincent', '?x')
+print "\t",j
+print "\t",{'?x':'vincent'}
+a=filtrage(['vincent', 'est un', 'doctorant'],['?x', 'est un', 'doctorant'] )
+print "\t",a
+print "\t",{'?x':'vincent'}
+b=filtrage(['vincent', 'est un', 'doctorant'],['?x', 'est un', '?y'])
+print "\t",b
+print "\t",{'?x':'vincent', '?y':'doctorant'}
+c=filtrage(['vincent', 'est un', 'doctorant'] , ['vincent', 'est un', 'doctorant'])
+print "\t",c
+print "\t",{}
+d=filtrage(['vincent', 'est un', 'doctorant',['vincent', 'est un', 'doctorant']] , ['vincent', 'est un', 'doctorant',['vincent', 'est un', 'doctorant']])
+print "\t",d
+print "\t",{}
+e=filtrage(['vincent', 'est un', 'doctorant'],['vincent', 'est un', 'doctorant',['vincent', 'est un', 'doctorant']])
+print "\t",e
+print "\t",echec
+f=filtrage(['vincent', 'est un', 'doctorant'] , ['paolo', 'est un', 'doctorant'])
+print "\t",f
+print "\t",echec
+g=filtrage(['vincent', 'est un','doctorant','paolo', 'est un', 'doctorant'],['?x', 'est un', '?y','?z', 'est un', '?v'])
+print "\t",g
+print "\t",{'?x':'vincent', '?y':'doctorant','?z':'paolo', '?v':'doctorant'}
+h=filtrage(['vincent', 'est un', 'vincent'],['?x', 'est un', '?x'])
+print "\t",h
+print "\t",{'?x':'vincent'}
+i=filtrage(['vincent', 'est un', 'doctorant'],['?x', 'est un', '?x'])
+print "\t",i
+print "\t",echec
+j=filtrage('vincent', '?x')
+print "\t",j
+print "\t",{'?x':'vincent'}
diff --git a/lab4/testInstantieVariables.py b/lab4/testInstantieVariables.py
new file mode 100644
index 0000000..d250c87
--- /dev/null
+++ b/lab4/testInstantieVariables.py
@@ -0,0 +1,2 @@
+print "Test instantieVariables"
+print instantieVariables(['?x',['?y', '?z']],[{'?x':'X','?y':'Y'},{'?x':'X','?z':'Z'}])
diff --git a/lab4/testMatch.py b/lab4/testMatch.py
new file mode 100755
index 0000000..b6d2c6b
--- /dev/null
+++ b/lab4/testMatch.py
@@ -0,0 +1,37 @@
+print "Test fonction match(daum,proposition)"
+a=match(['vincent', 'est un', 'doctorant'],['?x', 'est un', 'doctorant'])
+print "\t",a
+print "\t",{'?x':'vincent'}
+b=match(['vincent', 'est un', 'doctorant'],['?x', 'est un', '?y'])
+print "\t",b
+print "\t",{'?x':'vincent','?y':'doctorant'}
+a=match(['vincent', 'est un', 'doctorant'] , ['vincent', 'est un', 'doctorant'])
+print "\t",a
+print "\t",{}
+b=match(['vincent', 'est un', 'doctorant'],['?x', 'est un', '?x'])
+print "\t",b
+print "\t",echec
+f=match( ['foo', 'jean', ['marc', 'bar', 'jean']],['foo', '?x', ['?y', 'bar', '?x']])
+print "\t",f
+print "\t",{'?x':'jean','?y':'marc'}
+g=match(['foo', 'jean', ['marc', 'bar', 'paul']],['foo', '?x', ['?y', 'bar', '?x']])
+print "\t",g
+print "\t",echec
+
+c=match(['vincent', 'est un', 'doctorant'],['?x', 'est un', 'doctorant'] , {'?y':'doctorant'})
+print "\t",c
+print "\t",{'?x':'vincent','?y':'doctorant'}
+c=match(['vincent', 'est un', 'doctorant'],['?x', 'est un', '?y'] , {'?y':'doctorant'})
+print "\t",c
+print "\t",{'?x':'vincent','?y':'doctorant'}
+d=match(['vincent', 'est un', 'doctorant'], ['?x', 'est un','doctorant'] , 'ECHEC')
+print "\t",d
+print "\t",echec
+e=match('vincent','?x',  'ECHEC')
+print "\t",e
+print "\t",echec
+e=match( 'vincent', '?x',{})
+print "\t",e
+print "\t",{'?x':'vincent'}
+
+
diff --git a/lab4/testSatisfaitConditions.py b/lab4/testSatisfaitConditions.py
new file mode 100755
index 0000000..4409da1
--- /dev/null
+++ b/lab4/testSatisfaitConditions.py
@@ -0,0 +1,9 @@
+print "test satisfaitConditions"
+faits=[['a', 'and', 'b'],['b', 'and', 'b']]
+print satisfaitConditions([['?x', 'and','?y'],['?x', 'and','?x']],{'?y':'b'})
+
+faits=[['a', 'and', 'b'],['b', 'and', 'b']]
+print satisfaitConditions([['?z', 'and','?y'],['?x', 'and','?z']],{'?y':'b'})
+
+faits=[['a', 'and', 'b'],['b', 'and', 'c']]
+print satisfaitConditions([['?x', 'and','?y'],['?x', 'and','?x']],{'?y':'b'})
\ No newline at end of file
diff --git a/lab4/testSatisfaitUneCondition.py b/lab4/testSatisfaitUneCondition.py
new file mode 100755
index 0000000..f5f5c88
--- /dev/null
+++ b/lab4/testSatisfaitUneCondition.py
@@ -0,0 +1,3 @@
+print "test satisfaitUneCondition"
+faits=[['a', 'and', 'b'],['b', 'and', 'b']]
+print satisfaitUneCondition(['?x', 'and','b'],[{'?y':'b'}])
diff --git a/lab4/testSubstitueVariables.py b/lab4/testSubstitueVariables.py
new file mode 100755
index 0000000..64298b4
--- /dev/null
+++ b/lab4/testSubstitueVariables.py
@@ -0,0 +1,19 @@
+print "Test fonctions substitueVariables" 
+print "\t",substitueVariables(['?x', 'est un', 'doctorant'] , {})
+print "\t", ['?x', 'est un', 'doctorant']
+print "\t",substitueVariables(['?x', 'est un', 'doctorant'] , {'?y':'michael'})
+print "\t", ['?x', 'est un', 'doctorant']
+print "\t",substitueVariables(['?x', 'est un', 'doctorant'] , {'?x':'vincent','?y':'michael','?z':'paolo'})
+print "\t", ['vincent', 'est un', 'doctorant']
+print "\t",substitueVariables(['?w', 'est un', 'doctorant'] , {'?x':'vincent','?y':'michael','?z':'paolo'})
+print "\t", ['?w', 'est un', 'doctorant']
+print "\t",substitueVariables(['?x', 'et', '?z', 'sont', 'doctorants'] , {'?x':'vincent','?y':'michael','?z':'paolo'})
+print "\t", ['vincent', 'et', 'paolo', 'sont', 'doctorants']
+print "\t",substitueVariables(['?x', 'est un', ['?x']] , {'?x':'vincent','?y':'michael','?z':'paolo'})
+print "\t", ['vincent', 'est un', ['vincent']]
+print "\t",substitueVariables(['?x', 'est un', ['?a']] , {'?x':'vincent','?y':'michael','?z':'paolo'})
+print "\t", ['vincent', 'est un', ['?a']]
+print "\t",substitueVariables('?x', {'?x':'vincent','?y':'michael','?z':'paolo'})
+print "\t", 'vincent'
+print "\t",substitueVariables('doctorant', {'?x':'vincent','?y':'michael','?z':'paolo'})
+print "\t", 'doctorant'
diff --git a/lab4/testUnificateur.py b/lab4/testUnificateur.py
new file mode 100755
index 0000000..5ad34d3
--- /dev/null
+++ b/lab4/testUnificateur.py
@@ -0,0 +1,10 @@
+print "Test fonctions unificateur" 
+print "\t",unifcation(['?x', 'is a', 'doctorant'], ['vincent', 'is a', 'doctorant'])
+print "\t",unifcation(['vincent', 'is a', 'doctorant'],['?x', 'is a', 'doctorant'])
+print "\t",unifcation(['vincent', 'is a', '?y'],['?x', 'is a', 'doctorant'])
+print "\t",unifcation(['vincent', 'is a', 'doctorant'],['vincent', 'is a', 'doctorant'])
+print "\t",unifcation(['vincent', 'is a', 'doctorant'],['micheal', 'is a', 'doctorant'])
+print "\t",unifcation(['foo', '?x', ['?y', 'bar', 'jean']],['foo', 'jean', ['marc', 'bar', '?z']])
+print "\t",unifcation(['foo', '?x', ['?y', 'bar', 'jean']],['foo', 'jean', ['marc', 'bar', '?x']])
+print "\t",unifcation(['foo', '?x', ['?y', 'bar', 'paul']],['foo', 'jean', ['marc', 'bar', '?x']])
+print "\t",unifcation(['frere', '?x', '?y'],['frere', '?y', '?z'],{'?z':'?x'})
\ No newline at end of file
diff --git a/lab4/testUnifit.py b/lab4/testUnifit.py
new file mode 100755
index 0000000..a217f00
--- /dev/null
+++ b/lab4/testUnifit.py
@@ -0,0 +1,10 @@
+print "Test fonctions unifit" 
+print "\t",unifit(['?x', 'is a', 'doctorant'], ['vincent', 'is a', 'doctorant'])
+print "\t",unifit(['vincent', 'is a', 'doctorant'],['?x', 'is a', 'doctorant'])
+print "\t",unifit(['vincent', 'is a', '?y'],['?x', 'is a', 'doctorant'])
+print "\t",unifit(['vincent', 'is a', 'doctorant'],['vincent', 'is a', 'doctorant'])
+print "\t",unifit(['vincent', 'is a', 'doctorant'],['micheal', 'is a', 'doctorant'])
+print "\t",unifit(['foo', '?x', ['?y', 'bar', 'jean']],['foo', 'jean', ['marc', 'bar', '?z']])
+print "\t",unifit(['foo', '?x', ['?y', 'bar', 'jean']],['foo', 'jean', ['marc', 'bar', '?x']])
+print "\t",unifit(['foo', '?x', ['?y', 'bar', 'paul']],['foo', 'jean', ['marc', 'bar', '?x']])
+print "\t",unifit(['p', '?x', ['f', '?y']],['p', ['f','a'], '?x'])
diff --git a/lab4/unificateur.py b/lab4/unificateur.py
new file mode 100755
index 0000000..24c8ae0
--- /dev/null
+++ b/lab4/unificateur.py
@@ -0,0 +1,169 @@
+#################################################################################
+#################################################################################
+
+echec='ECHEC'
+################################################################################
+## retourne True si le symbole est une liste (cad: [])
+## @param x le symbole a tester
+## @ret True <=> x est une liste
+################################################################################
+def testeListe(x):
+    return type(x)==type([])
+################################################################################
+
+################################################################################
+## retourne True si le symbole est une liste vide (cad: [])
+## @param x le symbole a tester
+## @ret True <=> x est une liste vide
+################################################################################
+def testeListeVide(x):
+    return (type(x)==type([]) and len(x)==0)
+################################################################################
+
+###############################################################################
+##retourne True si le symbole est un atome (i.e.: ' ')
+## @param x le symbole a tester
+## @ret True <=> x est un atome
+#################################################################################
+################################################################################
+def testeAtome(x):
+    return type(x)==type('')
+################################################################################
+
+################################################################################
+## retourne le symbol x dans une liste
+## @param x le symbole 
+## @ret [x]
+################################################################################
+def retourneListe(x):
+    return [x]
+###############################################################################
+
+################################################################################
+## retourne True si le symbole est une substitution
+## @param x le symbole � tester
+## @ret True <=> x est une substitution
+################################################################################
+def testeSubstitution(x):
+    return type(x)==type({})
+################################################################################
+
+################################################################################
+## retourne True si le symbole est une variable; i.e.:commence par ?
+## @param x le symbole � tester
+## @ret True <=> x est une variable
+## '?toto' => True
+## 'toto' => False
+################################################################################
+def testeVariable(x):
+    return (testeAtome(x) and x[0]=='?')
+################################################################################
+
+
+###############################################################################
+## construit et retourne une substitution entre une variable et une expression
+## @param variable la variable
+## @param datum pr�position sans variable
+## @ret une substitution {variable:datum}
+################################################################################
+def construitSubstitution(variable, datum):
+    ...
+################################################################################
+
+###############################################################################
+## retourne la variable d'une substitution
+## @param substitution la substitution
+## @ret la variable de la substitution
+################################################################################
+def retourneVariable(substituion):
+    ...
+################################################################################
+
+###############################################################################
+## retourne la valeur d'une substitution
+## @param substitution la substitution
+## @ret la valeur de la substitution
+################################################################################
+def retourneValeur(substituion):
+    ...
+################################################################################
+
+###############################################################################
+## retourne la substitution associ� une variable
+## @param variable la variable
+## @param substituions la liste des substituion
+## @ret la substitution associ� � la varibale si elle existe, sinon retourn False
+################################################################################
+def trouveSubstitution(variable, substitutions):
+    ...
+################################################################################
+    
+########################..#######################################################
+## verifie que la variable est dans les substitutions
+## @param variable la variable
+## @param substituions la liste des substituion
+## @ret True <=> variable est dans les substitutions; else False
+################################################################################
+def variableDansSubstitutions(variable, substitutions):
+    ...
+################################################################################
+
+###############################################################################
+## construit l'union de deux substitutions
+## @param substitution1 la premiere substitution
+## @param substitution2 la deuxieme substitution
+## @ret substitution1 UNION substitution2; echec if substitution1 ou substitution2 ne sont pas des substitutions
+###############################################################################
+def unionSubstitution(substitution1,substitution2):
+    ...
+###############################################################################
+## retourne la proposition avec les variables remplacees par leurs valeurs
+## @param pattern la proposition (contient des variables, atomes,... sous forme [' ',' ', ' '] OU ' ' ou ['[]'...])
+## @param substitutions la liste des substitutions {a:b, c:d,...}
+## @ret la proposition avec les variables remplacees par leur valeurs
+################################################################################
+def substitueVariables(pattern , substitutions):  
+    ## test si on a pattern est un atome
+    if testeAtome(pattern):
+        if testeVariable(pattern) and substitutions.has_key(pattern):
+            return substitueVariables(retourneValeur(trouveSubstitution(pattern,substitutions)),substitutions)
+    else:
+        for x in pattern[:]:
+            pattern.append(substitueVariables(x , substitutions))
+            pattern.pop(0)            
+    return pattern
+#####################################################################    
+
+###############################################################################
+## fait l'unification entre deux proposition pass�es en parametres
+## ATTENTION Les propositions peuvent contenire des variables
+## @param proposition1 proposition 1 avec variable
+## @param proposition2 porposition 2 avec variable  
+## @ret substitution dans un dico is le filtrage reussi : {'?x':'a',...}, 'FAIL' sinon
+###############################################################################
+def unifit(proposition1, proposition2):
+    ...
+                    
+###############################################################################
+
+################################################################################
+## fait l'unification entre deux proposition pass�es en parametres
+## ATTENTION Les propositions peuvent contenire des variables
+## @param proposition1 proposition 1 avec variable
+## @param proposition2 porposition 2 avec variable
+## @param �nvironement un environement {'?x':'a',...}   
+## @ret substitution dans un dico is le filtrage reussi : {'?x':'a',...}, 'ECHEC' sinon
+###############################################################################
+def unifcation(proposition1, proposition2, environement=None):
+    if environement is None:
+        environement={}
+    if environement==echec:
+        return echec
+    else :
+        proposition1 = substitueVariables(proposition1,environement)
+        proposition2 = substitueVariables(proposition2,environement)
+        return unionSubstitution(environement,unifit(proposition1, proposition2))
+##############################################################################
+execfile("testSubstitueVariables.py")
+execfile("testUnifit.py")
+execfile("testUnificateur.py")