I11 : Informatique L11ersemestreCours d"Informatiqueannée 2006-2007Gilles BernotNotes de coursUniversité d"ÉvryAvertissement au lecteur :Ce polycopié n"est pas un document scolaire de référence surle cours d"informatique, c"est seulement l"ensemblede mes propres notes de cours mises en forme.
Il ne contient donc pas les explications détaillées qui ont été donnéesen cours.
En particulier tous les développements systématiques des exemples, expliquant comment le langage MLeffectuerait les traitements, sont absents de ces notes.
On trouvera également parfois quelques simples allusions à desconcepts élémentaires, largement développés en cours maisqui sont routiniers pour tout informaticien.G.
BernotCOURS 11. Informatique, Gigantisme, Méthodes2. Buts du cours3. Les langages de programmation4. Classement des langages5. Bibliographie6. Structures de données, types de données, types, fonctions7. Type de données des booléens8. Type de données des entiers relatifs9. Type de données des nombres " à virgule flottante »10. Type de données des caractères11. Type de données des chaînes de caractères12. Les expressions bien ou mal typéesCOURS 21. Enrichir le pouvoir d"expression : les déclarations2. La portée d"une déclaration globale3. Déclarations de fonctions4. Les types produits cartésiens5. Un argument produit cartésien v.s. plusieurs arguments6. Expressions conditionnelles7. Déclarations locales8. Déclarations multiplesCOURS 31. Typage des fonctions2. Typage des fonctions avec déclarations locales3. Fonctions partielles, traitement d"exceptions4. Les types " enregistrement »5. Champs explicites pour les enregistrementsCOURS 41. Résolution de problèmes par découpages2. Programmation structurée3. Un exemple : la date du lendemain14. Graphe d"appels des fonctions5. Graphes d"appels avec récursivité mutuelle6. La différence entreletetlet rec7. Cas des cycles minimauxCOURS 51. Exemples de fonctions récursives2. Les types " liste »3. Premières fonctions sur les listes4. Premières fonctions récursives sur les listesCOURS 61. L"usage dematchsur les listes2. Seuls[]et_ : :_sont indispensables3. Exemples de fonctions simples sur les listesCOURS 71. Sous-ensembles finis d"un type quelconqueCOURS 81. Sous-ensembles finis d"un type ordonnéCOURS 91. Preuves de terminaison de fonctions récursives2I11 : Informatique L11ersemestreCours No.
1) Gilles Bernotcours d"informatique1 Informatique, Gigantisme, MéthodeLes cours d"informatique porteront sur l"apprentissage des bonnes méthodes de programmation, au moyen d"unlangage de programmation spécialement conçu pour la pédagogie : ML.
L"objectif est d"acquérir les " bonnes habi-tudes »qui permettront ultérieurement d"écrire des logiciels de grande taille et facilement modifiables.Ceux qui n"ont jamais programmé ont presque une meilleure idée de l"informatique grandeur nature que ceux quiont déjà écrit des programmes chez eux (impression fausse demise au point petit à petit toujours possible, etc.).
Doncceux qui partent avec un handicap pour ce cours ne sont pas ceux qu"on croit.L"informatique individuelle donne souvent de mauvaises habitudes, dues à la faible taille des programmes écrits(souvent 1 seul programmeur, donc organisation facile), aux faibles conséquences des erreurs (vies humaines, investis-sements perdus, expérience scientifique unique manquée ), et au peu d"exigence des utilisateurs.Points clefs du génie logiciel : plusieurs développeurs, utilisateurs?=développeurs, gravité des erreurs.La programmation " ludique » est dangereuse pour des projetsen grandeur nature.
Conséquences terribles surcentrales nucléaires, débit des vannes d"un barrage, gestion des ambulances, etc.
Un oubli ou une erreurn"estpasréparable comme dans un " petit » programme (petit≈écrit par un seul homme en moins de quelques mois/années).Gigantisme de l"informatique=?méthodes, découpage des systèmes à réaliser, approche systématique, rigueurformelle (supérieure à une démonstration mathématique cartous les détails doivent être explicités dans un langagestrictement symbolique, qui n"autorise que certaines formes bien délimitées au point d"être analysable automatiquementpar ordinateur).
2) Buts du coursAcquérir les premiers éléments de cette rigueur sur des problèmes de petite taille.
Appréhender les premières notionsde " programmation dans les règles de l"art ».
Comprendre lesméthodes de découpage de problèmes en sous-problèmeset comment combiner les solutions intermédiaires.
Ne plus avoir ni une idée mythique de l"informatique, ni réductrice,en sachant quelles sont les techniques mises en jeu, leur rôle, leurs interactions.Comprendre ce qu"est un langage de programmation, l"évolution des langages de programmation.
Savoir utiliserles structures classiques de la programmation pour concevoir des programmes justes par construction.Vecteur d"apprentissage = un langage de programmation spécialisé dans la mise en oeuvre rigoureuse des méthodesde programmation : ML.
Signifie Méta Langage [Historique du nom : premier langage pour programmer des stratégiesautomatiques de preuves de théorèmes].
Il généralise et impose par construction une approche que l"on doit suivredanstousleslangagesde programmation pour réaliser un logiciel proprement.
3) Les langages de programmationUn langage de programmation est un " vocabulaire » restreintet des règles de formation de " phrases » très strictespour donner des instructions à un ordinateur.
Lemoinspar rapport au français ou aux mathématiques est donc sapauvreté.
Leplusest qu"aucune " phrase »(=expression) n"est ambigüe : il n"existe pas 2 interprétations possibles.
Deplus, chaque phrase(=expression) estexécutable.
Exécutable signifie qu"un programme part d"informations entréessous forme de caractères/symboles et/ou de nombres, qu"il décrit des séquences de transformations de symboles et/oude calculs sur ces entrées, pour aboutir à un résultat également symbolique.
Exemple :# let distance (x,y) = if x < ythen y-xelse x-y ;;# distance (48,31) ;;-: int = 17#letveut direSoitcomme en maths.
Calculs sur 48 et 31, transformation des symbolesxetyen des nombres,transformation des caractères "distance» en une expression qui est ensuite exécutée. [+ suivre les étapes de réductionde l"expressionif then else ]3Il faut aussi disposer d"actions plus complexes que de simples opérations de calculette (accélérer, monter, descendre,faire un tour de piste en attente, etc.).
On doit donc pouvoir:- regrouper puis abstraire un grand nombre de données élémentaires (nombres, caractères ) pour caractériser unestructure de donnéesabstraite (avion= latitude, longitude, altitude, vitesse, compagnie, origine, destination,etc.)- regrouper des suites de commandes élémentaires (additions, multiplications, statistiques, classifications, déci-sions ) pour organiser lecontrôle du programmeet le rendre plus lisible et logique (attribuer une piste à unavion = des inventaires pour vérifier qu"il reste de la place,déplacer dans la mémoire les avions sortis de piste,communiquer avec l"ordinateur de bord, etc.)Donc : ce qui définit les langages de programmation, c"est- la façon de représenter symboliquement lesstructures de données- et la façon de gérer lecontrôledes programmes.
4) Classement des
