Savoir écrire un programme simple dans un langage de programmation de haut niveau.

Premiers éléments de programmation et d’algorithmique. Notion d’algorithme. Langages de programmation, variables, structures de contrôle, fonctions et passage de paramètres.

Connaissance des fonctions d’un système d’exploitation. Savoir utiliser efficacement un système Unix.

Étude des différentes fonctions d’un système d’exploitation et familiarisation avec l’environnement et l’utilisation des systèmes de la famille Unix  : système de gestion de fichiers, processus, liens entre processus et fichiers, les commandes de base (locales et réseau), le concept de filtre, notion de script.

Comprendre un certain nombre des principes généraux du traitement de données par des machines binaires.

Principes de base du fonctionnement des ordinateurs  ; Organisation générale d’un ordinateur, représentation binaire, mode d’adressage, principe d’exécution d’un programme, langage machines, circuits logiques.

• Calculus  : manipulation d'expressions algébriques (fractions, polynôme du second degré, puissances, factorisation ; équations, inéquations, valeur absolue, systèmes linéaires à deux inconnues ; trigonométrie ; sommes discrètes, raisonnement par récurrence, formule de binôme, suites géométriques et suites arithmétiques, manipulation du signe Σ, sommes doubles)
• Fonctions (fonctions usuelles  : fonctions trigonométriques, fonctions puissance, exponentielles, logarithmes ; composées, dérivation, limites, asymptotes, convexité)
• Géométrie affine (points et vecteurs, équations paramétriques de droites, de plan, repères ; résolution de systèmes, pivot de Gauss)
• Suites (suites récurrentes, suites bornées, suites convergentes)

Apprendre à concevoir et à manipuler des structures de données. Introduction à la récursivité sur les données, et sur le contrôle. Etude approfondie des listes chaînées.

La première partie du cours concerne la modélisation avec une introduction aux objets  : encapsulation des données, liaisons un peu plus complexes (lorsque les objets ont des références croisées), notion d'interface.

Nous étudions ensuite de manière plus approfondie les structures récursives linéaires (listes chaînées, piles, files) ainsi que les bases de la programmation récursive.

Développement d’algorithmes simples de parcours d'arbres. Bases de la programmation et de l’algorithmique.

Comprendre et maîtriser un certain nombre de mécanismes et concepts fondamentaux propres aux traitements informatiques.

Présentation de concepts fondamentaux de l’informatique  : mécanismes liés aux échanges d’information entre fonctions, références, pointeurs et adresses ; la récursion  : ses liens avec les arbres et les piles, son élimination, la technique de backtracking ; quelques éléments de compression de textes et quelques éléments de cryptologie, numérisation des informations.

Acquérir la maîtrise des standards du Web tels que HTML et CSS et le modèle client / serveur. Apprendre un des langages les plus utilisés pour le développement serveur (e.g. PHP) ; connaître les rudiments de la manipulation et de l'interrogation des bases de données ; maîtriser l'interaction serveur Web / base de données.

Principes généraux des réseaux et d’Internet. Introduction au protocole HTTP. HTML. CSS. Introduction au PHP. Introduction aux bases de données et à un système simple de gestion de bases de donnée (e.g. MySQL). Introduction à SQL et à l'interface PHP / MySQL.

