Information and scientific computation (for MAN)

PREPA-094 / coefficient 6

Teacher: Hardiman Leonard Paul Arthur

Language: French

Résumé

Une introduction à la programmation Python est donnée en parallèle de l'algorithmique (recherche, tri, graphes) et de l'analyse numérique (équations non linéaires, intégration numérique). Les méthodes sont analysées, implémentées et comparées.

Contenu

Programmation Python

Langage Python : types, variables, fonctions, portée, modules
Flux de contrôle : conditions, boucles, itérables
Structures de données : tuples, listes (mutabilité, références), dictionnaires, compréhensions
Bibliothèques scientifiques : NumPy (tableaux, vectorisation) et Matplotlib (2D, 3D)

Algorithmique

Algorithmes, correctitude et récursivité
Complexité asymptotique
Algorithmes de recherche
Algorithmes de tri
Algorithmes sur les graphes

Analyse numérique

Résolution d'équations non linéaires par méthodes numériques
Intégration numérique

Mots-clés

Programmation, Python, Jupyter Notebook, listes, dictionnaires, NumPy, Matplotlib, algorithmique, invariant de boucle, récursivité, complexité asymptotique, recherche linéaire, recherche binaire, tri par sélection, tri par insertion, tri par fusion, graphes, matrice d'adjacence, liste d'adjacence, BFS, DFS, plus court chemin, arbre couvrant, méthodes numériques, équations non linéaires, bissection, méthode de la corde, méthode de la sécante, méthode de Newton, méthode de point fixe, ordre de convergence, formules de quadrature, formules de Newton-Côtes, formule de Simpson.

Acquis de formation

A la fin de ce cours l'étudiant.e doit être capable de:

Concevoir des programmes Python afin de résoudre des problèmes proposés et en respectant des consignes spécifiées
Analyser des programmes Python donnés (y compris comprendre leur but, expliquer leur fonctionnement, corriger d'éventuelles erreurs, anticiper leurs résultats, améliorer leur conception)
Résoudre une équation non linéaire en utilisant une méthode numérique appropriée
Calculer une intégrale définie en utilisant une méthode numérique appropriée
Concevoir et/ou analyser un programme qui implémente en langage Python une méthode numérique donnée
Utiliser les bibliothèques NumPy, Matplotlib et SciPy afin d'implémenter une méthode numérique donnée
Concevoir des algorithmes de recherche, de tri et des algorithmes sur les graphes, et analyser leur complexité
Démontrer la correctitude d'un algorithme

Méthode d'enseignement

Cours ex cathedra et travaux pratiques sur ordinateur. Une grande partie des séances consacrées à Python se déroule sous forme de classe inversée : les étudiant.e.s préparent le contenu à l'avance, le temps en salle étant consacré à la pratique et aux questions.

Méthode d'évaluation

Examen écrit

Encadrement

Office hours	Non
Assistant.e.s	Oui
Forum électronique	Oui

Ressources

Bibliographie

Notes de cours disponibles en ligne

C.D. Petrescu, Polycopié "Informatique et calcul scientifique (ICS - MAN) - Première partie - Programmation Python", EPFL

G. Swinnen, Apprendre à programmer avec Python 3, Eyrolles, 2012, ISBN : 9782212134346

J. Guttag, Introduction to Computation and Programming Using Python : With Application to Understanding Data, Second Edition, MIT Press, 2016, ISBN : 9780262529624

Documentation for Python 3 (https://docs.python.org/3/)

NumPy (https://numpy.org/)

Matplotlib: Visualization with Python (https://matplotlib.org/)

SciPy library (https://www.scipy.org/scipylib)

A. Quarteroni, R. Sacco, F. Saleri, Méthodes Numériques. Algorithmes, analyse et applications, Springer, 2007, ISBN : 9788847004955

J. Rappaz, M. Picasso, Introduction à l'analyse numérique, Presses polytechniques et universitaires romandes, 1998, ISBN : 9782889151936