Traitement de l'Information
Algorithmes, logique combinatoire et sequentielle, automates
Objectifs pedagogiques
- Concevoir des algorithmes structures pour resoudre des problemes
- Maitriser les operateurs logiques et les tables de verite
- Differencier logique combinatoire et logique sequentielle
- Modeliser un systeme avec une machine a etats finis (FSM)
Introduction : De la donnee a la decision
Exemple concret : Systeme d'alarme
Un systeme d'alarme doit analyser les signaux de capteurs (mouvement, ouverture porte, bris de vitre) et decider s'il declenche la sirene. C'est un traitement de l'information qui combine logique combinatoire (conditions) et logique sequentielle (etats arme/desarme).
Le traitement de l'information est le coeur de tout systeme numerique. Il transforme des donnees brutes en decisions et actions. Cette transformation repose sur des algorithmes et des structures logiques.
Les deux types de logique
Combinatoire
Sortie = f(entrees actuelles)
Sans memoire
Sequentielle
Sortie = f(entrees + etat)
Avec memoire
1Algorithmique : Structurer la Logique
Definition
Un algorithme est une suite finie d'instructions permettant de resoudre un probleme. Il doit etre deterministe et terminer en un temps fini.
Structures de controle
Sequence
instruction2;
instruction3;
Selection (if)
action1;
} else {
action2;
}
Iteration (boucle)
action;
}
2Logique Combinatoire : Les Fondamentaux
Operateurs logiques de base
La logique combinatoire utilise des variables booleennes (0 ou 1) et des operateurs logiques pour produire une sortie qui depend uniquement des entrees actuelles.
Les 3 operateurs fondamentaux
ET (AND)
S = A . B
| A | B | S |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OU (OR)
S = A + B
| A | B | S |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
NON (NOT)
S = /A
| A | S |
|---|---|
| 0 | 1 |
| 1 | 0 |
Theoremes de De Morgan
/(A.B) = /A + /B
/(A+B) = /A . /B
3Logique Sequentielle : Memoire et Etats
Difference fondamentale
Contrairement a la logique combinatoire, la logique sequentielle possede une memoire. La sortie depend non seulement des entrees actuelles mais aussi de l'etat precedent du systeme.
La bascule RS : element de memoire
Table de verite
| R | S | Q+ | Etat |
|---|---|---|---|
| 0 | 0 | Q | Memoire |
| 0 | 1 | 1 | Set |
| 1 | 0 | 0 | Reset |
| 1 | 1 | ? | Interdit |
Application
- Anti-rebond pour bouton poussoir
- Memorisation d'un evenement
- Registres de stockage
4Machines a Etats Finis (FSM)
Principe de la FSM
Une Machine a Etats Finis modelise un systeme avec un nombre fini d'etats. Les transitions entre etats sont declenchees par des evenements ou conditions.
Exemple : Feu de circulation
VERT
30s
ORANGE
5s
ROUGE
30s
Implementation : En C/Arduino, on utilise une variable d'etat et un switch/case pour gerer les transitions entre etats.
Resume en 5 points cles
- 1Un algorithme est une suite d'instructions utilisant sequence, selection et iteration.
- 2La logique combinatoire (ET, OU, NON) produit une sortie qui depend uniquement des entrees actuelles.
- 3La logique sequentielle possede une memoire (bascules) et des etats internes.
- 4Les theoremes de De Morgan permettent de simplifier les expressions logiques.
- 5Une FSM modelise un systeme avec des etats et des transitions declenchees par des evenements.
Mini-Quiz
Question 1 : Quel est le resultat de l'operation 1 AND 0 ?
a) 1
b) 0
c) Indetermine
Reponse : b) AND necessite que les DEUX entrees soient a 1
Question 2 : Quelle structure logique possede une memoire ?
a) Logique combinatoire
b) Logique sequentielle
c) Les deux
Reponse : b) La logique sequentielle utilise des bascules pour memoriser l'etat
Question 3 : Dans une FSM, qu'est-ce qui declenche une transition ?
a) Un changement d'etat
b) Un evenement ou une condition
c) Le temps uniquement
Reponse : b) Les transitions sont declenchees par des evenements (entrees, timeout, etc.)