Arithmétique élémentaire (division euclidienne, congruence, pgcd, modulo) ; nombres complexes (parties réelle et imaginaire, opérations algébriques, racines des polynômes du second degré) ; polynômes (division euclidienne, factorisation, racine, formule de Taylor, degré) ; matrices (multiplication, puissance, inverse, pivot de Gauss, rang) ; suites et séries de réels (suites récurrentes linéaires d'ordre 2, lien avec les puissances de matrices ; séries de réels ; critères de comparaison pour la convergence ; série harmonique, séries de Riemann)

Maîtrise des concepts de la programmation objet et connaissance d’un système d’interface graphique.

Principes de base de la programmation objet  : classes et objets, références, héritage, notion de polymorphisme, exceptions, généricité. Utilisation d’une interface graphique définie dans un langage orienté objet.

Ce cours est une introduction à la théorie des automates finis et des langages formels, ainsi qu'à l'analyse lexicale.

Les langages rationnels sont étudiés tant sous l'angle algorithmique qu'algébrique. Sont abordés en particulier des algorithmes pour transformer une expression rationnelle en automates et vice-versa, pour déterminiser un automate et le minimiser  ; mais aussi le lemme de l'étoile ou la caractérisation de Myhill-Nerode des langages rationnels selon leur nombre de résiduels.

Enfin, l'introduction à l'analyse lexicale forme une partie plus orientée vers la pratique et la programmation.

Apprendre à manipuler les algorithmes (les comprendre, les modifier, et les concevoir)

Cet enseignement vise à présenter l’approche algorithmique de la résolution de problèmes simples et à sensibiliser les étudiants à la notion d’efficacité d’un algorithme. Tris simples  ; Manipulations de structures récursives (listes, arbres)  ; Backtracking.

À la fin de ce cours, un étudiant doit savoir utiliser tous les outils de développement classiques et avoir de premières notions de processus de développement.

• Savoir utiliser efficacement les outils de développement (éditeur de texte, compilateur, débogueur, profileur, “build system” et gestionnaire de version).
• Communiquer au sein d'une équipe pour collaborer (revue de code, répartition des tâches, débat sur des choix de conception).
• Être initié à la conception du logiciel (décomposition modulaire, principes de base du génie logiciel).
• Être sensibilisé à la qualité du logiciel et de son développement (mise en page de code source, respect de normes de codage, tests, …)

Développements limités (DL à l'ordre 1 et dérivabilité, équivalents, notations o et O, formule de Taylor-Young, développements limités, application à la détermination de limites)

Algèbre linéaire (espaces vectoriels, sous-espaces vectoriels, base, dimension, application linéaire, rang et noyau, représentation matricielle, déterminant, réduction des endomorphimes digonalisables)

Conduite d'un premier projet répondant à un cahier des charges.

• Identifier les grandes phases du développement logiciel (spécification, développement, validation, déploiement/distribution, maintenance).
• Connaitre et mettre en pratique au moins une méthode agile
• Mener à bien la réalisation complète d'un logiciel de petite taille à partir d'une spécification donnée.
• Appliquer les outils et méthodes modernes du développement logiciel introduits en conduite de projet.
• Systématiser l'écriture de tests unitaires et d'intégration, ainsi que l'usage d'un système d'intégration continue.
• Communiquer au sein d'une équipe pour collaborer (revue de code, répartition des tâches, débat sur des choix de conception).
• Documenter un logiciel pour son utilisateur final.
• Documenter un code source pour améliorer sa qualité.
• Retravailler du code (factorisation, généralisation, nettoyage).

Algorithmes et structures de données classiques. Compréhension des problèmes élémentaires de complexité.

Complexité  : ordres de grandeur usuels, complexité en temps et en espace, au pire, en moyenne  ; Analyse comparée des algorithmes de tri classiques ; permutations  ; Structures pour les ensembles  : listes, arbres binaires de recherche, tas, tables de hachage.

Maîtrise du langage C et de la bibliothèque standard.

Syntaxe générale, types, structures, unions, entrées/sorties standard ; notion de pointeur, arithmétique des pointeurs, allocation dynamique de mémoire, chaînes de caractères, structures de données (listes, arbres), le débogueur, modularisation de programmes en C, make et Makefile, pointeurs de fonctions, macro-fonctions.

Ce cours est une introduction à la logique et notamment au calcul propositionnel et à certaines techniques de déduction automatique  : résolution, méthode de Davis-Putnam et diagrammes de décision binaire.

Groupes concrets (groupes cycliques, groupe des permutations, racines de l'unité)

Probabilités discrètes (variables aléatoires à valeurs dans un ensemble fini ou dénombrable, loi de probabilité, espérance, indépendance, probabilité conditionnelle)

Algorithmique des graphes  : parcours de graphes, composantes (fortement) connexes, extensions linéaires, plus courts chemins, arbres couvrants minimaux, flots…

Savoir démontrer des résultats mathématiques sur des objets manipulés en informatique, en particulier en algorithmique.

• Techniques de démonstration de base : dénombrements élémentaires, preuves par récurrence, preuves par l'absurde.
• Graphes réguliers, connexes, acycliques, bipartis ; suite de degrés d'un graphe ; graphes eulériens, graphes hamiltoniens.
• Probabilités discrètes.
• Méthodes probabilistes sur les graphes.

L'objectif de ce cours est d'apprendre les primitives de la programmation fonctionnelle à travers le langage OCaml.

Types de base (int, float, bool, char), fonctions, déclaration des valeurs ; listes ; types algébriques : produit, somme, récursion, polymorphisme ; filtrage par motifs ; type unit (read/print), enregistrements ; effets de bord : exceptions, input/output, traits impératifs. Stratégies d'évaluation et efficacité, exemples de modélisation impérative et fonctionnelle.

L'objectif principal est de savoir utiliser la logique pour modéliser des problèmes et les résoudre ensuite à l'aide de logiciels comme les solveurs SAT et les solveurs SMT. Cela demande une bonne familiarité avec les formules logiques, leur sémantique, et leur manipulation par exemple à l'aide de mises sous formes normales, ainsi qu'une compréhension des principes de base de ces solveurs.

Des implémentations en Java ou en OCaml (qui est introduit en cours programmation fonctionnelle PF5) de la plupart des constructions du cours sont soit fournies soit réalisées en exercice.

Le cours introduit des notions qui seront approfondies entre autres dans les cours de bases de données (BD6), puis en Master en calculabilité et complexité, programmation logique et par contraintes, preuves assistées par ordinateur, sémantique des langages de programmation, méthodes formelles de vérification, et modélisation et spécification.

Le cours revisite la logique propositionnelle vue en cours d'outils logiques (OL4), et introduit la logique du premier ordre. Le programme général est  :

• Logique propositionnelle  : syntaxe et sémantique. Conséquences et équivalences logiques. Formes normales, forme clausale. Modélisation, solveurs SAT, recherche de modèle, algorithme DPLL. Recherche de preuve, calcul des séquents propositionnel.

• Logique du premier ordre  : syntaxe et sémantique. Formes normales, skolémisation. Théories logiques, interprétations normales, élimination des quantificateurs. Modélisation, solveurs SMT. Recherche de preuve, calcul des séquents du premier ordre.

Le but de ce cours est d'expliquer le rôle d'un système d'exploitation, et de maîtriser les mécanismes de base d'un système de type unix/linux (fichiers, processus et mémoire). Une partie du cours porte sur les structures de données et les algorithmes utilisés par unix, une autre sur la programmation bas niveau (C POSIX).

• Explorer les concepts de la POO au travers du langage Java.
• Découvrir et comprendre les bonnes pratiques associées, pour une programmation fiable, efficace, évolutive et pérenne.

• Savoir programmer des algorithmes et structures de données simples (n'importe quel langage).
• Avoir déjà programmé en Java.

• discussions sur la pertinence des différents concepts pour différentes situations, assorties de conseils d'usage (cf. patrons de conception)
• approfondissement des mécanismes vus en L2, notamment les plus “avancés”  : généricité, exceptions, …
• sujets nouveaux  : immuabilité, lambda-expressions, introduction à la programmation concurrente, …

Comprendre les grandes lignes du modèle relationnel et de sa structuration en trois niveaux  : conceptuel, logique et physique. Maîtriser la modélisation conceptuelle des données, ainsi que l'étape de traduction du schéma conceptuel en un schéma relationnel. Comprendre le rôle des contraintes d'intégrité et être capable de juger de la qualité d'un schéma relationnel en fonction d'un ensemble de contraintes données. Savoir concevoir une base de données, l’alimenter, la modifier et l’interroger. En particulier, savoir écrire et comprendre des requêtes en SQL avancé (e.g., requêtes imbriquées, avec agrégats etc.), mais également en algèbre relationnelle. Comprendre le lien entre algèbre relationnelle et optimisation des requêtes SQL. Comprendre le statut et le mode d'utilisation des vues et tables temporaires (y compris l'utilisation des tables temporaires pour exprimer des requêtes récursives), ainsi que les spécificités propres à la gestion des données incomplètes. Comprendre les grandes lignes du théorème de Codd (équivalence entre calcul relationnel sûr et algèbre relationnelle, lien avec SQL).

Bases de données relationnelles. Modèle conceptuel des données. Contraintes d'intégrité. Algèbre relationnelle. SQL. Données incomplètes. Vues. Requêtes récursives. Calcul relationnel.

• cycle de vie d'un logiciel
• les processus de développement logiciel
• conception et architecture d'un logiciel
• implémentation et qualité du code
• tests du logiciel

• édition de code source
• gestion de versions
• chaîne de compilation et automatisation
• édition de liens et bibliothèques logicielles
• développement piloté par les tests

• langage de programmation  : C
• outils  : emacs, git, gcc, gdb, make, check

Les grammaires algébriques sont utilisées en informatique pour définir une syntaxe structurée, par exemple la syntaxe d'un langage de programmation avec des constructions imbriquées comme des conditionnelles, boucles, définitions de fonctions et procédures. Ce module enseigne les grammaires algébriques d'abord d'un point de vue pratique  : comprendre et pouvoir écrire des grammaires, constructions d'analyseurs grammaticales descendantes (technique LL1) et ascendantes (technique LR1), utilisation d'un générateur d'analyse grammaticale moderne (menhir), interaction avec l'analyse lexicale et construction d'un arbre de syntaxe abstraite. Pendant les dernières semaines, les aspects fondamentaux des grammaires seront étudiés, comme leur relation avec les automates à pile, et les limites d'expressivité des grammaires.

• module Automates et Analyse Lexicale (AAL3) : expressions rationnelles, automates déterministes et non-déterministes, lemme d'étoile, analyse lexicale.
• programmation en OCaml au niveau du cours PF5

Apprendre à développer des programmes échangeant des données à travers un réseau.

Ce cours présente les paradigmes principaux de la communication par socket dans un réseau. Il introduit les bibliothèques de fonctions permettant de communiquer par flux (TCP) et par paquet (UDP) et propose différentes séries de travaux pratiques ainsi qu'un projet afin de maîtriser leur utilisation.

• Formaliser les grandes phases du développement logiciel et leur intégration dans quelques processus de développement.
• Être initié à l'analyse des demandes informelles d'un client par problématisation.
• Distinguer spécification fonctionnelle, spécification non fonctionnelle, et choix de conception.
• Maîtriser quelques architectures modulaires classiques.
• Appliquer les outils et méthodes modernes du développement logiciel introduits en conduite de projet.
• Systématiser l'écriture de tests unitaires et d'intégration, ainsi que l'usage d'un système d'intégration continue, dans un processus de développement dirigé par les tests.
• Connaitre plusieurs méthodes agiles (Scrum, XP) et développer un regard critique qui permet de choisir la méthode la plus adaptée au cas pas cas
• Utiliser des bibliothèques externes et être sensibilisé à la problématique des dépendances logicielles.
• Être sensibilisé à des concepts du génie logiciel comme la dette technique, la sûreté, la sécurité, etc.

L'objectif de ce cours est d'apprendre les concepts des langages de script essentiellement à travers le langage Python.

Ce cours/TP introduit et approfondit le langage de programmation Python. Les concepts importants de Python sont présentés et mis en pratique : listes, dictionnaires, expressions régulières, objets, librairies de gestion du système d'exploitation, etc. Le langage de script bash est également abordé.

Ce cours introduit aux principes des machines virtuelles exécutant du code-octet (comme Ocamlrun ou JVM) et présente les bases de la compilation d’un langage de haut niveau en code-octet. Ce cours s'apparie très naturellement au cours Grammaires et Analyse Syntaxique en donnant des exemples d'analyse sémantique appliquée au résultat de l'analyse syntaxique.

Machines à piles ; codage/décodage du code-octet ; compilation  : expressions, branchements, declarations locales et globales, données structurées, fonctions et notion de clôture. Exemples d’optimisation. Jeu d’instructions de Ocamlrun et JVM.

Les TP utiliseront le langage OCAML, le cours de programmation fonctionnelle au S5 est donc un pré-requis essentiel. Ce cours introduit aux principes des machines virtuelles exécutant du code-octet (comme Ocamlrun ou JVM) et présente les bases de la compilation d'un langage de haut niveau en code-octet.

Le but de ce cours est d'apprendre à développer des techniques de programmation pour pouvoir programmer rapidement (en quelques heures) des prototypes pour résoudre des problèmes algorithmiques dont l'énoncé est simple mais pour lesquels trouver la meilleure solution est un problème complexe (par exemple des problèmes NP-complets, comme le voyageur de commerce ou le problème du sac à dos). L'idée est de vous sensibiliser au fait que pour certains problèmes avec un grand nombre d'instances, il n'est pas toujours possible d'avoir un programme qui trouve rapidement la solution optimale, mais qu'en revanche on peut programmer des algorithmes efficaces qui cherchent une solution approchée.

Le cours comportera deux parties, une partie plus théorique où l'on abordera des questions de complexité et d'algorithmique et une partie plus pratique pour laquelle vous devrez programmer en peu de temps une solution pour un problème donné et ensuite nous passerons du temps à comparer vos solutions pour voir quelles sont les bonnes stratégies. L'évaluation se fera sous forme d'une compétition de programmation (la note ne se résumera pas au classement mais tiendra également compte du style de programmation). Les étudiants souhaitant suivre cette option sont vivement encouragés à venir passer le google hashcode dans le hub organisé par l'ufr (jeudi 28 février 2019 au soir).

• Maitrise d'un langage de Programmation (Java, Python ou C)
• Algorithmique
• Implémentation de structures de données
• Un peu de probabilités

L'objectif du cours de Programmation Web est de fournir une introduction aux méthodologies courantes pour le développement d'applications Web, coté client et coté serveur.

Ce cours démarre avec une révision des langages HTML et CSS pour la description de pages Web. Ensuite une petite révision du langage PHP et des systèmes de bases de données permet d'introduire le développement serveur. Le cours se concentre ensuite sur les “frameworks” coté serveur (e.g. Symfony) et sur les serveurs node.js, ainsi que ajax pour la communication client-serveur. Enfin le cours aborde la programmation côté client pour dynamiser les pages Web  : Javascript et la librairie Jquery, ainsi que les librairies côté client pour simplifier la programmation CSS (e.g. Bootstrap).

Connaissance minimale des langages HTML, CSS, PHP et SQL pour l'interrogation/manipulation de bases de données.

Ce cours est une introduction à la sécurité informatique. Il comporte une partie sur la cryptographie symétrique dans laquelle des algorithmes d'authentification (MAC) et de chiffrement symétriques (PRF, AES, DES) seront étudiés et programmés. La deuxième partie concerne les vulnérabilités des logiciels permettant de corrompre leur fonctionnement normal et quelques moyens pour prévenir ou atténuer ces attaques (analyse et test de programmes).

Mathématiques du premier cycle (notamment notions d'algèbre et de calcul des probabilités) ; notions de base de l'algorithmique (structures de données, complexité asymptotique) ; notions en programmation C, Java et Python ; notions en système Linux ; notions en architecture des ordinateurs (CI2) ; notions en outils internet (IO2).