1. Présentation du cours

1.1. Avant-propos

Author:Thierry Massart <tmassart@ulb.ac.be>
Version:2.1.4
Date:sept. 16, 2016
Copyright:This document has been placed in the public domain.

1.2. But du cours

Le but premier de ce cours et des exercices associés est de donner aux étudiants une connaissance active de l’algorithmique de base et de la programmation structurée. Le formalisme utilisé pour décrire les programmes développés dans ce cours est le langage de programmation Python.

Notons que, bien qu’une certaine partie de la syntaxe et sémantique du langage Python soit étudiée, ce cours n’est pas simplement un manuel de programmation Python. De nombreuses parties de Python n’y sont d’ailleurs pas étudiées.

Les concepts de base Python utilisés dans le cadre de ce cours pour écrire un algorithme ou un programme Python résolvant un problème algorithmique donné sont peu nombreux. Le cours théorique sert à expliquer ces concepts. Il ne vous est pas seulement demandé de comprendre ces notions de base, mais également de les assimiler et de pouvoir les utiliser pour concevoir et dans une moindre mesure analyser, des programmes Python résolvant les problèmes posés. La résolution de nombreux exercices ainsi que les travaux à effectuer vous permettront d’arriver à une connaissance de l’algorithmique beaucoup plus profonde, requise au terme de ce cours. Cette matière doit donc être pratiquée de façon constante à la fois pendant et en dehors des séances d’exercices sur papier et sur machine. Une étude entièrement comprise dans une courte période de temps ne peut pas aboutir au but final requis.

De façon complémentaire, ce cours aborde d’autres aspects essentiels pour maîtriser la matière: nous y verrons comment évaluer l’efficacité d’un algorithme (complexité); nous verrons également comment décrire formellement l’état d’un programme et des bribes de la théorie visant à prouver qu’un programme est correct; nous placerons également Python dans le paysage des langages à la fois au niveau historique et pour les concepts et paradigmes manipulés.

Note

Le cours ne vise donc pas à passer en revue d’ensemble des notes mises à votre disposition. L’ordre de présentation ainsi que les éléments présentés au cours peuvent différer de celui donné dans ces pages. L’étudiant est invité à lire ces notes ainsi que les références données ci-dessous, en particulier le livre de Gérard Swinnen sur Python 3 (principalement les 11 premiers chapitres), avant d’assister au cours.

1.3. Compétences principales visées

Si vous avez suivi avec fruit le cours, vous aurez améliorer les compétences suivantes :

  • L’apprentissage autonome : vous serez dans une dynamique d’apprentissage autonome et permanent dans ce domaine en constante et rapide évolution qu’est l’informatique ; vous pouvez vous adapter tout au long de votre carrière aux technologies nouvelles. Par exemple, vous apprendrez, en vous référant aux manuels.
  • La résolution de problèmes : vous aurez la capacité d’analyser des besoins, de structurer l’information, de concevoir, modéliser et implémenter des solutions pertinentes et efficaces ; de façon plus globale on vous demandera dans les cours d’informatique d’acquérir la “pensée informatique” (“computational thinking”) en étant capable de faire des abstractions adéquates pour un problème, et d’allier la théorie à la pratique avec l’ordinateur comme support;
  • La communication : vous pourrez comprendre les problèmes posés, et expliquer les solutions proposées ; vous pourrez utiliser la communication scientifique et technique (formalismes mathématiques).

En particulier vous pourrez:

  • démontrer une bonne compréhension des concepts de base de Python ainsi que lire et comprendre des programmes existants
  • analyser un problème simple et proposer une solution informatique pour le résoudre et la mettre en oeuvre en Python
  • exprimer formellement, en formalisme logique, les fonctionnalités attendues d’un programme informatique
  • utiliser des outils informatiques de support à la programmation; exploiter la documentation technique
  • réaliser des programmes Python corrects et bien structurés
  • identifier les cas de test pour valider ces programmes.

1.4. Ressources

1.5. Pourquoi Python ? (et pas C++, Java, ...)

Python est un langage créé début des années nonante par Guido van Rossum

  • de haut niveau multi-paradigmes (programmation impérative, orientée-objet, fonctionnelle,...)
  • qui permet d’illustrer rapidement et simplement de nombreux concepts de programmation
  • portable
  • interprété
  • doté d’un typage dynamique fort, d’un ‘’Garbage collector’’ (ramasse-miettes) et d’une gestion des exceptions

Ces concepts seront expliqués lors du cours.

1.6. Un peu de vocabulaire

Le but de l’informatique est d’effectuer du traitement de l’information.

L’information est un ensemble d’éléments qui ont une signification dans le contexte étudié. Les données d’un problème sont représentées par l’ensemble des informations utilisées pour résoudre ce problème en vue d’obtenir les résultats escomptés.

Un algorithme n’est pas conçu uniquement pour obtenir un résultat pour une donnée bien précise, mais constitue une méthode qui permet, à partir de n’importe quelle autre donnée du même type, d’obtenir le résultat correspondant.

Un problème algorithmique peut être vu comme une fonction f dont l’image de toute donnée d de l’ensemble D des données possibles est un résultat r (= f(d)) de l’ensemble R des résultats possibles.

L’algorithme qui résout le problème est la méthode calculant f(d) en un temps fini, pour toute donnée d valide.

Notons qu’il n’existe pas d’algorithme pour tout problème (Il est donc intéressant de déterminer théoriquement l’existence d’un algorithme pour un problème donné avant d’essayer de l’écrire effectivement). A côté de cela, il existe souvent de nombreux algorithmes pour résoudre un problème donné; leurs qualités propres permettront de les différencier.

Un algorithme doit être implémenté sur un ordinateur. Celui-ci ne possède jamais qu’un nombre limité de mémoire de stockage d’information dont la précision est limitée. De ce fait pour résoudre certains problèmes qui en théorie pourraient requérir un calcul trop long, ou une précision ou un stockage d’information trop importants, des algorithmes ne donnant qu’une valeur approchée du résultat doivent être conçus.

Ecrire un petit programme ou a fortiori développer un gros logiciel demande une démarche en plusieurs étapes, appelée processus de développement d’un programme, qui peut être divisé en plusieurs phases (partiellement) successives.

  1. Analyse de ce qui est requis et spécification,
  2. Conception,
  3. Implémentation,
  4. Tests et installation,
  5. Exploitation et maintenance.

Chaque phase produit des résultats écrits soit sous forme de rapport : spécification de ce qui est requis (cahier de charges), manuel utilisateur, description du fonctionnement, description succincte ou détaillée de l’algorithme, programme dûment commenté, historique des modifications, ....

Ce cours n’abordera par tous ces points en détails.