Mardi 31 mars – intégrales : changeons de point de vue

Bonjour.

 

D’abord, voici la correction des derniers exercices A5.

 

Donc, comme bilan provisoire, on a bien compris qu’une intégrale est une aire : celle « sous » la courbe de la fonction qu’on intègre.

 

Mettons-ça de côté quelques temps : nous y reviendrons.

 

Pour jeudi, réfléchissez aux questions toutes simples suivantes :

  • Quelle est une fonction dont la dérivée soit f(x)=2x ? En trouver plusieurs. Qu’ont-elles toutes en commun ? Qu’est ce qui les différencie ?
  • Quelle est une fonction F dont la dérivée soit f(x)=4x-1 ?
  • Quelle est une fonction G dont la dérivée soit g(x)=6x^2-5x+3 ?
  • Quelle est une fonction H dont la dérivée soit h(x)=e^x+\dfrac{1}{x} ?

 

A jeudi !

Mardi 31 mars – exode rurale

Bonjour.

 

Voici le corrigé d’une part de l’exercice 5 sur les graphes, et du dernier exercice de cryptographie.

 

Je vous invite à travailler pour vendredi le dernier exercice (modèle proie – prédateur) de la feuille d’exercices sur les graphes, assez calculatoire (courage !)

 

Après cela, on fera un bilan des différentes techniques liées aux graphes, à la notion d’état stable, à la traduction matricielle des graphes, aux suites de matrices qui en résultent, etc.

 

Bonne semaine à tous.

 

 

Test « rapide » -> se donner 30 minutes

Le sujet :


Un corrigé dans 30 minutes en cliquant sur « lire la suite » :

cm 2020-03-31 - TS1 - A11 - Test rapide primitives ex1 cm 2020-03-31 - TS1 - A11 - Test rapide primitives ex2cm 2020-03-31 - TS1 - A11 - Test rapide primitives ex3

 

Lundi 30 mars – fin de l’orthogonalité dans l’espace

Bonjour.

 

On va commencer par la correction des petits exercices dans le manuel, et par le début du travail sur l’idée d’orthogonalité entre deux plans.

 

Ensuite, on peut terminer le cours sur l’orthogonalité, avec celle entre droite et plan et quelques règles simples.

 

 

Pour mercredi :

  • terminer la feuille G5 – « idée d’orthogonalité dans l’espace »
  • exercice 41 page 351

 

On corrige ça mercredi, on fixe les modalités d’une interro, et on démarre… le calcul intégral !!!

 

Bon début de semaine (si vous arrivez encore à distinguer semaine et week-end…)

CI n°2 – se créer ses propres objets

Bonjour ! Et bienvenue dans cette deuxième semaine.

Le support du jour :


ch3-1-tout-est-objetch3-2-creer-son-propre-objetch3-3-1-creer-une-classech3-3-2-pas-compris-instancech3-3-4-c-est-qui-ce-self-1ch3-3-4-c-est-qui-ce-self-2ch3-4-1ch3-4-2ch3-5


Les exemples du cours et l’autre exemple développé en deuxième partie de cours :

class MaPremiereClasse:
        
    def __init__(self):
        print("constructeur de la classe MaPremierClasse")
        self.nombre = 42     # ajout de l’attribut nombre
        self.nom = "John"

# truc = MaPremiereClasse()

class Etudiant :
    """Cette classe permet de stocker des informations sur un.e etudiant.e

    Un.e etudiant.e est ici caracterise.e par :
    −> ses nom et prenom
    −> son age
    −> son numero d’etudiant.e
    −> son cursus """

    def __init__(self, prenom, nom, age, numero, cursus):
        """Constructeur de notre classe """
        self.nom = nom
        self.prenom = prenom
        self.age = age
        self.numero = numero
        self.cursus = cursus

from math import sqrt

