CAPES NSI – Préparer l’épreuve Python du CAPES informatique

CAPES NSI préparer l’épreuve de programmation Python. Cet article fait suite aux quatre premières parties qu’il est possible de consulter ici et vous permettre de préparer le CAPES informatique :

CAPES NSI Python

CAPES NSI Introduction

Je traite ici des bases du langage Python pour l’apprendre rapidement. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES Informatique.

Regroupement de fonctions :

Un module est un fichier qui contient un ensemble de fonctions que vous souhaitez inclure dans votre application.

Exemple fichier monmodule.py :

def salutations(nom):
  print("Salut " + nom)

Utilisation du module dans un programme Python :

import monmodule

monmodule.salutations("Sébastien")

Renommer le module :

import monmodule as mod

mod.salutations("Daniel")

La fonction dir est une fonction intégrée pour répertorier tous les noms de fonction (ou noms de variable) dans un module.

import platform

res = dir(platform)
print(res) 

Il est possible de n’importer que des parties d’un module, en utilisant le mot-clé from.

from monmodule import salutations

salutations("Jean")

Packages :

Les packages permettent une structuration hiérarchique de l’espace de noms du module.

Les packages aident à éviter les collisions entre les noms de modules.

La création d’un package est assez simple, car elle utilise la structure en répertoire du système d’exploitation.

Si on considère un répertoire nommé pkg qui contient deux modules, module1.py et module2.py.

Le contenu des modules est:

def test():
    print('test module 1')

class Toto:
    pass
def test2():
    print('test module 2')

class Joe:
    pass

Avec cette structure, si le répertoire pkg est dans un emplacement où il peut être trouvé (càd un des répertoires contenus dans sys.path).

Il est possible de se référer aux deux modules (pkg.module1, pkg.module2) et de les importer :

import pkg.module1, pkg.module2

pkg.module1.test()
x = pkg.module2.Joe()

Valeurs aléatoires (random value) :

import random

print(random.random()) #Retourne un nombre décimal aléatoirement entre 0 et 1
print(random.randint(10,20)) #Retourne un entier dans l'écart défini
membre = ["Seb","Jean","Louise"]
print(random.choice(membre)) #Retourne un élément de la liste aléatoirement

CAPES NSI – Liens Externes :

https://www.python.org/

https://fr.wikibooks.org/wiki/Programmation_Python

CAPES NSI Python – Liens Internes :

http://128mots.com/index.php/2021/01/26/ordinateur-quantique-prix/

http://128mots.com/index.php/category/python/

Python les bases en plus de 128 mots [Partie 4]

Cet article fait suite aux trois premières parties qu’il est possible de consulter ici :

Je traite ici des bases du langage Python pour l’apprendre rapidement. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.

Exceptions :

Lorsqu’une erreur se produit, (une exceptions) elle peut être gérée à l’aide de l’instruction try:

try:
  print(r)
except NameError:
  print("variable r non définie")
except:
  print("Autre exception") 

Commentaires :

#Ceci est un commentaire
#sur
#plusieurs ligne
print("Bonjour Python")
"""
Ceci est un commentaire
sur
plusieurs ligne
"""
print("Bonjour Python")

Classes :

Les classes sont comme un constructeur d’objet, cela permet de modeler des concepts réels.

class Personne:
  def __init__(self, nom, age):
    self.nom = nom
    self.age = age

  def ma_fonction(self):
    print("Nom de la personne : " + self.name)

p1 = Personne("Sébastien", 36)
print(p1.nom)
print(p1.age) 
p1.ma_fonction()
p1.age = 40 #Modification des propriétés de l'objet
del p1.age #supprime la propriété de l'objet
del p1  #supprime l'objet

self est une référence à l’instance actuelle de la classe et est utilisé pour accéder aux variables qui appartiennent à la classe. Il peut être nommé autrement que self, mais ce doit être obligatoirement le premier paramètre de toute fonction de la classe.

Héritage :

L’héritage permet de définir une classe qui hérite de toutes les méthodes et propriétés d’une autre classe.

class Animal :
   def marcher():
       print('marche')

class Chien(Animal)
    pass

c1 = Chien()
c1.marcher()

Constructeur :

La fonction __init __ () est appelée automatiquement chaque fois qu’un nouvel objet est créé.

super () fera que la classe enfant héritera de toutes les méthodes et propriétés de son parent.

class Etudiant(Personne):
  def __init__(self, nom, prenom):
    super().__init__(nom, prenom) 

Python les bases en plus de 128 mots [Partie 3]

Cet article fait suite aux deux premières parties qu’il est possible de consulter ici :

Je traite ici des bases du langage Python pour l’apprendre rapidement. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.

Tuples :

