Dernière séance : Axel nous met un jeu en réseau

Pour cette dernière séance, Axel a accepté le challenge : prendre la main de la classe virtuelle et coder un petit jeu pygame ou une petite interface de type « grille » en réseau.

Moi, j’ai uniquement posé des questions. Respect Axel !

On y parle de Threads et de Sockets mais aussi de classe avec des instances dont les attributs sont des dictionnaires… Un sacré tour d’horizon de ce qu’on a appris dans ce cycle NSI.

Bravo et merci Axel ! Les codes en cliquant sur « lire la suite »


Émotion de finir ce cycle terminal avec des élèves géniales et géniaux, un plaisir de vous côtoyer depuis un, deux, parfois trois ans (avec l’ancienne option de seconde ICN).

Au revoir ! Bonne continuation !

Lire la suite

Cryptographie

On commence par corriger l’exercice donné sur le routage.


Cryptographie : chiffrement symétrique, asymétrique, en pratique dans HTTPS ?

On utilise l’excellent support de Gilles Lassus, ici.


Le code de la première activité :

from operator import xor


def chiffre(message_clair, masque):
    """chiffre message en le XORant avec masque"""
    assert len(message_clair) <= len(masque)

    reponse = ""
    # parcours du message à chiffrer
    for i in range(len(message_clair)):
        a = ord(message_clair[i])
        b = ord(masque[i])
        x = xor(a, b)
        reponse += chr(x)

    return reponse


# pour réviser le xor
print(xor(42, 96))  # 74 = 64 + 8 + 2 attendu
# car 00101010 xor 01100000 donne 01001010
print(xor(74, 96))  # 42 le nombre de départ

# la vraie question

masque = "CETTEPHRASEESTVRAIMENTTRESTRESLONGUEMAISCESTFAITEXPRES"

message_code = chiffre("HELLO WORLD OF NSI ! JE CHIFFRE :-)", masque)
print(message_code)
print(chiffre(message_code, masque))

Routage

Cours – routage, RIP ou OSPF ?

Tables de routage. Routage statique vs routage dynamique ?

On reprend et on précise les deux logiques des routages dynamiques avec

  • le protocole RIP (Routing Information Protocol) proche d’un parcours en largeur où l’on compte les sauts
  • le protocole OSPF (Open Shortest Path First) proche d’une recherche du plus court chemin avec l’algorithme de Dijkstra.

On se base sur l’excellent cours de David ROCHE (pixees).

Exercices

Les sujets des deux exercices

Le tableau du jour :

Exercice 2 pour vendredi ! Courage !

Dijsktra : correction à la main et en python

Il fallait pour aujourd’hui déterminer le plus court chemin de H à E dans ce graphe pondéré à l’aide de l’algorithme de Dijkstra.

À la main

On corrige avec notre maintenant habituel tableau :

En python ?

Le fruit du travail de TP hier, groupe Alanis, Axel et Bastien :

On marque la sélection H avec poids 0
Pour B, on remplace (None, 1000) par ('H', 12)
Pour C, on remplace (None, 1000) par ('H', 20)
Pour D, on remplace (None, 1000) par ('H', 9)
On marque la sélection D avec poids 9
Pour C, on remplace ('H', 20) par ('D', 17)
Pour F, on remplace (None, 1000) par ('D', 30)
On marque la sélection B avec poids 12
Pour G, on remplace (None, 1000) par ('B', 25)
On marque la sélection C avec poids 17
Pour F, on remplace ('D', 30) par ('C', 28)
Pour G, on remplace ('B', 25) par ('C', 24)
On marque la sélection G avec poids 24
Pour E, on remplace (None, 1000) par ('G', 33)
On marque la sélection F avec poids 28
Pour E, on remplace ('G', 33) par ('F', 31)
On marque la sélection E avec poids 31

***********
* Bilan : *
***********

Le parcours le plus court a pour longueur 31
Par exemple : 'H', 'D', 'C', 'F', 'E'

Le code pour implémenter un graphe pondéré et la fonction dijkstra en cliquant sur « lire la suite ». Bravo à ces trois codeurs !