class NombreComplexe:
    """Une classe exemple meme s’il existe un type complex"""

    def __init__(self, a, b):
        self.re = a
        self.im = b
        self.module = sqrt(a ** 2 + b ** 2)

class Personne:
    """Quelqu'un sur l'arbre généalogique

    Une personne, son genre, ses enfants, ses parents"""

    def __init__(self, prenom, nom, age, genre,
                 conj = None, enfants = None, parents = None):
        """Constructeur"""
        self.prenom = prenom
        self.nom = nom
        self.age = age
        self.genre = genre
        self.conj = conj
        if enfants is None:
            self.enfants = []
        else :
            self.enfants = enfants
        if parents is None:
            self.parents = []
        else :
            self.parents = parents
        
        
def affiche(p):
    print("\n", p.prenom, p.nom, "a", p.age, "ans")
    if p.conj is not None:
        print("En couple avec", p.conj.prenom, p.conj.nom)
    if len(p.enfants) > 0:
        print("Enfants :", end = '')
        for e in p.enfants:
            print(e.prenom, end = '\t')
        print()
    if len(p.parents) > 0:
        print("Parents :", end = '')
        for e in p.parents:
            print(e.prenom, end = '\t')
        print()

Et le shell correspondant

>>> moi = Personne("Christophe", "Marchant", 46, "masculin")
>>> moi.conj = Personne("Barbara", "Marchant", 37, "féminin")
>>> affiche(moi)

 Christophe Marchant a 46 ans
En couple avec Barbara Marchant
>>> affiche(moi.conj)

 Barbara Marchant a 37 ans
>>> moi.conj.conj
>>> moi.conj.conj = moi
>>> affiche(moi.conj)

 Barbara Marchant a 37 ans
En couple avec Christophe Marchant
>>> papa = Personne("Jean-Pierre", "Marchant", 73, "masculin")
>>> 
>>> maman = Personne("Nicole", "Marchant", 72, "feminin", papa)
>>> papa.conj = maman
>>> moi.parents
[]
>>> moi.parents =[maman, papa]
>>> affiche(moi)

 Christophe Marchant a 46 ans
En couple avec Barbara Marchant
Parents :Nicole	Jean-Pierre	
>>> papa.enfants += [moi]
>>> maman.enfants = papa.enfants
>>> papa.enfants += [Personne("Pierre", "Marchant", 49, "masculin", None, None, [papa, maman])]
>>> maman.enfants
>>> maman.enfants += [Personne("Marie", "Marvalin", 41, "féminin", None, None, [papa, maman])]
>>> affiche(moi)

 Christophe Marchant a 46 ans
En couple avec Barbara Marchant
Parents :Nicole	Jean-Pierre	
>>> affiche(papa)

 Jean-Pierre Marchant a 73 ans
En couple avec Nicole Marchant
Enfants :Christophe	Pierre	Marie	
>>> affiche(moi.conj)

 Barbara Marchant a 37 ans
En couple avec Christophe Marchant
		
>>> def fratrie(p):
	liste = []
	for e in p.parents:
		for k in e.enfants:
			if k not in liste and k is not p :
				liste += [k]
	return liste

>>> fratrie(moi)
[, ]
>>> for buddy in fratrie(moi):
	print(buddy.prenom, buddy.nom)

	
Pierre Marchant
Marie Marvalin

 

 

 

Prouver un algorithme

On devait pour aujourd’hui implémenter l’algorithme de recherche dichotomique sur un tableau trié :

def recherche_dichotomique(tab, val):
    """ Recherche val dans un tableau tab
        tab est supposé trié """

    # initialisation
    gauche = 0
    droite = len(tab) - 1
    
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tab[milieu] == val:
            # on a trouvé val dans le tableau,
            # à la position milieu
            return milieu
        elif tab[milieu] > val:
            # on cherche entre gauche et milieu - 1
            droite = milieu - 1
        else:             # on a tab[milieu] < val
            # on cherche entre milieu + 1 et droite
            gauche = milieu + 1

    # on est sorti de la boucle sans trouver val
    return -1


#tests

liste = [1, 3, 5, 7, 9]
print(liste)
for truc in [0, 42, 5 , 3, 7, 2, 8, 9, 1, -52]:
    print("Pour", truc, "on obtient",
          recherche_dichotomique(liste, truc))
[1, 3, 5, 7, 9]
Pour 0 on obtient -1
Pour 42 on obtient -1
Pour 5 on obtient 2
Pour 3 on obtient 1
Pour 7 on obtient 3
Pour 2 on obtient -1
Pour 8 on obtient -1
Pour 9 on obtient 4
Pour 1 on obtient 0
Pour -52 on obtient -1
>>>

C’est sans difficulté, puisqu’on vous avait donné ce document institutionnel (à comprendre jusqu’au milieu de la troisième page) et que ce code figurait au milieu de la deuxième page.


Prouver un algorithme – en deux temps (à savoir) :

  • Il faut prouver qu’il se termine : On parle de terminaison.

    On utilise ici un variant de boucle, en général

    • soit une variable qui augmente et ne peut pas dépasser un « plafond »
    • soit une variable qui diminue et ne peut pas passer sous un « plancher »
  • Il faut prouver qu’il fait bien ce que l’on attend de lui : On parle de correction.

    Pour cela, on va chercher un un invariant de boucle.

    C’est quoi un « invariant de boucle ? »

    C’est une propriété qui est vérifiée avant l’entrée dans la boucle,
    qui est vérifiée à chaque itération de la boucle et qui amène au résultat escompté à la sortie de la boucle.


Exemple facile pour commencer

Soit l’algorithme

def deux_puissance(n):

    assert n >=0

    #initialisation
    i = 0
    reponse = 1
    
    # traitement :
    while i < n : 
        i += 1
        reponse *= 2

    # terminé :
    return reponse

# tests
assert deux_puissance(0) == 1
assert deux_puissance(1) == 2
assert deux_puissance(2) == 4
assert deux_puissance(8) == 256

Cette fonction passe sans encombres les tests caractérisés par

  • les quatre assert en fin de code qui testent quatre valeurs de retour,
  • le assert en début de fonction qui teste les préconditions « n positif ou nul ».

Mais nous voulons prouver cet algorithme !

  • Terminaison :

    Le variant de boucle est clairement ici i qui augmente forcément avec l’incrémentation i += 1 dans la boucle while. Quand i atteint n, qui est forcément positif ou nul, l’algorithme termine. La terminaison est donc assurée.

  • Correction :

    On veut que le programme renvoie 2 ** n quel que soit n positif ou nul.
    L’invariant de boucle est par exemple ici la propriété

    « reponse vaut 2 ** i »

    • Avant la boucle, i vaut zéro et reponse vaut 1 soit 2 ** 0. OK
    • Si l’invariant « reponse vaut 2 ** i » est vraie à la fin d’un passage de la boucle, au passage suivant
      • i passera à i + 1
      • reponse vaudra reponse * 2 soit 2 ** i * 2 soit 2 ** (i +1). OK
    • Au sortir de la boucle, l’invariant est donc encore respecté et la dernière valeur de i est n donc « reponse vaut 2 ** n » et c’est bien la bonne valeur qu’on renvoie.
    • La correction est donc assurée.

Prouver notre algorithme de dichotomie

On s’appuie sur ce document institutionnel où il est prouvé.

Commentaires.


Et nos tris ?

Et bien pour les deux tris par sélection ou par insertion étudiés :

  • Un variant de boucle est rang initialisée à zéro puis incrémentée et qui ne dépassera pas len(tab). Ceci prouve la terminaison.
  • Un invariant de boucle est

    « les éléments sont triés jusqu’à rang »

    Souvenons-nous que nous l’avions bien souligné (et même encadré en vert). Ceci permet de prouver la correction.