Premier semestre (S5)

Cours : 20h, TD : 20h

Crédits ECTS : 4

responsable : Rumen Andonov - andonov@irisa.fr

 

Objectifs :

L'objectif de ce cours, dans le cadre de la licence informatique, est double. Il permet, d'une part, l'apprentissage de la modélisation de nombreux problèmes (graphes d'états, modèles en intelligence artificielle, réseaux, etc.). Il contribue, d'autre part, à enrichir le corpus algorithmique : en effet, les graphes sont des objets complexes permettant d'aborder d'intéressantes notions algorithmiques à travers la résolution de problèmes classiques (techniques d'exploration, parcours dans les graphes, complexité, types abstraits…).

 

Contenu des enseignements :

1. Le type abstrait graphe et ses représentations.
2. Exploration de la descendance d'un sommet. Parcours en largeur et en profondeur.
3. Circuits et composantes fortement connexes. Tri topologique.
4. Chemins de valeur optimale.
5. Arbres couvrants minimaux.
8. Flots sur les réseaux de transport.
9. Notions de programmation linéaire.

 

Cours : 16h, TD : 18h, TP : 16h

Crédits ECTS : 6

responsable : Lucien Ungaro - ungaro@univ-rennes1.fr

 

Cette première partie d’architecture des ordinateurs est consacrée à la conception des circuits digitaux.

 

Contenu des enseignements :

1. Algèbre de Boole et représentation des informations.
2. Conception de circuits combinatoires et  séquentiels.
3. Décomposition d’une machine en unités de traitement et de contrôle.
4. Fonctionnalités et technologies des mémoires.

Bibliographie :

Computer Architecture: A Quantitative Approach - John L. Hennessy , David A. Patterson

Cours : 8h, TD : 32h, TP : 20h
Crédits ECTS : 6

responsable : Laurent Perraudeau - perraudeau@irisa.fr

Objectifs :

• Permettre à l’étudiant de se construire une « boîte à outils » d’utilisation et de programmation de systèmes (shell Unix, Makefile, langage C).
• Offrir à l’étudiant une connaissance de base des principes de mise en œuvre des systèmes de gestion de fichiers et d’introduire les problèmes de gestion des objets en mémoire par un calculateur.
• Comprendre les architectures de réseaux, et protocoles associés, connaître et savoir utiliser les services de l’Internet, et programmer des applications utilisant ces services.

Contenu :

Partie système d'exploitation : TD : 28h, TP : 12h

• Unix/Linux et langages de commandes
    - Désignation des fichiers (protection, hiérarchie)
    - Commande Unix classiques (grep, find, ps, etc.), programmation en Bourne shell
• Introduction au langage C
    - Introduction au langage C
    - Chaîne de compilation : compilation, édition de lien
    - Outils annexe : Makefile, débogueur
• Systèmes de gestion de fichiers
    - Organisation des fichiers (descripteurs de fichiers, hiérarchie, etc.)
    - Accès aux fichiers (Tampons d’E/S, cache système, etc.)
• Introduction à la gestion des objets en mémoire
    - Présentation de la machine MIPS
    - Introduction au langage d’assemblage MIPS
    - Mode d’adressages et accès aux objets simples

Partie réseaux : Cours : 8h, TD : 4h, TP : 8h

• Introduction aux applications et protocoles réseaux
    - Architecture des réseaux informatiques et protocoles Internet
    - Service de l’Internet : Web et http, transfert et gestion de fichiers (FTP/nfs), courrier électronique et SMTP, service d’annuaires et serveurs DNS
    - Programmation et mise en œuvre d’applications sur Internet

 

Cours : 20h, TD : 20h

Crédits ECTS : 5

responsable : Anne Grazon - anne.grazon@univ-rennes1.fr

 

Dans ce cours sont définis les mots, les langages et les opérations sur ces objets. Les langages étudiés sont essentiellement les langages algébriques et rationnels. Différentes approches coexistent pour décrire un langage : il peut être reconnu par un automate, engendré par une grammaire, dénoté par une expression rationnelle, solution d'un système d'équations ; on s'attache à montrer l'équivalence de ces modes de description, par des manipulations sur ces outils eux-mêmes.

Plan

  1. Introduction : la théorie des langages et ses applications en informatique
  2. Le monoïde libre
  3. Engendrer des mots, des langages : les grammaires algébriques
  4. Reconnaître des mots, des langages : les automates finis
  5. Langages reconnaissables, opérations sur ces langages
  6. Langages rationnels et théorème de Kleene
  7. Automate minimal
  8. Formes de grammaires algébriques
  9. Automates à pile et modes de reconnaissance associés
  10. Lemme d'itération pour les langages algébriques
  11. La hiérarchie de Chomsky
  12. Décidabilité : problèmes décidables et indécidables en théorie des langages

