Enseignant des groupes de TP 1A et 1B : Philippe MARTIN
(9*2h ; à la suite des 3*2h de Jean-Paul MORILLON)
Cette page ( http://www.phmartin.info/cours/pSage/ ) indique des liens ou
informations complémentaires
non inclus dans la page Moodle de ce cours.
Serveur Bloc-note Sage à utiliser pour les TPs :
http://10.230.0.93/home/admin/
(accessible depuis les réseaux de l'université ou par VPN ;
pour le VPN, utilisez
cette procédure)
L2_Math<groupID>_Sage_TP<NumTP>_<NOM1>_<Prenom1>_<NOM2>_<Prenom2>
Exemple:L2_Math1a_Sage_TP4_CABRE-MARTIN_Philippe-Andre
(utilisez '-' dans les (pré-)noms composés)
L2_Maths_SAGE_TP4_CABRÉ MARTIN_Philippe_Andre' //trouvez les 7 erreurs !
L2_Math1a_Sage_TP4_MARTIN_Philippe_complet
Page Web relative à Python dans le cours
"Programmes et Algorithmes" (L1 IEEA S1IN102).
substractionGame_dictNextNodes= dict([(i, [i-1,i-2]) for i in range(2,24)])
substractionGame_dictNextNodes.update({1:[0]})
substractionGame_dictNextNodes.update({0:[]})
def mex_complexAndInefficientVersion (arrayOfIntegers):
if len(arrayOfIntegers)==0: return 0
nMax= max(arrayOfIntegers) #or: t= sorted(arrayOfIntegers); max=t[-1] #gets the max
sortedArrayOfIntegers= [i for i in range(0,nMax+2) #+2: +1 since range removes one +1
if i not in arrayOfIntegers] # +1 since "mex: Minimum EXcluded"
return sortedArrayOfIntegers[0] #the min element of sortedArrayOfIntegers: the first
def mex_simpleButInefficient (arrayOfIntegers):
min= 0 #the inefficiency comes from the fact that "in" (a loop) is called within the test
while min in arrayOfIntegers: min+= 1 # a "while" (another loop)
return min
def mex (arrayOfIntegers):
min= 0
for i in arrayOfIntegers: #only 1 loop here
if (i==min): min+= 1
return min
print(mex([])) #0
print(mex([0,0])) #1
print(mex([0,1,2,3,5])) #4
def grundy_simpleButInefficientVersion (game_dictNextNodes, nodeKey): #nodeKey: "v" in the TP
#for each game/rel and each nodeKey x in V=domain(R),
# if x is a sink, grundy(x) = 0 #this case is actually also covered in the next line
# else grundy(x) = mex( {grundy(y) : y ∈ V and x R y} )
nodeKey_nextNodes= game_dictNextNodes[nodeKey]
arrayOfGrundyOfEachNextNode= [grundy_simpleButInefficientVersion(game_dictNextNodes,k)
for k in nodeKey_nextNodes] #[] if nodeKey_nextNodes==[]
return(mex(arrayOfGrundyOfEachNextNode)) #mex([])==0 so no need for a special case for sinks
Stock= {} #every variable must be declared/initialized
#depth=0: first called with depth==0
def grundy_efficient (game_dictNextNodes, nodeKey, depth=0): #grundy_archive
global Stock #Stock is a global variable used for storing the results of this
# recursive function to re-calculating them again and again
nodeKey_nextNodes= game_dictNextNodes[nodeKey]
if depth==0: #if this is the first call of this function then
Stock= {} # 1) empty/re-initialize Stock between each game simulation
arrayOfGrundyOfEachNextNode= [grundy_efficient(game_dictNextNodes,k,depth+1) # 2) ... (needed later);
for k in nodeKey_nextNodes] # 2) no need to store here since
else: # it will not be reused
if nodeKey in Stock.keys(): #if an arrayOfGrundyOfEachNextNode has already been calculated and stored
arrayOfGrundyOfEachNextNode= Stock[nodeKey] #then use the saved list instead of re-calculating it
else: #else calculate this list and store it for future uses:
Stock[nodeKey]= arrayOfGrundyOfEachNextNode= [grundy_efficient(game_dictNextNodes,k,depth+1)
for k in nodeKey_nextNodes]
return(mex(arrayOfGrundyOfEachNextNode))
print(grundy_efficient(substractionGame_dictNextNodes,5,0)) #",0" can be omitted: default value
print(grundy_inefficientVersion(substractionGame_dictNextNodes,5))
def calcule_noyau (game_dictNextNodes):
return [k for k in game_dictNextNodes.keys() if grundy_efficient(game_dictNextNodes,k,0)==0]