OPTION INFORMATIQUE
Le cours de l'option informatique de première année s'appuie sur les
connaissances en algorithmie acquises lors du premier trimestre. L'objectif
de ce cours est d'approfondir les connaissances en algorithmie. Le cours
est illustré à l'aide du langage de programmation Caml développer à
l'INRIA. Les principaux thèmes abordés sont : les boucles itératives et
conditionnelles, les branchements conditionnels, la complexité des
algorithmes, différents types de structures de données (tableaux, listes,
piles, files) et la récursivité.
Dans ce qui suit vous trouverez les cours et les exercices
d'accompagnement.
- Le
cours(0)
est le cours d'introduction à l'option informatique. Il
présente principalement les rudiments du langage Caml.
- À partir de cours(1),
nous rentrons dans le vif du sujet. Dans ce cours, on présente trois
algorithmes de tri sur des tableaux (tris par insertion, sélection et par
bulles).
- Le cours(2)
présente les
listes de façon formelle et aussi la manipulation des listes en Caml.
- Le
cours(3)
traite des tris sur les listes (tri fusion, par insertion et par bulles)
- Le cours(4) traite de la
logique et des circuits logiques.
- Le cours(5) traite des
piles et de leur représentation à l'aide de tableau ou de liste dans Caml.
- Le cours(6)
traite des files et de leur représentation à l'aide de tableau ou de liste
dans caml,
- Le cours(7) traite des expressions post-fixées et de
leur évaluation à l'aide d'un pile.
- Le cours(8) traite des structures de données récursives.
On y voit comment définir par nous mêmes des listes en Caml et comment
définir un arbre binaire. Ce chapitre est juste une introduction aux
arbres, le sujet étant traité en deuxième année.
- retour au sommaire
Voici maintenant quelques feuilles exercices et leurs corrigés.
Les sujets sont de diverses origines. Ils sont le résultat de mes propres
réflexions ou bien inspirés par des sujets de concours ou bien par
d'autres auteurs comme
J.C. Filliâtre et
Laurent Chéno.
| thèmes abordés
| énoncés
| corrigés
|
| premiers programmes
| TD n°1
| 1
|
| deuxième série de programmes simples
| TD n°2
| 2
|
| Codage de César (utilisation des tableaux en Caml)
| TD n°3
| 3
|
| tableaux et boucles "for"
| TD n°4
| 4
|
| récursivité (premiers pas)
| TD n°5
| 5
|
| listes et récursivité
| TD n°6
| 6
|
| listes et graphisme (intersection de rectangles)
| TD n°7
| 7
|
| entiers longs façon Maple
| TD n°8
| 8
|
| récursivité et graphisme
| TD n°9
| 9
|
| récursivité et graphisme (suite)
| TD n°10
| 10
|
| autour des nombres premiers
| TD n°11
| 11
|
| représentation d'objets en 3D.
| TD n°12
| 12
|
| expressions algébriques postfixées
| TD n°13
| 13
|
| parcours dans un labyrinthe (usage des piles)
| TD n°14
| 14
|
| expressions logiques
| TD n°16
| 16
|
| enveloppe convexe d'une famille finie de points
| TD n°18
| 18
|
| réalisation d'un jeu : le Sokoban
| TD n°19
| 19
|
bonne lecture.