Bibliographie

  1. Introductory Logic and Sets for Computer Scientists, N. Nissanke, Addisson Wesley 1999
  2. Mathématiques pour l'informatique, A. Arnold et I. Guessarian, Masson (3ème édition) ou Dunod 2005
  3. Concepts fondamentaux de l'informatique, A. Aho, J. D. Ullman, Dunod 1996
  4. Introduction to Automata, Theory, Languages and Computation, J.E. Hopcroft , J. D. Ullman, R. Motwani, Addisson Westey 2007
  5. Thérorie des langages et des automates, J.M. Autebert, Masson 1994
  6. Langages algébriques, J.M. Autebert, Masson 1987
  7. Le Théorème de Gödel de Ernest Nagel, Seuil 1997
  8. La machine de Turing, A. Turing, J-Y. Girard, Seuil 1999
  9. Godel, Escher, Bach. Les Brins d'une Guirlande Eternelle, Douglas Hofstadter, InterEdition 1985 ou Dunod 2000

Cours : 8h, TD : 12h, TP : 4h
Crédits ECTS : 3

responsable : Jean-Marc Jézéquel - jezequel@irisa.fr

 

Objectif :

L'objectif de ce module est de proposer une introduction à la modélisation par objets avec UML (en anglais Unified Modeling Language, « langage de modélisation unifié ») qui est un langage graphique de modélisation des données et des traitements largement utilisé en ingénierie du logiciel.
A l'issue de ce cours, un étudiant doit être capable de lire et de comprendre les diagrammes UML les plus communément utilisés (diagramme de classes, diagrammes de package, cas d'utilisation, diagrammes de séquences), ainsi que de modéliser avec UML des applications logicielles simples.

Prérequis : Connaissances de base en informatique, notions de programmation orientée objet (classe, interface, opérations, méthodes, héritage).

Contenu :

- Introduction à la modélisation par objets
- Notions d'objet, de classe vue comme un module, d'interface, de contrat
- Eléments d'OCL
- Relations entre classes, généricité, héritage, classification
- Paquetages
- Cas d'utilisation
- Diagrammes de séquences
La partie pratique met l'accent sur la prise en main des principaux diagrammes UML : diagramme de classes, diagrammes de package, cas d'utilisation, diagrammes de séquences, et introduit brièvement la pratique d'un AGL (atélier de génie logiciel) dans l'environnement Eclipse.

Bibliographie

Modélisation objet avec UML par Pierre-Alain Muller ISBN 2-212-08966-X Editions Eyrolles

TD : 34h, TP : 22h

Crédits ECTS : 6

responsable : Mickaël Foursov - foursov@irisa.fr

Cet enseignement porte sur les structures de données classiques (listes, arbres, ensembles, tables) par une approche type abstrait / programmation objet : on définit d'abord la structure du type étudié ainsi que les primitives de manipulation (méthodes) puis, dans un second temps, on examine les représentations possibles en mémoire (mises en œuvre).

Contenu des enseignements:

1. Eléments de programmation objet : classe, objet, héritage, généricité, polymorphisme
2. Listes
3. Récursivité
4. Arbres binaires
5. Ensembles / Tables
6. Partage de tables

Deuxième semestre (S6)

Cours : 26h, TD : 22h

Crédits ECTS : 5

responsable : Sophie Pinchinat - pinchinat@irisa.fr

 

Objectif :

Le but de ce module est d'introduire  les méthodes algorithmiques classiques de résolution de problèmes, et de donner un aperçu tant sur la complexité (coût en temps  et en mémoire)  des algorithmes que sur la difficulté intrinsèque des problèmes. Au terme du cours l'étudiant aura appris et assimilé les notions fondamentales de l'algorithmique séquentielle (notions de base qui sont présentes dans toute application informatique).

Contenu :

1- Introduction à l'algorithmique et à la complexité.
2- La méthode diviser pour résoudre (et la récursivité).
3- La méthode tabulaire (programmation dynamique)
4- Les essais successifs : puissance, limitations et heuristiques.
5- Méthodes approchées et algorithmes gloutons.
5- Les classes de problèmes P et NP.
6- Les limites de l'algorithmique.
7- Les algorithmes probabilistes.

Cours : 16h, TD : 16h, TP : 18h
Crédits ECTS : 4

responsable : Steven Derrien : steven.derrien@univ-rennes1.fr

 

Cette partie concernant l’architecture matérielle des ordinateurs vise à favoriser une bonne compréhension des couches basses de système : processeurs, mémoires centrales, bus, entrées-sorties, interruptions, hiérarchies de mémoire.

Contenu des enseignements :

1. Structure interne des processeurs : architectures CISC et RISC – notion de pipe-line.
1. Structure d'un ordinateur : technologie et utilisation des mémoires ; signaux de bus.
2. Entrées/Sorties : synchronisation par attente active ; synchronisation par interruptions ; transmissions séries.
3. Hiérarchies de mémoire : principes généraux ; caches ; mémoires virtuelles.

Bibliographie :

Organisation et conception des ordinateurs, l’interface matériel/logiciel – David Patterson et John Hennessy, Dunod

CM : 16h, TP : 10h, Projet : 24h
Crédits ECTS : 5

responsable : Guillaume Pierre - guillaume.pierre@univ-rennes1.fr

 

Objectifs :

Approfondir les connaissances acquises au premier semestre en s’intéressant aux «couches basses » d’un système. On s’intéressera en particulier à la gestion des objets statiques/dynamiques par un calculateur, à la mise en œuvre des entrées/sorties physiques, et au fonctionnement des outils de traduction de programmes (assembleur, éditeur de lien, chargeur).

Contenu :

• Gestion de la mémoire et accès aux objets
 - Sous-programmes et appels système
 - Gestion statique et accès aux objets
 - Gestion dynamique (pile, tas) et accès aux objets
• Logiciels de traduction des programmes
 - Logiciel d’assemblage
 - Editeur de lien et chargeur
• Entrées-sorties physiques
 - Support matériel pour système d’exploitation (mode superviseur, exceptions)
 - Gestion des périphériques sous Unix (pseudo-fichiers)
 - Périphérique en mode caractère (attente active + IT)
 - Périphérique en mode bloc (attente active + IT)

Cours : 20h, TD : 20h, TP : 12h
Crédits ECTS : 5

responsable : Sandrine Blazy - sandrine.blazy@irisa.fr

 

Ce cours se concentre sur les concepts fondamentaux de la programmation raisonnée, qui sont appliqués sur des exemples pratiques de programmes.

Objectifs

-      Comprendre les concepts fondamentaux de la programmation (ex. types, récursion).
-       Savoir exploiter au mieux les atouts de la programmation fonctionnelle.
-       Savoir faire des calculs et raisonner sur des programmes.
-       Initier au développement de logiciels fiables (vérification déductive)

Contenu théorique

-       Initiation à la sémantique des langages de programmation.
-       Induction de listes.
-       Terminaison de programmes récursifs.
-       Spécifications, invariants de boucle

Contenu pratique

-       Langage de programmation OCaml (noyau fonctionnel).
-       Réalisation d’un prototype de vérification déductive.

TD : 24h, TP : 24h

Crédits ECTS : 5

responsable : Véronique Masson - masson@irisa.fr

 

Ce cours introduit les deux niveaux d'analyse présents dans un compilateur : l'analyse lexicale (automate d'états fini) et l'analyse syntaxique (automate à pile). On étudie ensuite comment sont compilées les constructions de base d'un langage impératif (déclarations, expressions, instructions, procédures). Enfin, on présente les notions nécessaires à la compilation d'unités écrites séparément et à la constitution d'un programme exécutable par un éditeur de liens.

Prérequis :

Programmation 1 et Langages formels

Contenu des enseignements:

1. Programmation par automate d'états fini
2. Analyse syntaxique descendante gauche droite
3. Éléments de compilation : table des identificateurs ; calcul de type et compilation des expressions ; compilation des instructions et des procédures ; compilation séparée et édition de liens.
4. Automates à pile, grammaires LL(1)
Un projet consiste à écrire un compilateur et un éditeur de liens pour un petit langage impératif. Ce projet présente l'avantage de faire travailler les étudiants par groupes.

Bibliographie :

Compilateurs : Principes, Techniques et Outils ( traduction française), AHO A.,SETHI R.,ULLMAN J., INTEREDITIONS 1989

Cours : 10h, TD : 16h

Crédits ECTS : 3

responsable : Sophie Pinchinat - sophie.pinchinat@irisa.fr

 

Ce cours vise deux buts : d'une part, donner une base solide en raisonnement logique, ceci est l'aspect  “ calcul ” ; d'autre part, introduire la notion de système formel, essentielle en informatique. Enfin, ce cours donne l'occasion de présenter, de façon informelle, différentes notions approfondies plus tard comme les langages, la sémantique, la calculabilité, la décidabilité.

Contenu des enseignements :

1. Introduction
2. Calcul des propositions : langage et sémantique du calcul des propositions ; systèmes formels.
3. Calcul des prédicats : langage et sémantique du calcul des prédicats ; systèmes formels.