DEA de Chimie Informatique et Théorique C, Algorithmique et Programmation
1 Le langage C
1.1 Un premier programme
1.2 Les variables en C
1.2.1 Denition
1.2.2 Declaration
1.2.3 Utilisation d’une variable
1.2.4 Achage de la valeur d’une variable
1.3 Achage des expressions : introduction
1.4 Instructions de base
1.4.1 Expressions
1.4.2 La boucle for
1.4.3 La boucle while
1.4.4 La boucle do-while
1.4.5 L’instruction if
1.4.6 Le choix switch
1.5 Les tableaux
1.5.1 Les tableaux simples
1.5.2 Les tableaux a plusieurs dimensions
1.6 Les structures
1.7 Les unions
1.8 Les types enumeres
1.9 Les pointeurs
1.9.1 Introduction : les cha^nes de caracteres
1.9.2 Generalisation de la notion de pointeur
1.9.3 Arithmetique des pointeurs
1.9.4 Application : tableaux avant-apres
1.9.5 Pointeurs sur structure
1.10 L’instruction printf en detail
1.10.1 forme generale
1.10.2 ecrire des cha^nes de caracteres
1.11 Demander des informations a l’utilisateur
1.11.1 L’instruction scanf
1.11.2 La fonction getchar
1.12 Les fonctions
1.12.1 Notion de fonction
1.12.2 Declaration et utilisation d’une fonction
1.12.3 passage par valeur, passage par adresse
1.12.4 Consequences du passage par adresse
1.12.5 Portee des identicateurs
1.13 Recursivite?
1.13.1 Programmer une suite recurrente
1.13.2 fonction recursive
1.13.3 type recursif
1.14 Gestion dynamique de la memoire
1.14.1 Introduction
1.14.2 Bien gerer l’allocation dynamique
1.14.3 Allocation dynamique et types recursifs
1.15 Lire et ecrire dans des chiers
1.16 Fonctions en parametre
1.16.1 Pourquoi des fonctions en parametre
1.16.2 Application
1.17 Les denitions : #dene
1.18 La programmation modulaire en C
1.18.1 Pourquoi la programmation modulaire
1.18.2 R^ole des chiers d’en-t^ete
1.18.3 Variables globales
1.19 Fonctions liees aux cha^nes de caracteres
1.19.1 Introduction
1.19.2 Quelques fonctions
1.20 Les arguments de la ligne de commande
1.20.1 Introduction
1.20.2 Les parametres argc et argv
1.21 Gestion des processus
1.21.1 Introduction
1.21.2 Creation d’un processus
1.21.3 Communication entre processus
2 Un peu de théorie
2.1 Preuve de programme
2.1.1 Introduction
2.1.2 Methode de Floyd
2.1.3 Preuve de terminaison
2.2 Notion de complexite des algorithmes
2.2.1 Introduction
2.2.2 Petit rappel : Ordre d’une fonction
2.2.3 Dierentes mesures de complexite
2.2.4 Que mesurer
2.2.5 Exemple : Le tri a bulle
2.3 Langage regulier
2.3.1 Denitions
2.3.2 Automates nis
2.3.3 Notation
2.3.4 Determinisation d’un automate
2.4 Langages algebriques
2.4.1 introduction
3 Structures de données
3.1 Listes cha^nees
3.1.1 Introduction
3.1.2 Les listes lineaires
3.1.3 Implantation en C
3.1.4 Denition des constructeurs
3.1.5 Variation sur les listes
3.2 Les arbres
3.2.1 Introduction
3.2.2 Type abstrait : exemple des arbres binaires étiquetés
3.2.3 Implantation en C des arbres unaires-binaires
3.2.4 Les arbres n-aires
3.2.5 arbres equilibres
3.3 Les graphes
3.3.1 Introduction
3.3.2 Representation des graphes
3.3.3 Implantation en C
3.3.4 Recherche des composantes connexes
3.3.5 Recherche de chemin dans un graphe decore
3.3.6 graphe pondere
3.4 Les les
3.4.1 Introduction
3.4.2 Implantation en C
3.5 Les piles
3.5.1 Introduction
3.5.2 Implantation en C
4 Algorithmes fondamentaux
4.1 Recherche dans un ensemble de données trié
4.1.1 Introduction
4.1.2 Liste cha^née : recherche séquentielle
4.1.3 Recherche dans un tableau trié
4.1.4 Table de hachage
4.2 Les tris
4.2.1 Tri par insertion
4.2.2 Tri par sélection
4.2.3 Le tri à bulle
4.2.4 Le tri shell
4.2.5 Tri rapide : le quick sort
4.2.6 Réutilisabilité.
4.3 Les jeux
4.3.1 Introduction
4.3.2 Algorithme du Min-Max
4.4 Quelques algorithmes sur les matrices
4.4.1 somme et produit de deux matrices
4.4.2 Méthode du pivot de Gauss
4.5 Algorithme du simplexe
4.5.1 Introduction
4.5.2 Principe de l’algorithme
4.6 Les algorithmes génétiques
4.6.1 Introduction
4.6.2 Représentation des données
4.6.3 L’algorithme proprement dit
4.6.4 Quelques remarques
4.7 Procédures par séparation et evaluation
4.7.1 Introduction
4.7.2 Exemple : le probléme du sac-à-dos
4.7.3 S’aider d’heuristiques
4.7.4 Exercice
4.8 Programmation dynamique
4.8.1 Application aux problémes de programmation lineaire en nombres entiers
4.8.2 Application au probléme du voyageur de commerce
4.9 Calcul scientique
4.9.1 Approximation au sens des moindres carrés
4.9.2 Résolution de systémes linéaires par itération
4.9.3 Résolution d’une équation non linéaire
4.9.4 Résolution d’un systéme d’équations non-linéaires f(x)=0 136