Un tuple est une collection ordonnée comme les listes et immuable (qui ne change pas).

exempleTuple = ("pomme", "poire", "fraise")
print(exempleTuple)
print(exempleTuple[1])
print(exempleTuple[-1]) #L'indexation négative signifie à partir de la fin, -1 se réfère au dernier élément, -2 se réfère à l'avant-dernier élément, etc.
print(exempleTuple[1:2]) #Vous pouvez spécifier une plage d'index en spécifiant par où commencer et où terminer la plage.
z = list(exempleTuple) #conversion tuple en liste
z[1] = "banane" 
x = tuple(z) #conversion liste en tuple

for x in exempleTuple: #Boucle sur un tuple
  print(x) 

if "poire" in exempleTuple: #test d'existence dans un tuple
  print("Oui") 

Unpacking :

coordonnees = (1,2,3)
x,y,z = coordonnees
print(x)

Dictionnaires :

Un dictionnaire est une collection non ordonnée, modifiable et indexée.

client = {
   "nom": "Elodie",
   "age": "45",
   "annee": 1980
 }

print(client["age"])
client["nouvelleCle"] = "nouvelleValeur" #ajoute une nouvelle clé et valeur
client.get("solde") #renvoi 'None' car la clé n'existe pas

Fonctions :

Les fonctions permettent d’organiser le code en morceau réutilisables. En Python, une fonction est définie à l’aide du mot clé def.

def exemple_fonction():
  print("TestFonction")

exemple_fonction()

Les données peuvent être passées aux fonctions en tant que paramètre. Vous pouvez ajouter autant de paramètres que vous le souhaitez, il suffit de les séparer par une virgule.

def exemple_fonction(prenom):
  print("Bonjour " + prenom)

exemple_fonction("John")
exemple_fonction("Pierre")

Python les bases en plus de 128 mots [Partie 2]

Cet article fait suite à la première partie qu’il est possible de consulter ici : http://128mots.com/index.php/2019/12/04/python-les-bases-capes-nsi-snt-en-plus-de-128-mots/

Comme pour le premier article, je traite ici des bases du langage Python pour l’apprendre rapidement. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.

Priorité des opérateurs :

Je récapitule la priorité des opérateurs en Python, de la priorité la plus haute à la priorité la plus basse

  • Parenthèses () : groupement d’opérations
  • Exposant : x ** y
  • Multiplication, multiplication de matrice, division, division entière, modulo : *, @, /, //, %
  • Addition, soustraction : +, –

Fonctions mathématiques :

import math
  • math.ceil(2.6) entier supérieur
  • math.floor(-5.3) partie entière, donne ici -8.0.
  • math.sqrt : racine carrée.
  • math.pow(5, 5) : 5 puissance 5.
  • math.exp(2) : fonction exponentielle.
  • math.log(2) : fonction logarithme
  • math.log(3, 2) : log en base 2.
  • math.factorial(4) : factorielle
  • math.fsum(L) : somme des éléments d’une liste
  • math.sin, math.cos, math.tan : fonctions trigonométriques
  • math.pi : pi
  • math.degrees(y) : conversion de radians en degrés
  • math.radians(y) : conversion de degrés en radians

Expressions conditionnelles :

Python s’appuie sur l’indentation pour définir la portée du code.

x = 100
y = 23
if x > y:
  print("x plus grand que y")
elif a == b:
  print("égalité")
else:
  print("y plus grand que x")

Chaines de caractères formatées (f-strings) :

import math
print(f'La valeur de pi est {math.pi:.3f}.')

Listes à deux dimensions (matrices) :

matrix = [[1, 2, 3], [4,5, 6], [7, 8, 9]]
print(matrix[0][1])

Méthodes sur les listes :

list.append('n') #Ajoute un élément en fin de liste
list.insert(0,'a') #Ajoute un élément à la position spécifiée
liste.pop(1) #Enleve l'élément de la liste à la position spécifiée
liste.sort() #Trie la liste
liste.reverse() #Retourne la liste
liste.copy()   #retourne une copie de la liste

Python les bases en plus de 128 mots [Partie 1]

Voici mes notes pour apprendre très rapidement le langage python. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.

Opérateurs logiques :

  • and : retourne True si les deux déclarations sont vraies
  • or : Renvoie True si l’une des déclarations est true
  • not : Inverser le résultat, renvoie False si le résultat est vrai

Opérateurs de comparaison :

  • == Égalité
  • != Non égal
  • > < Supérieur / Inférieur
  • <= >= Inférieur égal / Supérieur égal
  • != Différent

Mot clé pass :

Lorsque l’instruction pass est exécutée, rien ne se produit, mais vous évitez une erreur lorsque du code vide n’est pas autorisé.

