Loading...
Reload document 
Open in new tab COURS ALGORITHMIQUE
ET PROGRAMMATION
INFORMATIQUE
DUT INFORMATIQUE
S1
Marie-Agnès peraldi-frati
Mâitre de conférences en informatique
UNS/IUT de Nice côte d’azur
1
M A P @ U N I C E . F R
MAP – UNS
RÉFÉRENCES
• Algorithmes D.E Knuth CSLI Publications 2011
• Introductipon a la science informatique G. Dowek Ed RPA 2010
• Eléments pour une histoire de l’informatique, D.E Knuth CSLI
Publications 2011
• Cours et exercices corrigés d’algorithmique- J. Julliand Ed Vuibert
• Algorthmique méthodes et modèles , P Lignelet Ed Masson 1988
• Cours algorithme Cécile Balkanski, Nelly Bensimon, Gérard Ligozat
Fev 2010
IUT Orsay
MAP – UNS
2
12/03/2013
1
OBJECTIF DU COURS API
• Notions de base en algorithmique
• Types de données et lien avec la machine
• Notion de sous-programmes et lien avec la compilation
• Qualité
• nommage des variables, assertions, documentation …,
• pré et post conditions
• Structures algorithmiques fondamentales: .
• Implantation des algorithmes dans un langage de
programmation.
• Introduction au test unitaire, boîte noire,
• Algorithmes fondamentaux de recherche recherche d’un
élément, parcours, tri, …
• Avoir une première notion des performances des algorithmes
utilisés
MAP – UNS
3
NOTION DE BASE EN
ALGORITHMIQUE
4
MAP – UNS
12/03/2013
2
CONCEPTS IMPORTANTS EN
INFORMATIQUE
• Algorithme : mot dérivé du nom du mathématicien
al_Khwarizmi qui a vécu au 9ème siécle, était
membre d’un académie des sciences à Bagdad .
• Un algorithme prend des données en entrée,
exprime un traitement particulier et fournit des
données en sortie.
• Programme : série d’instructions pouvant s’exécuter
en séquence, ou en parallèle (parallélisme
matériel) qui réalise (implémente) un algorithme
MAP – UNS
5
POURQUOI UN COURS D’ “ALGO” ?
•Pour obtenir de la «machine» qu’elle effectue
un travail à notre place
•Problème: expliquer à la «machine» comment
elle doit s’y prendre
• Besoins :
• savoir expliciter son raisonnement
• savoir formaliser son raisonnement
• concevoir (et écrire) des algorithmes:
• séquence d’instructions qui décrit comment résoudre un
problème particulier
MAP – UNS
6
12/03/2013
3
ALGORITHME
• Savoir expliquer comment faire un travail sans la
moindre ambiguïté
• langage simple : des instructions (pas élémentaires)
• suite finie d’actions à entreprendre en respectant une
chronologie imposée
•L’écriture algorithmique : un travail de programmation
à visée universelle
• un algorithme ne dépend pas du langage dans lequel il est
implanté,
• ni de la machine qui exécutera le programme correspondant.
MAP – UNS
7
EXEMPLE D’ALGORITHMES
• Recette de cuisine
• Notice de montage de meuble
en kit
• Mathématiques : problème 3n+1: élémentaire mais
redoutable
• si n est pair, on le divise par 2 ;
• si n est impair, on le multiplie par 3 et on ajoute 1.
• Est-il vrai que l’on finira tôt ou tard par tomber sur 1 ?
MAP – UNS
8
12/03/2013
4
12/03/2013
LES PROBLÈMES FONDAMENTAUX
EN ALGORITHMIQUE
• Complexité
• En combien de temps un algorithme va -t-il atteindre le
résultat escompté?
• De quel espace a-t-il besoin?
• Calculabilité:
algorithme ?
• Correction
• Existe-t-il des tâches pour lesquelles il n’existe aucun
• Etant donnée une tâche, peut-on dire s’il existe un
algorithme qui la résolve ?
• Peut-on être sûr qu’un algorithme réponde au problème
pour lequel il a été conçu ?
MAP – UNS
9
EXEMPLE DE LANGAGE ALGORITHMIQUE
MAP – UNS
10
5