Lire la suite

« Descriptifs » pour la fiche pour le grand oral

Il s’agit des parties du programme non traitées, à recopier sur la fiche du grand oral pour éviter d’être interrogé sur ces questions. Le secrétariat du lycée agrafera agrafera ces documents signés par moi-même à votre fiche.


EN NSI

Architecture :
Gestion des processus et des ressources par le système d’exploitation.
Composants intégrés d’un système sur puce

Langages et programmation :
Calculabilité, décidabilité. Halting problem.
Paradigmes de programmation :
→ fonctionnel : map, reduce, filter
→ logique

Algorithmique :
Programmation dynamique
Recherche textuelle → Boyer-Moore


EN MATHS – COMMUN AVEC LES COLLÈGUES AU LYCÉE

  • Les équations différentielles à coefficients ou second membre non constants,
  • fonctions trigonométriques,
  • méthode d’Euler et la plupart des exemples d’algorithmes,
  • somme de variables aléatoires,
  • concentration, loi des grands nombres et inégalité de Bienaymé-Tchebychev.

TP graphes et algorithmique

On commence par corriger la recherche de plus court chemin donnée pour aujourd’hui :

Pour demain : un autre parcours

Plus court chemin de H à E ?


TP – algorithmique des graphes

Dans un premier temps, autocorrection des implémentations pour aujourd’hui : corriger ou faire si pas fait ! Les codes corrigés sont disponibles ci-dessous ou en cliquant sur « lire la suite ».

Puis implémenter la recherche de cycles (algorithme en pseudo-code à « À faire vous-même 8 » sur cette page de l’excellent David Roche) et pour les plus valeureuses et les plus valeureux l’algorithme de Dijkstra.

Lire la suite

Parcourir un graphe

Parcours en profondeur

On revient sur le parcours en profondeur avec une pile.

Le code ci-dessous en cliquant sur « lire la suite »

Version récursive à faire pour lundi

Parcours en largeur

On obtient ce parcours en largeur avec le même algorithme mais en utilisant une file plutôt qu’une pile. A faire pour lundi


Algorithme de Dijkstra : recherche du plus court chemin dans un arbre pondéré

On explique le principe sur cet exemple, dans une version « mathématique » de l’algorithme.
Une autre version et une implémentation à venir la semaine prochaine.

Pour lundi, même travail sur ce graphe pour trouver le chemin le plus court pour aller de A à I:

Application au routage

On introduit à l’oral les deux logiques des routages avec

  • le protocole RIP (Routing Information Protocol) proche d’un parcours en largeur où l’on compte les sauts
  • le protocole OSPF (Open Shortest Path First) proche d’une recherche du plus court chemin avec l’algorithme de Dijkstra.

AU FINAL, POUR LUNDI 7 juin :
-> Depuis lundi, créer une matrice d’adjacence pour implémenter le même graphe et une liste des sommets. Répondre aux questions du TP de lundi avec cette nouvelle implémentation
-> Implémenter le parcours en largeur avec une file
-> Implémenter le parcours en profondeur en version récursive
-> Faire l’exercice « Dijkstra » sur le dernier graphe
-> Courage !

Lire la suite

Graphes (2)

Flash / TP

Implémentez ce graphe avec un dictionnaire dont les clés sont les sommets et les valeurs les listes d’adjacence de ces sommets

Écrire des fonctions pour :

  1. Rajouter un sommet K
  2. Rajouter une arête:
    • entre A et E
    • entre B et C
    • entre K et H
    • entre K et B
    • entre K et F
  3. Supprimer l’arête entre A et C
  4. Supprimer le sommet I (et toutes les arêtes de sommet I)

Les codes ci-dessous en cliquant sur « lire la suite »

POUR LUNDI 7 juin :
Dans un autre fichier, créer la matrice d’adjacence pour implémenter le même graphe et une liste des sommets. Répondre aux mêmes questions avec cette nouvelle implémentation pour vendredi lundi.


Suite du cours : parcours en profondeur

  • version itérative avec une pile, sera repris vendredi
Lire la suite