x = 22
y = 150

if x > y:
  pass

Entrée utilisateur :

Utilisation de l’instruction input :

nom = input("Nom utilisateur :")
print("Username is: " + nom)

Boucle While :

La boucle while exécute un ensemble d’instructions tant qu’une condition est vraie. L’instruction break, permet d’arrêter la boucle même si la condition while est vraie.

x = 1
while x < 11:
  if x == 5:
    break
  x += 1 

Boucle For :

Une boucle for effectue une itération sur une séquence (une liste, un tuple, un dictionnaire, un ensemble ou une chaîne de caractère).

Une liste :

for x in [1, 2, 3]:
  print(x)

Une chaine de caractère :

for x in "hello":
  print(x)

Un tuple :

tupleObjet = ('Citroen', 2019, 'C4', 23000)
 
for elements in tupleObj:
    print(elements)

Un dictionnaire :

dico = {'couleur': 'vert', 'animal': 'chien', 'legume': 'epinard'}
for cle in dico:
    print(cle)

Fonction Range :

Pour boucler un nombre de fois spécifique, utilisez la fonction range ().

for x in range(10):
  print(x)

Les Listes :

Une liste est une collection qui est ordonnée et modifiable et qui permet les doublons.

liste = ["pomme", "banane", "poire"]
print(liste[1])
print(liste[-1]) #Affiche le dernier élément de la liste
print(liste[2:3])#Lorsque vous spécifiez une plage, la valeur de retour sera une nouvelle liste avec les éléments spécifiés.
print(liste[2:3])#Lorsque vous spécifiez une plage, la valeur de retour sera une nouvelle liste avec les éléments spécifiés.
print(liste[:3])#En omettant la valeur initiale, la plage commencera au premier élément:
print(liste[1:])#En omettant la valeur de fin, la plage ira à la fin de la liste:
print(liste[-2:-1])#des index négatifs pour lancer la recherche à partir de la fin de la liste: Cet exemple renvoie les éléments de l'index -2 (inclus) à l'index -1 (exclu).

Tri fusion Python – implémentation de l’algorithme

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présente une implémentation du tri fusion python.

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présent une implémentation du tri fusion python.

Introduction

L’algorithme est le suivant :
Diviser en deux moitiés la liste à trier.
On trie chacune d’entre elles.
Fusionner les deux moitiés obtenues pour reconstituer la liste triée.

On applique récursivement cet algorithme c’est à dire jusqu’à ce que la liste à trier soit constituée d’un seul élément.

tri fusion python
Tri fusion (source : wikipedia)
#Tri fusion fonction de division du tableau
def tri_fusion(tableau):
    if  len(tableau) <= 1: 
        return tableau
    pivot = len(tableau)//2
    tableau1 = tableau[:pivot]
    tableau2 = tableau[pivot:]
    gauche = tri_fusion(tableau1)
    droite = tri_fusion(tableau2)
    fusionne = fusion(gauche,droite)
    return fusionne


#Tri fusion fonction de fusion de 2 listes
def fusion(tableau1,tableau2):
    indice_tableau1 = 0
    indice_tableau2 = 0    
    taille_tableau1 = len(tableau1)
    taille_tableau2 = len(tableau2)
    tableau_fusionne = []
    while indice_tableau1<taille_tableau1 and indice_tableau2<taille_tableau2:
        if tableau1[indice_tableau1] < tableau2[indice_tableau2]:
            tableau_fusionne.append(tableau1[indice_tableau1])
            indice_tableau1 += 1
        else:
            tableau_fusionne.append(tableau2[indice_tableau2])
            indice_tableau2 += 1
    while indice_tableau1<taille_tableau1:
        tableau_fusionne.append(tableau1[indice_tableau1])
        indice_tableau1+=1
    while indice_tableau2<taille_tableau2:
        tableau_fusionne.append(tableau2[indice_tableau2])
        indice_tableau2+=1
    return tableau_fusionne

tableau = [11, 222, 3, 899, 24, 5, 46, 67]
print(tableau)
tableau_trie = tri_fusion(tableau)
print(tableau_trie)

A propos de tri fusion

Enfin, Le tri fusion fonctionne par comparaison. La complexité de l’algorithme pour n entrée est n log n, donc asymptotiquement optimal.

La technique est de diviser pour régner. Et l’algorithme fait principalement une opération de fusion (deux listes triées peuvent être fusionnées en temps linéaire).

Tri fusion python : liens externes

https://www.geeksforgeeks.org/merge-sort/

http://lwh.free.fr/pages/algo/tri/tri_fusion.html

https://pixees.fr/informatiquelycee/n_site/isn_algo_diviser_pour_regner.html

https://fr.wikipedia.org/wiki/Tri_fusion

