ALGORITHME

10 étudiants

Introduction
Notion d’algorithme 3
• Selon le Petit Robert : “ensemble des règles opératoires propres à
un calcul.”
• Un peu plus précisement : Une séquence de pas de calcul qui
prend un ensemble de valeurs comme entrée (input) et produit un
ensemble de valeurs comme sortie (output).
• Un algorithme résout toujours un problème de calcul. L’énoncé
du problème spécifie la relation input / output souhaitée.
Notion d’algorithme 4
Exemples :
1. Multiplication
Input : deux entiers a et b
Output : leur produit ab
Algorithme : celui de l’école
2. Plus Grand Commun Diviseur (PGCD)
Input : deux entiers a et b
Output : pgcd(a,b)
Algorithme : celui d’Euclide
3. Primalité
Input : un entier a
Question : a est-il un entier premier?
Cas spécial : problème de décision – output = réponse oui/non à une question.
Notion d’algorithme 5
Donner une définition précise de la notion d’algorithme est assez
difficile et complexe.
Il existe plusieurs définitions mathématiques depuis les années 30.
exemples :
• fonctions récursives
• λ-calcul
• machines de Turing
• RAM
(Random Access Machine : machine à accès
aléatoire)
Notion d’algorithme 6
Fait :
Toutes ces définitions sont équivalentes
Thèse de Church :
Tout ce qui est calculable intuitivement est aussi
calculable par les objets formels ci-dessus
Mais :
Il existe des problèmes non calculables (indécidables)
exemple :
Problème de l’arrêt
Input : Un algorithme (programme) A et un input I
Output : A termine-t-il pour I?

  • Types fondamentaux

    Structure de l’algorithme La structure d’un programme C est proche de celle d’un algorithme. Le fichier, qui doit avoir l’extension .c, commence par un cartouche faisant apparaître le nom des auteurs du programme, la version ou la date de réalisation et l’objectif du programme. Ces éléments sont mis dans des commentaires et sont donc ignorés par le compilateur. Les #include correspondent à des directives qui indiquent au compilateur (en fait au préprocesseur) d’inclure les fichiers nommés stdio.h et stdlib.h. Ces fichiers font parties de Cours C, Semaine 1 c INPT–PAD 3/26 ALGORITHMIQUE ET PROGRAMMATION 1 Algorithmique et programmation : les bases (C) la bibliothèque standard du C et donne accès à des fonctions déjà définies. Par exemple les fonctions d’affichage (printf) et de lecture (scanf) sont définies dans stdio.h. La constante EXIT_SUCCESS est définie dans stdlib.h. Si on ne met pas ces #include, on ne peut pas utiliser ces fonctions ou constantes. Le #define suivant permet de définir la constante PI. Il correspond donc à une définition. Finalement, les déclarations et instructions sont regroupées entre les accolades qui suivent int main(), d’abord les déclarations, puis les instructions. main est la fonction principale, c’està-dire que c’est elle qui est exécutée quand le programme sera lancé. Les instructions sont les mêmes que cette présentées dans l’algorithme même si elles ont une forme un peu différente. 2.3 Identificateurs Un identificateur est un mot de la forme : une lettre (y compris le souligné) suivie d’un nombre quelconque de lettres et de chiffres. Attention, il n’est pas possible d’utiliser les lettres accentuées en C. 2.4 Commentaires Les commentaires commencent par /* et se terminent par */. Attention, les commentaires ne peuvent pas être imbriqués. Pour représenter une propriété du programme, nous utiliserons /*{ ... }*/. Le langage C++ ajoute les commentaires qui commencent par // et se termine avec la fin de la ligne (comme --). Ils peuvent être utilisés la où on met -- en algorithmique.

Formateur

€200.00 €150.00

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *