Posts

  • Ce mini projet sera l’occasion de mettre en oeuvre les notions vues dans le cours précédent sur : la définition d’un objet en javascript la gestion des évènements l’utilisation d’une fonction callback avec un timer Vous pourrez également suivre ce tutoriel avec la video à l’adresse : lien video Afficher des éléments en javascript Contenu du dossier du projet D’abord, créer un dossier contenant :
  • Le DOM le DOM ou Document Object Model, une interface qui fait partie du BOM (Browser Object Model) et grâce à laquelle nous allons pouvoir manipuler le contenu HTML et les styles de nos pages. Le DOM est ainsi une représentation structurée du document sous forme « d’arbre » crée automatiquement par le navigateur, à partir de sa lecture du document HTML.
  • Algorithme des k plus proches voisins notebook Le notebook présenté ici se trouve à l’adresse tix06.github.io/jupyterlite_NSI Choisir le dossier TP4_data_analyse puis le notebook algoKNN.ipynb.
  • Notebooks associés algorithme de recherche de plus proches voisins KNN: algKnn algorithme de recommandation : algorithme de recommandation.md arbres de décision : graphes_mini_prog.md Intelligence artificielle (IA) L’intelligence artificielle désigne des algorithmes plus ou moins évolués qui traitent des problèmes dont la résolution fait appel à l’intelligence humaine. Ils imitent des actions humaines.
  • Algorithmes de recommandation Lien vers le notebook en ligne : https://mybinder.org/v2/gh/tix06/notebooks_classif/master Choisir alors le fichier : algorithme de recommandation.ipynb Il s’agit d’un cas très classique d’algorithme utilisé dans le web marketing. Un client choisit et met dans ses favoris un article, ou dans son panier. Le site lui propose des articles compatibles, ou similaires. La recommandation peut être basée sur la description de ces articles. L’algorithme va alors chercher les articles qui ont le plus de points communs dans leur description; c’est à dire le plus de mots communs dans leur description.
  • Arbres de classification Lien vers le notebook en ligne : https://mybinder.org/v2/gh/tix06/notebooks_classif/master Choisir alors le fichier : graphes_mini_prog.ipynb Définition Un arbre de classification est utile pour réaliser des prévisions de manière explicite. C’est un outil utilisé pour les algorithmes de backtracking (modéliser une partie d’echecs) pour l’appentissage automatisé (machine learning) supervisé (les classes des entrées sont connue) Pour le machine learning l’arbre peut évoluer et se restructurer à partir d’informations reçues.
  • tracer un arbre à partir d’une expression NPI NPI : notation polonaise inversée En particulier : on dispose d’une expression en NPI, du type : L3 = [7,8,’-’,6,’’,10,3,’+’,’’] Et on veut créer et afficher le graphe correspondant : On utilisera le script : L3 = [7,8,’-’,6,’’,10,3,’+’,’’] D = makeTree(L3) G = nx.Graph() graphDict(D) Dont l’instruction suivante va générer le dictionnaire à partir de l’expression NPI (fonction npiTree recursive):
  • tracé de graphes avec Networkx Les scripts suivants permettent de choisir entre plusieurs types de configuration pour tracer un graphe avec Networkx, module Python. On pourra choisir de personaliser : la couleur d’un noeud l’etiquette des noeuds l’étiquette des arêtes le type de trait (plein ou en pointillés) des arêtes Déclaration du graphe import matplotlib.pyplot as plt import networkx as nx from numpy import array G = nx.Graph() # definition des noeuds G.add_node(0,label=‘A’,col=‘pink’) G.add_node(1,label=‘B’,col=‘red’) G.add_node(2,label=‘C’,col=‘white’) G.add_node(3,label=‘D’,col=‘white’) G.add_node(4,label=‘E’,col=‘white’) G.add_node(5,label=‘F’,col=‘blue’) # definition des aretes G.add_edge(0,1,weight=6,styl=‘dashed’) G.add_edge(0,2,weight=5,styl=‘solid’) G.add_edge(0,4,weight=1,styl=‘solid’) G.add_edge(4,1,weight=5,styl=‘solid’) G.add_edge(4,2,weight=1,styl=‘solid’) G.add_edge(4,3,weight=3,styl=‘solid’) G.add_edge(2,3,weight=8,styl=‘solid’) G.add_edge(4,5,weight=6,styl=‘dashed’) G.add_edge(3,5,weight=9,styl=‘solid’) Exploration de la structure de données couleur des noeuds liste = list(G.nodes(data=‘col’)) colorNodes = {} for noeud in liste: colorNodes[noeud[0]]=noeud[1] colorNodes {0: ‘pink’, 1: ‘red’, 2: ‘white’, 3: ‘white’, 4: ‘white’, 5: ‘blue’} Pour les couleurs des noeuds, le format doit être en liste (de la taille du nombre de noeuds)
  • Créer et resoudre un labyrinthe Les scripts suivants permettent de créer un labyrinthe de manière aléatoire, et d’exploiter la structure de données de ce labyrinthe. On pourra ainsi tester quelques algorithmes relatifs au parcours de ce labyrinthe. Les scripts en permettent une visualisation. Définitions des classes class Pile: def init(self): self.lst = [] def empty(self): return self.lst == [] def push(self, x): self.lst.append(x) def pop(self): if self.empty(): raise ValueError(“pile vide”) return self.lst.pop() def explorer(laby): pile = Pile() pile.push((0, laby.q - 1)) laby.tab[0][laby.q - 1].etat = False while True: i, j = pile.pop() if i == laby.p - 1 and j == 0: break if j > 0 and laby.tab[i][j].S and laby.tab[i][j-1].etat: pile.push((i, j)) pile.push((i, j-1)) laby.tab[i][j-1].etat = False elif i < laby.p-1 and laby.tab[i][j].E and laby.tab[i+1][j].etat: pile.push((i, j)) pile.push((i+1, j)) laby.tab[i+1][j].etat = False elif j < laby.q-1 and laby.tab[i][j].N and laby.tab[i][j+1].etat: pile.push((i, j)) pile.push((i, j+1)) laby.tab[i][j+1].etat = False elif i > 0 and laby.tab[i][j].W and laby.tab[i-1][j].etat: pile.push((i, j)) pile.push((i-1, j)) laby.tab[i-1][j].etat = False return pile.lst class Case: def init(self): self.N = False self.W = False self.S = False self.E = False self.etat = False class Labyrinthe: def init(self, p, q): self.p = p self.q = q self.tab = [[Case() for j in range(q)] for i in range(p)] def show(self): plt.plot([0, 0, self.p, self.p, 0], [0, self.q, self.q, 0, 0], linewidth=2) for i in range(self.p-1): for j in range(self.q): if not self.tab[i][j].E: plt.plot([i+1, i+1], [j, j+1], ‘b’) for j in range(self.q-1): for i in range(self.p): if not self.tab[i][j].N: plt.plot([i, i+1], [j+1, j+1], ‘b’) plt.axis([-1, self.p+1, -1, self.q+1]) plt.show() def solution(self): sol = explorer(self) X, Y = [], [] for (i, j) in sol: X.append(i+.5) Y.append(j+.5) X.append(self.p-.5) Y.append(.5) plt.plot(X, Y, ‘r’, linewidth=2) self.show() def creation(p, q): laby = Labyrinthe(p, q) pile = Pile() i, j = randint(p), randint(q) pile.push((i, j)) laby.tab[i][j].etat = True while not pile.empty(): i, j = pile.pop() v = [] if j < q-1 and not laby.tab[i][j+1].etat: v.append(‘N’) if i > 0 and not laby.tab[i-1][j].etat: v.append(‘W’) if j > 0 and not laby.tab[i][j-1].etat: v.append(‘S’) if i < p-1 and not laby.tab[i+1][j].etat: v.append(‘E’) if len(v) > 1: pile.push((i, j)) if len(v) > 0: c = v[randint(len(v))] if c == ‘N’: laby.tab[i][j].N = True laby.tab[i][j+1].S = True laby.tab[i][j+1].etat = True pile.push((i, j+1)) elif c == ‘W’: laby.tab[i][j].W = True laby.tab[i-1][j].E = True laby.tab[i-1][j].etat = True pile.push((i-1, j)) elif c == ‘S’: laby.tab[i][j].S = True laby.tab[i][j-1].N = True laby.tab[i][j-1].etat = True pile.push((i, j-1)) else: laby.tab[i][j].E = True laby.tab[i+1][j].W = True laby.tab[i+1][j].etat = True pile.push((i+1, j)) return laby Librairies from numpy.random import randint import matplotlib.pyplot as plt Un premier exemple laby = creation(6, 5) laby.solution()
  • Utiliser le module turtle Le script suivant présente les classes et fonctions utiles pour : tracer un labyrinthe complet parcourir le labyrinthe selon une méthode de parcours en profondeur tracer ce parcours animé avec turtle Utilisation : tab=labyrinthe(5,6) L = parcours((len(tab)-1,0),(0,len(tab[0])-1),tab) afficheTurtle(tab,L) librairies from numpy.random import randint import matplotlib.pyplot as plt import turtle classes utiles class Pile: def init(self): self.lst = [] def empty(self): return self.lst == [] def push(self, x): self.lst.append(x) def pop(self): if self.empty(): raise ValueError(“pile vide”) return self.lst.pop() """ def explorer(laby): pile = Pile() pile.push((0, laby.q - 1)) laby.tab[0][laby.q - 1].etat = False while True: i, j = pile.pop() if i == laby.p - 1 and j == 0: break if j > 0 and laby.tab[i][j].S and laby.tab[i][j-1].etat: pile.push((i, j)) pile.push((i, j-1)) laby.tab[i][j-1].etat = False elif i < laby.p-1 and laby.tab[i][j].E and laby.tab[i+1][j].etat: pile.push((i, j)) pile.push((i+1, j)) laby.tab[i+1][j].etat = False elif j < laby.q-1 and laby.tab[i][j].N and laby.tab[i][j+1].etat: pile.push((i, j)) pile.push((i, j+1)) laby.tab[i][j+1].etat = False elif i > 0 and laby.tab[i][j].W and laby.tab[i-1][j].etat: pile.push((i, j)) pile.push((i-1, j)) laby.tab[i-1][j].etat = False return pile.lst """ class Case: def init(self): self.N = False self.W = False self.S = False self.E = False self.etat = False class Labyrinthe: def init(self, p, q): self.p = p self.q = q self.tab = [[Case() for j in range(q)] for i in range(p)] def show(self): plt.plot([0, 0, self.p, self.p, 0], [0, self.q, self.q, 0, 0], linewidth=2) for i in range(self.p-1): for j in range(self.q): if not self.tab[i][j].E: plt.plot([i+1, i+1], [j, j+1], ‘b’) for j in range(self.q-1): for i in range(self.p): if not self.tab[i][j].N: plt.plot([i, i+1], [j+1, j+1], ‘b’) plt.axis([-1, self.p+1, -1, self.q+1]) plt.show() """ def solution(self): sol = explorer(self) X, Y = [], [] for (i, j) in sol: X.append(i+.5) Y.append(j+.5) X.append(self.p-.5) Y.append(.5) plt.plot(X, Y, ‘r’, linewidth=2) self.show() """ def creation(p, q): laby = Labyrinthe(p, q) pile = Pile() i, j = randint(p), randint(q) pile.push((i, j)) laby.tab[i][j].etat = True while not pile.empty(): i, j = pile.pop() v = [] if j < q-1 and not laby.tab[i][j+1].etat: v.append(‘N’) if i > 0 and not laby.tab[i-1][j].etat: v.append(‘W’) if j > 0 and not laby.tab[i][j-1].etat: v.append(‘S’) if i < p-1 and not laby.tab[i+1][j].etat: v.append(‘E’) if len(v) > 1: pile.push((i, j)) if len(v) > 0: c = v[randint(len(v))] if c == ‘N’: laby.tab[i][j].N = True laby.tab[i][j+1].S = True laby.tab[i][j+1].etat = True pile.push((i, j+1)) elif c == ‘W’: laby.tab[i][j].W = True laby.tab[i-1][j].E = True laby.tab[i-1][j].etat = True pile.push((i-1, j)) elif c == ‘S’: laby.tab[i][j].S = True laby.tab[i][j-1].N = True laby.tab[i][j-1].etat = True pile.push((i, j-1)) else: laby.tab[i][j].E = True laby.tab[i+1][j].W = True laby.tab[i+1][j].etat = True pile.push((i+1, j)) return laby autres definitions utiles def directions(laby,i,j): “““les directions possibles pour la case courante i : int numero de ligne j : numero de la colonne retourne une liste (tuple) des points cardinaux possibles "”” L = [] if laby.tab[j][i].N == True: L.append(‘N’) if laby.tab[j][i].S == True: L.append(‘S’) if laby.tab[j][i].E == True: L.append(‘E’) if laby.tab[j][i].W == True: L.append(‘W’) return tuple(L) def labyrinthe(lines,col): "”" Params : ——– lines : int : nombre de lignes du labyrinthe col : int : nombre de colonnes Returns : ——— tab2 : list : tuples de 1 à 4 éléments correspondants aux directions libres (‘N’, ‘S’, E’, ‘W’) sortie : tracé du labyrinthe Variables : ———– p : nombre de colonnes (=largeur) q : nombre de lignes (=hauteur) """ laby = creation(col, lines) tab2 = [[0]laby.p for i in range(laby.q)] for i in range(laby.q): for j in range(laby.p): tab2[i][j] = directions(laby,i,j) Labyrinthe.show(laby) return tab2 def nexto(c,direc): “““retourne les coordonnées lors du deplacement selon la position actuelle et la direction Params : ——– c : tuple (ligne,colonne) correspondant à (y,x) dans le plan cartesien direct : str : ‘N’, ‘S’, E’, ‘W’ Returns : ——— tuple : (int,int) correspondant à (ligne,colonne) "”” i,j = c[0],c[1] if direc==‘N’ : return (i+1,j) if direc==‘S’ : return (i-1,j) if direc==‘E’ : return (i,j+1) if direc==‘W’ : return (i,j-1) def visited(c,L,couleur): “““retourne la couleur du noeud de coord c et de liste de directions possibles L selon celle de ses voisins Params : ——– c : tuple : (ligne,colonne) correspondant à (y,x) dans le plan cartesien L : list : tuples de 1 à 4 éléments correspondants aux directions libres (‘N’, ‘S’, E’, ‘W’) couleur : List dimension 2 contenant des elements str ‘white’ si noeud non visité, ‘green’ si le noeud est en cours de visite, ‘red’ si tous les noeuds ont été visités autour de lui Returns : ——— couleur : str : ‘green’ si le noeud est en cours de visite, ‘red’ si tous les noeuds ont été visités autour de lui "”” i,j = c[0],c[1] coul=‘red’ for direc in L: coord = nexto(c,direc) if couleur[coord[0]][coord[1]]‘white’:coul=‘green’ #print(c,coul) return coul def parcours(start,end,tab): “““trouve la solution au labyrinthe et trace ce chemin p : Pile() utile pour la recherche du parcours pchemin : Pile() utile pour memoriser tout le chemin on insère dans le chemin toutes les arêtes empruntées : pour le chemin entre c1 et c2, on insère c1 puis c2 "”” p = Pile() pchemin = Pile() p.push(start) c = start couleur = [[‘white’]*len(tab[0]) for i in range(len(tab))] while (not p.empty()) and (not c == end): c = p.pop() pchemin.push(c) # chaque fois que l’on depile, on rempile dans pchemin L = tab[c[0]][c[1]] couleur[c[0]][c[1]]=visited(c,L,couleur) # c est retiré de la pile et coloré en green ou red for direc in L: coord = nexto(c,direc) if couleur[coord[0]][coord[1]]‘white’: # le noeud fils est coloré en blanc dans la direction D p.push(c) # on remet le noeud parent afin de reconsidérer sa couleur à chaque fois que l’on depile # et le chemin arriere CONTINU pour le tracé p.push(coord) # alors on ajoute le noeud fils dans la direction D au sommet de la pile return pchemin.lst fonctions particulières au module turtle def turtleWall(dir,i,j): “““trace les murs des directions fermées dir est un tuple contenant les directions libres "”” larg = len(tab[0]) haut = len(tab) fenX = 600 fenY = fenXhaut/larg scaleX = (fenX-20)/larg scaleY = (fenY-20)/haut x0=-fenX/2+10 y0=-fenY/2+10 if not(‘N’ in dir[i][j]) : turtle.penup() turtle.setpos(x0+jscaleX,y0+(i+1)scaleY) turtle.setheading(0) turtle.pendown() turtle.forward(scaleX) if not(‘S’ in dir[i][j]) : turtle.penup() turtle.setpos(x0+jscaleX,y0+iscaleY) turtle.setheading(0) turtle.pendown() turtle.forward(scaleX) if not(‘E’ in dir[i][j]) : turtle.penup() turtle.setpos(x0+(j+1)scaleX,y0+iscaleY) turtle.setheading(90) turtle.pendown() turtle.forward(scaleY) if not(‘W’ in dir[i][j]) : turtle.penup() turtle.setpos(x0+jscaleX,y0+iscaleY) turtle.setheading(90) turtle.pendown() turtle.forward(scaleY) def turtleLab(tab): for i in range(len(tab)): for j in range(len(tab[i])): turtleWall(tab,i,j) #plt.plot([0, 0, len(tab[0]), len(tab[0]), 0], [0, len(tab), len(tab), 0, 0], ‘blue’,linewidth=10) #plt.savefig(’laby.png’) def turtlePath(tab,L): “““tracé du parcours dans le labyrinthe à l’aide de la tortue Params: ——- tab : Liste de liste contenant des str : ‘N’,‘S’,‘W’,‘E’ = le labyrinthe L : Liste de tuples correspondant aux cases visitées sortie : ——– le dessin du parcours animé "”” larg = len(tab[0]) haut = len(tab) fenX = 600 fenY = fenXhaut/larg scaleX = (fenX-20)/larg scaleY = (fenY-20)/haut x0=-fenX/2+10 y0=-fenY/2+10 turtle.penup() turtle.pencolor(“red”) turtle.setpos(x0+scaleX/2,y0+scaleY4+scaleY/2) # depart turtle.showturtle() turtle.pendown() start = L[0] for c in L[1:]: #angle = 90*(c[0]-start[0]) # si deplacement uniquement vertical if c[0]!=start[0] : depl = scaleY # vertical angle = 90*(c[0]-start[0]) else : depl = scaleX # horizontal angle = 90 - 90*(c[1]-start[1]) if c[1]<start[1] : angle = 180 # deplacement à gauche turtle.setheading(angle) turtle.forward(depl) start = c fonction principale pour affichage de l’animation turtle def afficheTurtle(tab,L): larg = len(tab[0]) haut = len(tab) fenX = 600 fenY = fenX*haut/larg scaleX = (fenX-20)/larg scaleY = (fenY-20)/haut turtle.setup(fenX, fenY) #Largeur : 600px, Hauteur : 400px turtle.bgcolor((0.9, 0.9, 0.9)) turtle.hideturtle() turtle.penup() turtle.setpos(-fenX/2+10,-fenY/2+10) turtle.setheading(90) turtle.pendown() #turtle.speed(0) turtle.tracer(False) # tracer le Laby avant de demarrer l’animation avec la tortue turtle.pensize(2) turtle.forward(fenY-20) turtle.left(-90) turtle.forward(fenX-20) turtle.left(-90) turtle.forward(fenY-20) turtle.left(-90) turtle.forward(fenX-20) turtle.left(-90) turtleLab(tab) turtle.tracer(True) # fin du tracé du Laby turtle.speed(6) turtlePath(tab,L) # animation du parcours par la tortue #calling for the mainloop() turtle.mainloop() Programme tab=labyrinthe(5,6) L = parcours((len(tab)-1,0),(0,len(tab[0])-1),tab) afficheTurtle(tab,L)
  • Principe Un modèle prédictif ne peut être établi qu’à partir d’une étude prealable de données. Une étude statistique permet de repérer si certains paramètres sont liés entre eux. Alors, si ces données étaient suffisamment nombreuses et précises, il est possible d’établir des lois mathematiques sur ces données. Une manière de représenter ce lien entre paramètres est d’établir une loi de regression linéaire, par exemple.
  • Utilisation du module unittest avec le calcul des nombres premiers avant de démarrer cette partie, il est recommandé de consulter : le cours sur les tests unitaires Et le paragraphe sur mettre son programme sous forme de modules Définition: Un test unitaire est un test réalisé sur une portion du programme, typiquement sur une fonction. Le module unittest offre des outils de test de code, comme la classe TestCase. Le but est des vérifier que votre code génère des résultats corrects, conformes au attentes.
  • Chiffrements symétriques Vocabulaire Chiffrer: transformer les caractères d’un texte pour le rendre incompréhensible, sauf pour celui qui possède la clé de chiffrement. Déchiffrer: transformer le texte chiffré en texte clair à l’aide de la clé de chiffrement Décrypter: transformer le texte chiffré en texte clair sans posséder la clé. Cryptologie: science du secret: possède deux branches cryptographie: étude de l’art du chiffrement cryptanalyse: analyse des méthodes de chiffrement pour les casser (décrypter) à quoi sert le chiffrement? Le chiffrement a pour but de protéger nos données, nos communications, mais aussi de signer nos messages et de s’assurer que l’on communique bien avec la bonne personne: