Quelques remarques sur les TD :
Certains TD sont compressés à l'aide d'un logiciel libre d'archivage : 7-zip.
Ce logiciel est multiplateforme.
[voir la page wiki consacrée].
Il vous faut télécharger les outils de compression / decompression pour windows [7zip] ou macOSX [7zX] :
TD Révision 5/2 : méthode d'Euler explicite
Dans ce TD on souhaite modéliser la propagation de la lumière dans une fibre optique par deux méthodes de discrétisation.
La fibre optique étant un milieu d'indice variable, le rayon lumineux suit une trajectoire courbée.
La première méthode consiste à découper la fibre en strates horizontales parallèles à l'axe de la fibre et à appliquer les
lois de Descartes à chaque réfraction. A chaque étape on établit le déplacement à venir jusqu'à la nouvelle strate.
Cette méthode est la plus naturelle mais trouve vite ses limites.
La seconde méthode repose sur l'équation intrinsèque des rayons : équation locale qui met en jeu le gradient de l'indice optique. La formule permet de calculer à chaque pas de temps l'évolution du vecteur unitaire tangent au rayon par la
méthode d'Euler. On suit ainsi le rayon dans sa course à la manière d'un point matériel en mécanique.
TD 5/2 : Régression linéaire
Ce TD vous propose de calculer la droite de régression linéaire d'un nuage de point à partir des points de mesures,
tel que le ferait votre calculatrice mais en prennant de plus en compte les incertitudes sur les ordonnées seules.
On s'appuie pour cela sur des informations statistiques comme les moyennes et écart-types mais aussi sur les fonctions
de corrélation.
TD Révisions 3/2 : et plus si affinités ....
TD : Atome-H orbitale 1s
Méthode des trapèzes.
Ce TD de révision aborde le calcul numérique des intégrales, la recherche de maximum
et le tracé de fonction.
TD : Recherche de zéros
Méthode de Newton / Méthode par dichotomie
Ce TD de révision concerne la recherche numérique de zéros de fonctions analytiques.
TD : Ecriture en chiffres Romains
Travail sur les listes et les chaines.
Ce TD de révision concerne la conversion d'une écriture décimale en écriture romaine et réciproquement.
TD : Structure de données I
Les piles et les queues.
Dans ce TD on construit des objets Pile et Queue ainsi que les méthodes de base sur ces structures fondamentales.
Base de Données I
Ce TP a pour but de s'entrainer à la formulation de requêtes SQL [Structured Query Language], avec la base de données
W3schools accessible et utilisable en ligne :
www.w3schools.com : partie SQL
Cette base de données possède huit tables reliées entre elles et des centaines d'entrées.
Le site propose en à-coté un formulaire qui vous permet de revoir et de tester en direct les différents éléments
de syntaxe de ce langage relationnel :
SQL Tutorial
Le TP consiste en une suite de questions formulées dans le langage courant, à la manière des épreuves de concours.
Détection d'alignements simples... 3/2
... dans un nuage de points ...
On se donne un nuage de N points dans le plan comme une liste de tuples où chaque tuple contient les coordonnées (x,y) d'un point.
Au sein du nuage, on recherche les alignements de 3 points consécutifs.
On peut prendre en exemple le nuage simple suivant :
listePoints=[(0,0), (1,0), (2,0), (1,1), (3,1), (1,2), (0,3), (2,3), (3,3)]
1 - Représenter ce nuage et trouver les alignements à la main. (voir ci-dessus)
2 - Ecrire une fonction sontAlignes(P1, P2, P3) qui prend en argument trois points et renvoie True si les points sont alignés.
On appellera "point" la donnée d'un tuple (x,y) des coordonnées du point dans le plan.
3 - Ecrire une fonction trouveAlignement(nuage), qui prend en argument un nuage, et renvoie la liste de tous les alignements
de 3 points trouvés au sein du nuage. On appellera alignement une liste de 3 points qui sont alignés, soit la liste de 3 tuples.
La fonction renvoie donc une liste de liste de 3 tuples.
4 - On souhaite que l'algorithme détecte chaque alignement une fois et une seule. Est-ce le cas du votre ?
Sinon, comment s'en assurer ?
5 - Que se passe-t-il lorsque 4 points ou plus encore sont alignés ? On pourra rajouter des points au nuage pour faire des essais.
6 - Ecrire une fonction affiche(nuage, alignement), qui représente l'ensemble des points par un point vert, et trace les
alignements de points trouvés au sein du nuage.
7 - Quelle est la complexité de votre algorithme ?
8 - Question ouverte :
- Comment peut-on étendre cet algorithme à la recherche d'alignements de k points ?
- Quelle en serait la complexité ?
- Quelle difficulté se pose en terme de codage si k est une valeur arbitraire ?
Peut-on proposer un algorithme plus général valide pour rechercher des alignements de toute taille ?
Algorithmique : Recherche d'alignements 5/2
Du bon usage des tris :
trouver des alignements dans un nuage de points
Les objectifs algorithmiques sont de trouver :
- tous les alignements
- pour un nombre k de points quelconque
- chaque alignement étant unique
- Et dans un minimum de temps.
PROJET : Le voilier solaire
Méthode d'Euler en coordonnées polaires
Mouvement dans un champ de force "centrales conservatives" ?
Ce projet aborde la méthode d'Euler explicite sur l'exemple du calcul de la trajectoire d'un voilier solaire,
poussé par la pression de radiation électromagnétique sur sa voile. L'intérêt technique est ici que l'on doit
implémenter cette méthode en coordonnées polaires (et non en cartésiennes) car les angles sont importants pour le
calcul de la poussée.
Le document ci-joint est un B.U.P. et contient des erreurs dans les formules que l'on vous demande de retrouver
#attrapezLesTous. Il faut donc dans un premier temps re-démontrer toutes les formules de la dynamiques du voilier,
ainsi que l'énergie réduite et l'angle optimisé. A vous aussi de donner du sens à ces expressions.
Dans un second temps je vous fournirai un code python à compléter. Le but étant de retrouver les courbes obtenues dans ce B.U.P.
et de les interpréter en révision du chapitre de physique de sup. "mouvement dans un champ de force centrale".
Rq : Ce document était anciennement donné aux concours en Analyse de Documents Scientifiques (ADS) avec les fautes, qui font de fait partie de l'exercice.
Algorithmique : Enveloppe Convexe !
Du bon usage des tris :
trouver l'enveloppe d'un nuage de points
Les applications de ce problème sont multiples :
- reconnaissance de forme
- détermination de contour
- contournement d'obstacle
- convexité d'un N-gone
BioInformatique
Code génétique
Recherche et traduction de Gènes.
Dictionnaires et compréhension de listes
Ce TD porte sur l'étude des chaînes de caractères 'A' 'C' 'G' et 'T' dans l'ADN de la bactérie Escherichia Coli,
et de sa traduction en séquence d'acides aminés pour former des protéines.
Marche aléatoire
Recherche d'effet de repli de l'ADN d'une bactérie
impliquée dans la maladie de Lyme
Ce TD se propose de tracer une carte de l'ADN sous forme de marche aléatoire, puis on utilise une étude
fréquentielle des couples de nucléotides 'GC' et 'AT' pour mettre en évidence une séquence palindromique.
Optique géométrique
Réflexion d'un faisceau lumineux
Application de la loi de Descartes pour une surface
dont le profil est modifiable à volonté.
Ce TD propose de mettre en place sur une méthode de recherche des points d'impacts par extrapolation linéaire
des vecteurs incidents. On y revient ausssi largement sur les représentations graphiques.
Introduction aux Graphes
TD I : Introduction aux graphes
Trois représentations des graphes
Ce TD propose de réaliser des opérations simples sur les graphes, pour se familiariser avec ces structures de données.
Les graphes y sont abordés par la donnée de leurs cotés, la matrice d'ajacences et la liste d'adjacences.
TD II : Listes d'adjacences
Les algorithmes de base sur les graphes
Ce second TD va nettement plus loin avec les graphes en abordant les parcours de graphe,
la recherche d'un arbre de recouvrement etc...
Autres problèmes d'algorithmique
knapSack : Le PB du sac à dos
Différentes approches algorithmiques
Il s’agit ici d’un grand classique de l’algorithmique, l'intérêt de ce problème est la quantité de démarches possibles pour son approche et aussi le fait qu’on peut vouloir trouver vite une « bonne » solution ou chercher la garantie d’avoir la « meilleure » solution possible.
Base de données 2 : SQL ZOO
Révision de SQL :
Exploration du zoo de SQL !
Le site sqlzoo.net vous propose différentes bases de données (et plutôt amusantes ...) pour vous entrainer à la rédaction de reqêtes SQL. Le site est organisé par type de requêtes allant des plus simples aux plus compliquées. Le site étant très vaste mon corrigé ne sera pas exhaustif !
sqlZOO !!!
Corrigé
Notion de class : introduction aux objets !
création d'une class "bidon"
UNE JOURNEE EN ENFER : Die Hard 3
Bruce Willis et Samuel Lee Jackson doivent résoudre l'énigme suivante pour sauver la ville de New York :
"A une fontaine, on dispose de deux bidons :
un de 3 litres et un de 5 litres.
Comment peut-on obtenir 4 litres d'eau ?"
Vous avez 30 secondes !!!
L'objectif de ce TP est d'apprendre à créer un objet en Python, en l'occurence un bidon de capacité fixée.
On veut pouvoir remplir le bidon, le vider totalement, ou verser son contenu dans un autre objet bidon.
Le fichier vous donne la classe avec son constructeur et son afficheur, et vous devez compléter les corps de
fonction pour les opérations de base.
Le fichier est compressé avec 7zip. Merci de télécharger le décompresseur (en haut de page).
TD COURS : Réalisation d'une class vecteur
Ce TD a pour but d'implémenter une classe d'objets vecteur en python pour se familiariser avec la notion de classe
sur un exemple simple, mais la démarche , très générale, sera toujours la même. Nous corrigerons cet exemple en classe.
L'enjeu d'une classe est l'encapsulation d'un ensemble de propriétés qui sont spécifiques à un objet :
- obtenir des attributs de l'objet, ici dimension & composantes
- calculer une norme pour un objet vecteur
- fabriquer un objet vecteur par le produit vectoriel de deux objets vecteurs
L'encapsulation signifie que ces informations ou opérations ne seront possibles que pour ce type d'objet ce qui permettra
facilement de garantir qu'une action effectuée est bien autorisée. On ne risque pas par exemple de tenter de faire le produit
vectoriel à partir d'un entier ou même d'un tuple.
Le travail a réaliser est détaillé dans le fichier python et doit être fait pour la semaine prochaine.
Ce n'est pas très difficile mais il faut bien lire l'entête de fichier qui donne des informations complémentaires.
A lire également : le cours sur les classes en python et surtout les exemples associés.
Nous corrigerons ensemble en classe.
TP-COURS 6 : Réalisation d'une class matrice
Ce TP fait suite à celui sur la classe vecteur mais demande beaucoup plus de travail.
1 - Une première partie s'attache à créer la classe matrice en elle même. Il y a beaucoup de méthodes à coder,
mais chacune est une fonction "simple" :
faire la somme ou le produit de deux matrices, calculer le déterminant, la matrice inverse etc...
Pour chaque méthode, on se posera la question du coût algorithmique ou complexité
pour réaliser l'opération.
2 - La seconde partie concerne la résolution d'un système linéaire par la méthode du pivot de Gauss, dans le cas
général d'une matrice n*n. On compare ensuite cette résolution avec celle utilisant directement la matrice inverse.
Résolution de problème : Diving for pearls !
Travail pour les vacances
Les coquillages ci-dessous contiennent des perles et on souhaite en attraper un maximum !
Problème : lorsque l’on prend les perles d’un coquillage, ses voisins immédiats
(gauche et/ou droite) se referment aussitôt !
Objectif : proposer un algorithme qui permette d’attraper systématiquement le nombre de perles maximal
et qui soit le plus rapide possible.
On traitera à titre d’exemple et sur papier les trois situations suivantes :
Généraliser votre méthode à toute liste et proposer une implémentation en python de votre algorithme.
Remarques : il existe des tas de méthodes possibles mais :
- toutes ne trouvent pas la somme optimale.
- toutes ne sont pas aussi rapides.
TD COURS RECURSIVITE : Les tours de Hanoï
Le projet suivant consiste en une classe dite Hanoï [représentant le jeu des tours de Hanoï dans son ensemble],
et cette classe contient elle-même une classe Tour permettant de créer les 3 instances de tours.
Tout ce qui relève des classes (constructeur, attributs, méthodes et affichage) vous est donné.
En revanche :
On vous demande de coder la résolution du jeu : mouvement d'une tour de hauteur n avec l'approche récursive vue en cours.
De plus la classe Tour n'est rien de moins qu'une structure de pile et vous devez coder les corps de fonction des méthodes
push(pierre) et pull().
Modélisation numérique de la diffraction avec Numpy !
On Souhaite pouvoir calculer l'intensité diffractée sur un écran pour toutes les formes de diaphragmmes possibles.
En général, le calcul littéral n'est possible que pour des formes très simples. On montre ci dessous l'exemple de la diffraction
à travers des trous de Young, soient deux trous circulaires espacés d'une distance a. On note que la diffraction combine la tache
d'Airy d'une ouverture circuaire avec les franges associées aux fentes de Young.
Dans ce programme on a créé des fonctions pour générer les tableaux numpy représentant les diaphragmmes.
On créé de même un tableau numpy réprésentant les différentes positions sur l'écran.
On imagine alors chaque case du tableau du diaphragmme comme une source de lumière secondaire, selon la théorie de Fresnel.
Soit M un point sur l'écran :
On calcule l'onde totale reçu en M en sommant (en complexe) les ondes provenant de toutes les sources émettrices. On en déduit
l'intensité en M. On procède de même pour tous les points de l'écran.
Tous les calculs seront menés à l'aide du module Numpy (Numerical Python) et à l'aide des compréhensions de listes. On testera
toujours le code sur de petites tailles de tableaux, car les temps de calculs deviennent vite très très longs.
Analyse de Fourier
Dans ce TP on veut étudier l'évolution temporelle d'une onde stationnaire sur une corde à l'aide de l'analyse de Fourier.
On se donne pour cela une fonction (sinusoïde, triangle ou autre) représentant la déformation de la corde à l'instant initial.
La corde est attachée à ses deux extrémités et on suppose que la corde est lâchée sans vitesse initiale.
On se donne une fréquence de vibration qui est un La 440Hz.
1 - Dans une première partie on cherche à calculer les coefficients de Fourier bn de façon numérique.
On peut ainsi tracer le spectre associé aux modes de Fourier de l'onde stationnaire.
2 - Dans un second temps on trace la fonction théorique de départ représentant la forme de la corde,
et on superpose sa restitution numérique à t=0 à l'aide de la synthèse de Fourier.
3 - Enfin on trace l'évolution de la forme de la corde au cours du temps sur une fraction de la période.
Problème d'algorithmique : l'âge du capitaine
... un problème d'âge en somme ...
On considère une liste de valeurs entières positives qui pourraient représenter les âges des membres d'un équipage, et
une valeur cible qui est l'âge du capitaine. On veut trouver si elles existent, toutes les paires de deux membres
d'équipage dont la somme de leurs deux âges respectifs est exactement égale à l'âge du capitaine !
L'idée algorithmique est que le nombre N des membres de l'équipage [soit la taille N du tableau] peut devenir gigantesque
et on veut trouver l'algorithme qui trouve la solution dans un temps minimum !
Vous pouvez envisager deux algorithmes assez naturellement, il existe d'autres solutions encore.
"Old Captain" 2013 Гари-Николай Ангелов (Gary-Nikolai Angelov)
A vous de créer votre fichier Python ! On attend simplement une fonction :
-> qui prend en argument un tableau d'entiers positifs, et un entier cible positif.
-> qui renvoie la liste des paires de valeurs solutions, c-à-d une liste de tuple (i,j).
Le nombre de solutions sera donc la longueur de la liste, la liste sera donc vide si il n'y a pas de solution.
Exemple :
solution([9, 14, 2, 7, 3, 6, 3], 9) -> [(7, 2), (6, 3), (3, 6)]
solution([2, 7, 11, 15], 3) -> []
TD COURS :
Expérience numérique de percolation
Besoin d'un café ? La percolation est partout :
- physique & chimie des matériaux,
- biologie : transmission des maladies génétiques et MST, flores bactériennes,
- réseaux sociaux, reseau neuronal,
et même dans le percolateur de votre machine à expresso !
Problème : il n'y a pas de traitement mathématique satisfaisant de la percolation, mais des expériences numériques
permettent de simuler le phénomène. C'est le cas ici dans un échantillon à 2-dimensions.
Le TP suivant se propose ici de mesurer numériquement le taux d’impuretés à introduire dans un milieu à deux dimensions
pour que le courant traverse l’échantillon. Cette modélisation est analogue à l’introduction de micro-canaux pour l’écoulement
d’un fluide par porosité et bien d’autres choses.
Deux électrodes sont soudées aux extrémités de l’échantillon et chaque impureté permet la connexion électrique avec ses voisins du haut, du bas, de gauche et de droite.
Le chemin de connexion est inconnu et la grille peut être très grande N >> 1 ; il faut donc s’appuyer sur une structure de données efficace pour répondre à la question « est-ce que les points de départ et d’arrivée sont connectés ». On utilise ici la classe Quick Find [qui est déjà rédigée en début de code]. C’est la plus simple mais pas la plus rapide.
Oral de physique Centrale-Supelec :
Exemples de sujets où Python est mis en jeu.
Les deux exemples suivants permettent de se faire une première idée des attentes en "informatique" à l'oral.
Globalement il s'agit simplement d'utiliser un programme tout fait et de jouer avec les paramètres physiques.
Dans le premier cas il y a une réelle part de modélisation informatique :
il s'agit du redressement de courant alternatif en courant continu (tel que vous avez pu le faire en TP de physique).
Le problème est a traiter aussi bien sur papier qu'avec le code python.
Dans le second cas il s'agit simplement d'alimenter la discussion si il reste du temps. Le problème est a faire sur papier
(attention il peut y avoir des fautes dans l'énoncé....).
Le programme réalise pour vous le tracé dynamique des champs électrique et magnétique au cours du temps.
Dans les deux cas en revanche le fichier python est très intéressant car si vous le comprenez, il apporte des informations
sur les calculs attendus dans l'exercice => n'attendez pas la dernière minute pour y jeter un oeil !
