Depuis son apparition durant la seconde guerre mondiale, l'informatique n'a cessé de transformer profondément la société. La science et les différents domaines de l'ingénieur sont aujourd'hui de plus en plus dépendants de l'informatique pour des besoins de calcul ou de simulation notamment. Dans un rapport récent [1], plusieurs scientifiques ont mis en avant les liens de plus en plus forts entre l'informatique et les différentes disciplines scientifiques. Ils vont même jusqu'à prévoir l'émergence de nouvelles formes de "sciences" qui feront la synthèse entre les sciences ou les métiers traditionnels de l'ingénieur et l'informatique. Dès aujourd'hui, cette synthèse a créé de nouveaux domaines comme la bioinformatique qui fait le lien entre la biologie moléculaire et l'informatique, la climatologie dont les prédictions dépendent d'ordinateurs de plus en plus puissants, mais aussi les nanotechologies où les modélisations informatiques sont essentielles pour comprendre les interactions entre atomes et molécules ou la physique des particules où des équipements tels que le Large Hadron Collider (LHC) installé récemment au CERN à Genève produisent des quantités de mesure tellement gigantesques qu'il faut utiliser des milliers d'ordinateurs pour les traiter.
Si les ordinateurs sont tellement utiles pour résoudre des problèmes scientifiques ou d'ingénierie c'est grâce à leur puissance de calcul. Cette puissance de calcul est à deux niveaux : matériel et logiciel. Au niveau matériel, les processeurs utilisés dans les ordinateurs actuels sont capables d'effectuer très rapidement des additions, multiplications, divisions, soustractions et comparaisons de nombres réels.
Pour cette mission, vous devez écrire un programme Python qui permet de trouver les solutions entières à des équations du style :
Vous constaterez que l'énoncé de cette mission est plutôt directif. Dans les problèmes suivants, la mission sera bien moins explicite et une partie du travail de préparation consistera à la préciser.
| [1] | Towards 2020 Science, disponible depuis http://research.microsoft.com/towards2020science/ |
Conditions à remplir pour pouvoir résoudre le problème :
A l'issue de cette mission, chacun d'entre vous :
sera en mesure de dire quelques mots sur certains concepts sous-jacents à un programme Python simple :
- types de données
- chaînes de caractères
- opérations arithmétiques
- opérations booléennes
- appel de fonction
- boucles for
sera en mesure d'utiliser l'environnement de travail Thonny pour traiter des programmes écrits en Python et de soumettre son travail au serveur de correction.
Vous devez lire et comprendre ces parties du syllabus pour pouvoir mener à bien cette mission :
Rappelez-vous qu'il est impossible d'atteindre les objectifs visés par ce problème sans effectuer préalablement le travail d'étude individuel en consultant les sections du livre de référence.
Les questions qui figurent ci-dessous sont des exemples de questions que vous pourriez vous poser à la lecture de l'énoncé et des ressources qui s'y rapportent. Si vous avez convenablement fait ce qui était attendu de vous pendant la phase d'étude et d'apprentissage, vous devriez être en mesure de répondre sans difficulté à ces questions. Si ce n'est pas le cas, il est encore temps de rattraper votre retard (mais ne tardez pas trop !). Il ne faut en aucun cas commencer la phase de réalisation avant d'être en mesure de répondre à ce questionnaire.
Pour chaque question, indiquez toujours où vous avez trouvé les éléments de réponse (livre page ..., documents fournis, manuels en ligne, ...). Travaillez en deux temps:
Visez à fournir des réponses complètes, motivées et qui prouvent votre compréhension de la matière. Ne vous contentez pas de réponses superficielles.
Pour vous aider dans la réalisations de ces exercices, certains d'entre eux sont disponibles sur Inginious avec une correction automatisée. Il a été fait en sorte que cette correction automatique soit utile à votre compréhension de la matière, cependant cela ne doit pas vous empêcher de discuter de vos réponses, correctes ou non, avec votre tuteur et les membres de votre groupe.
Définissez les concepts suivants :
Dans l'extrait de programme ci-dessous, indiquez après chaque ligne les valeurs contenues dans les variables a, b, c.
a = 0 b = 1 c = 2 a = b # ligne 1 a = a*2 # ligne 2 b = 17 # ligne 3 c = a+b # ligne 4 a = b-c # ligne 5 c = a+b+c+a # ligne 6
Expliquez, avec vos propres mots, ce que représente la notation
i = i + 1
et ce qu'elle a comme effet. Pourrait-on la remplacer par une autre notation ?
Quelle est la relation entre une instruction et une expression ? Donnez des exemples.
Expliquez ce que produisent les instructions suivantes :
Que se passe-t-il si on exécute ce programme ? Comment peut-on le corriger ?
n = input("n = ? ") print("n^2 =", n ** 2)
Expliquez ce que produisent les instructions suivantes :
Que fait le programme suivant ?
for n in [0, 1, 2, 3, 4]: print(10 ** n)
Comment pourrait-on écrire autrement la boucle for ?
Complétez le fragment de code suivant:
# Place dans sum la somme des n premiers entiers pairs strictement positifs n = some_value sum = 0 for ___ in ___________: ______________
Etape d'une boucle for :
Pour plus de détails sur les étapes, allez voir le catalogue .
Un nombre premier est un nombre naturel plus grand que 1 et qui n'a pas d'autres diviseurs positifis à part 1 et lui-même.
Stockez dans is_prime True si le n est un nombre premier et False sinon. is_prime est initialisé à True par défaut.
Les variables ont été initialisées. Ils vous restent à déterminer la séquence, écrire la condition de traitement si nécéssaire, le corps de la boucle et vérifier les cas particulier. Pour plus de détails sur les étapes, allez voir le catalogue .
is_prime = True n = ... #Un entier supérieur à 1
Remarques importantes
On ne commence ce travail de réalisation qu'après la réunion du bilan intermédiaire et en ayant déjà fait un premier travail d'étude dans le livre de référence.
Chaque étudiant dispose, sur le système informatique de l'EPL, d'un espace de travail qui lui est propre et auquel il accède en démarrant une session par un login sur n'importe lequel des postes de travail (en salles Candix/IAO/DAO). Les fichiers créés ou modifiés par un étudiant ne sont donc pas directement accessibles à un autre étudiant (il n'y a pas de partage de fichiers entre étudiants). Une manière simple d'échanger des fichiers entre étudiants d'un sous-groupe consiste à se les envoyer en annexe ("attachment") à un courrier électronique.
Durant cette partie de la mission vous allez écrire un petit programme Python permettant de rechercher les racines entières d'une équation diophantienne :
Cette recherche se fera en énumérant toutes les valeurs possibles de x, y et z et en vérifiant pour chacun triplet de valeurs si l'équation diophantienne est vérifiée (attention, vous ne pouvez pas utiliser les fonctions du package math dans cette mission). Cette technique d'énumération est parfois utilisée dans le domaine de la sécurité informatique pour décoder des messages cryptés sans connaître la clé de cryptage qui a été utilisée. Elle s'appelle attaque par force brute ou recherche exhaustive.
Groupes : A partir de cette deuxième mission, vous travaillerez en binômes de deux étudiants. Associez-vous en binômes au sein de votre groupe ou de votre local. Si vous êtes en nombre impair dans votre local, un étudiant devra travailler seul. Vous devrez travailler avec un étudiant différent chaque semaine; organisez une tournante des binômes.
Organisation : Décidez comment vous allez faire, dans votre sous-groupe, pour travailler à deux : est-ce toujours le même qui travaille à l'ordinateur ou allez-vous alterner au milieu de la mission ? Que fait celui qui n'est pas à l'ordinateur pour aider celui qui l'est ? A quel moment faut-il aller consulter le livre de référence ? Faut-il avoir lu toutes les sections du livre indiquées dans la rubrique Ressources avant de faire le travail ?
Analyse : Considérez le programme ci-dessous :
# Recherche des racines d'une équation a x + b y = c
# Charles Pecheur, septembre 2018
solutions = 0
a = int(input("Entrez la valeur du coefficient a : "))
b = int(input("Entrez la valeur du coefficient b : "))
c = int(input("Entrez la valeur du coefficient c : "))
max = int(input("Entrez la valeur maximale pour x et y : "))
for x in range(1, max+1):
for y in range(1, max+1):
if a*x + b*y == c:
print("x =", x, " y =", y)
solutions += 1
if solutions == 0:
print("Aucune solution trouvee")
else:
print(solutions, "solutions trouvees")
Ce programme recherche les racines entières de l'équation diophantienne simple ax + by = c. Essayez de le lire et de bien comprendre comment il fonctionne. Dans Thonny, recopiez le programme dans un fichier equation_simple.py (copiez-collez à partir du syllabus) et testez-le en l'exécutant avec différentes valeurs de a, b et c. Vérifiez notamment que l'équation 8 x + 4 y = 1 n'admet aucune solution alors que l'équation 2 x + y = 3 en admet une infinité.
Vous pouvez inspecter les valeurs des différentes variables en affichant le panneau des variables (menu View > Variables) et en exécutant le programme pas à pas (bouton Debug). Attention, vous devez interrompre votre programme en cours d'exécution (bouton Stop) avant de pouvoir lancer une nouvelle exécution.
Vous pouvez maintenant créer un nouveau programme equation.py permettant de trouver des solutions à des équations diophantiennes du type xa + yb = zc.
Si vous n'obtenez pas le bon résultat, analysez ce qui se passe et corrigez jusqu'à obtention du résultat désiré. Cette phase de test est essentielle dans le développement d'un programme. Indiquez dans le fichier README.TXT que vous renverrez à votre tuteur les tests que vous avez réalisés pour le convaincre du bon fonctionnement de votre programme.
N'oubliez pas de bien documenter votre programme en utilisant des commentaires.
Si vous avancez vite, modifiez votre programme de façon à ce qu'il n'affiche que les racines qui n'ont aucun diviseur commun à l'exception de 1. Pour cela, vous devrez écrire un programme permettant de vérifier si trois nombres ont un diviseur commun. En Python, l'expression a % b calcule le reste de la division euclidienne de a par b. Cela pourrait vous aider dans cette extension.
Soumettez votre travail au serveur de soumission. Indiquez dans le fichier README.TXT les tests que vous avez effectués et les problèmes éventuels que vous avez eu. Votre tuteur pourra les lire afin de préparer la réunion de bilan final.
| [1] | Voir notamment http://www.alpertron.com.ar/SUMPOWER.HTM |
Pour cette mission, vous devez soumettre votre programme equation.py et votre fichier README.txt au serveur de soumissions de programmes du cours.
Les étudiants qui ont résolu rapidement ce problème sont invités à écrire un programme permettant de résoudre le problème suivant.
En mathématiques, depuis les travaux de Fermat, on sait qu'il n'existe pas de quadruplet de nombres entiers positifs distincts a, b, c et n tels que an + bn = cn lorsque n > 2. Le théorème correspondant a d'ailleurs été démontré il y a seulement quelques années. Par contre, il existe de nombreux quadruplets de nombres entiers positifs distincts a, b, c et d tels que a3 + b3 = c3 + d3. En utilisant un programme qui teste intelligemment tous les quadruplets possibles en utilisant des boucles for, pourriez-vous déterminer quel est le quadruplet pour lequel la somme a3 + b3 = c3 + d3 est minimale ?
Supposez que les variables a, b et x contiennent un nombre naturel. Ecrivez un fragment de code qui assignerait la valeur booléenne True à une variable nommée interval si x appartient à [a, b]. Assignez la valeur False sinon.
Supposez que les variables a, b et c contiennent un nombre naturel.
Ecrire un fragment de code qui assigne à la variable min le plus petit de ces nombres.
Ecrivez un programme qui permet de jouer au jeu fizzbuzz. Vous recevez un nombre (stocké dans la variable i). Nous allons implémenter une version simplifiée du jeu. Pour un entier i donné, le jeu va :
Supposez que les variables a et b contiennent un nombre naturel.
Ecrivez un fragment de code qui assigne le reste de leur division à la variable rest.
Pour implémenter votre solution, utilisez uniquement une boucle while et des soustractions (la solution la plus simple rest = a % b n'est pas acceptée; nous voulons tester si vous êtes capable d'implémenter une telle opération par vous-même).
Notez que vous ne devez pas permettre la division par 0 et vous devez assigner la la valeur None à rest dans un tel cas.