https://graal.hypotheses.org/tag/algorithme-de-wagner-fischer

https://fr.wikipedia.org/wiki/Algorithme_de_Wagner-Fischer

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein

https://medium.com/@sddkal/wagner-fischer-algorithm-be0d96893f6d

https://www.python-course.eu/levenshtein_distance.php

Liens internes sur les algorithmes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/graphes/

http://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Pour calculer la distance de Levenshtein avec un algorithme non récursif. On utilise une matrice qui contient les distances de Levenshtein. Alors Ce sont les distances entre tous les préfixes de la première chaîne et tous les préfixes de la seconde chaîne de caractères.

Parcours en profondeur python – algorithmes graphes

Implémentons le parcours en profondeur python d’un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.

Introduction

Le principe et d’explorer le graphe à partir d’un sommet donné et on explore tous ses voisins en allant le plus profond possible (càd en répétant l’opération de sommet visité en sommet visité jusqu’à ce qu’on soit coincé, on revient alors via le chemin emprunté jusqu’au point de départ).

Le parcours en profondeur permet de trouver l’arbre couvrant du graphe qui n’est pas le même en général que l’arbre couvrant trouvé via le parcours en largeur du graphe.

L’algorithme en résumé :

Phase de descente :

Partir du sommet choisi pour démarrer et le marquer.

Tant que c’est possible :

  • Aller vers un voisin non visité et le marquer.
  • Mémoriser l’arrête ou l’arc par lequel on est passé.
  • Si tous les voisins sont déjà visités :
    • Revenir vers le sommet par lequel il a été découvert (backtrack phase : de remontée)

Si tous les sommets du graphe sont visités (sont dans l’arbre couvrant) alors le graphe est connexe sinon le graphe n’est pas connexe.

Exemple Python avec 3 graphes :

Implémentons le parcours en profondeur python d'un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.
Exemple de graphe connexe
Implémentons le parcours en profondeur python d'un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.
Exemple de graphe non connexe
Implémentons le parcours en profondeur python d'un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.
Exemple de graphe connexe

Module Python pour le parcours en profondeur :

#Parcours en profondeur d'un graphe
# Algorithme récursif : Le principe est d'explorer le graphe et de revenir sur ses pas lorsuqu'on est coincé.
def parcours_en_profondeur(graphe, sommet_en_cours:str, sommets_visites:[]):
	print('Essai d explorer le sommet :' + str(sommet_en_cours))
	if sommet_en_cours not in sommets_visites:
		sommets_visites.append(sommet_en_cours) #Ajoute le sommet en cours au noeud visité
		print('Exploration du sommet :' + str(sommet_en_cours))
	sommets_voisins_non_visites = []
	for sommet_voisin in graphe[sommet_en_cours]:
		if sommet_voisin not in sommets_visites:
			sommets_voisins_non_visites.append(sommet_voisin) # Constitue la liste des sommets voisins non encore visité

	for sommet in sommets_voisins_non_visites:
		#pour tout les sommets voisins non visités on effectue un parcours en profondeur
		parcours_en_profondeur(graphe, sommet, sommets_visites)

#Fonction de test si le graphe est connexe suite à un parcours en profondeur
def est_un_graphe_connexe(graphe, sommets_visites):
	if len(sommets_visites) == len(graphe):
		print("Le graphe est connexe")
		print(20 * "-")
	else:
		print("Le graphe n'est pas connexe")
		print(20 * "-")


#Liste d'ajacence du graphe
graphe = {
	'A': ['B','C'],
	'B': ['A','C', 'D'],
	'C': ['D'],
	'D': ['C','A']
}

sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)

#Exemple de graphe non connexe : Le sommet D n'est pas connecté au graphe
graphe = {
	'A': ['B','C'],
	'B': ['A','C'],
	'C': ['A'],
	'D': []
}

sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)

#Autre exemple
graphe = {
	'A': ['B','D'],
	'B': ['A','C'],
	'C': [],
	'D': ['A']
}

sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)

#en fin de parcours si tout les sommets sont dans les sommets visités alors le graphe est connexe

#Note
#J'ai rencotré l'erreur IndentationError: unindent does not match any outer indentation level
#Je l'ai simplement résolu en reprenant toute l'indentation en debut de ligne
#et en la remplaçant par des Tabulation plutot que des espaces
http://128mots.com/index.php/en/2021/01/13/quantum-sort-algorithm/

http://128mots.com/index.php/category/non-classe/

Parcours en profondeur python : Liens externes :

https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes

https://www.kartable.fr/ressources/mathematiques/cours/les-graphes/4795

http://math.univ-lyon1.fr/irem/Formation_ISN/formation_parcours_graphes/graphe/1_notion_graphe.html