Définition d'algorithme

Le différence entre un algorithme et un programme est souvent une question de niveau de détail. Un algorithme est souvent exprimé avec une notation indépendante de tout langage de programmation alors qu'un programme est écrit dans un langage de programmation particulier.

Une autre différence entre algorithme et programme est que l'exécution d'un algorithme doit toujours se terminer avec un résultat, alors que celle d'un programme peut conduire à une boucle infinie (ne jamais s'arrêter).

Un algorithme est donc une méthode pour résoudre un problème particulier dont on est sûr qu'elle trouve toujours une réponse en un temps d'exécution fini.

Exemple : Pour déterminer si un entier  est premier (à savoir qu'il ne contient pas de facteur autre que  et ), l'algorithme suivant peut être utilisé :

Pour chaque entier , , vérifier si  est un facteur de  (en divisant  par  puis en vérifiant si le résultat est entier). Si c'est le cas, arrêter avec la réponse ``non''. Si aucune valeur  n'est facteur de , alors arrêter avec la réponse ``oui''.

Il y a dans cette définition (informelle) d'algorithme un problème majeur. Prenons l'exemple des nombres premiers. Pourquoi peut-on supposer que l'on sait comment diviser  par  et vérifier que le résultat est un entier ? Ne faudrait-il pas avoir un algorithme pour ça aussi ? Et si jamais on trouve un algorithme pour cette division, ne faudrait-il pas trouver un algorithme pour chaque étape de celle-ci ? Et ainsi de suite. Ou, au contraire, pourquoi ne peut-on pas simplement supposer que ``vérifier si un entier est premier'' est une opération élémentaire ? Pourquoi est-il nécessaire de trouver un algorithme pour cette opération ?

En d'autres termes : comment savoir si une opération est élémentaire (et ne nécessite par conséquent aucun algorithme) ?

La réponse est qu'une opération est élémentaire lorsque un ordinateur peut l'exécuter très rapidement, en réalité en un nombre relativement faible de cycles d'horloge.

Le lecteur de ce livre ne sait pas forcément déterminer si une opération est élémentaire au sens du paragraphe précédent. Heureusement cela ne sera pas nécessaire. La notion de type abstraitexaminée dans la section suivante nous permettra de savoir si une opération est élémentaire dans le sens ci-dessus.

Read more »

Les types structurés et les enregistrements

Les types structurés et les enregistrements

Introduction

Contrairement aux tableaux qui sont des structures de données dont tous les éléments sont de même type, les

enregistrements sont des structures de données dont les éléments peuvent être de type différent et qui se rapportent à

la même entité sémantique (analogie avec Merise).Les éléments qui composent un enregistrement sont appelés

champs.

Avant de déclarer une variable enregistrement, il faut avoir au préalable définit son type, c'est à dire le nom et le type

des champs qui le compose. Le type d'un enregistrement est appelé type structuré. (Les enregistrements sont parfois

appelé structures, en analogie avec le langage C)

Préalable: déclaration d'un type structuré

Jusqu'à présent, nous n'avons utilisé que des types primitifs (caractères, entiers, réels, chaînes) et des tableaux de types

primitifs. Mais il est possible de créer nos propres types puis de déclarer des variables ou des tableaux d'éléments de ce

type.

Pour ce faire, il faut déclarer un nouveau type, fondé sur d'autres types existants. Après l’avoir défini, on peut dès lors

utiliser ce type structuré tout autre type normal en déclarant une ou plusieurs variables de ce type. Les variables de type

structuré sont appelées enregistrements.

La déclaration des types structurés se fait dans une section spéciale des algorithmes appelée Type, qui précède la section

des variables (et succède à la section des constantes). Si l’algorithme comporte des sous-programmes, les types et les

constantes sont déclarées en dehors du programme.

Syntaxes :

Exemple:

I. Déclaration d'un enregistrement à partir d'un type structuré

Une fois qu'on a défini un type structuré, on peut déclarer des variables enregistrements exactement de la

même façon que l'on déclare des variables d'un type primitif.

Type

Structure nom_type

nom_champ1: type_champ1

…

nom_champN: type_champN

FinStruct

Type

Structure tpersonne

nom : chaîne

prénom : chaîne

âge : entier

FinStruct

Read more »