Algorithmique et

Informatique Théorique

Licence 2 MASS


Descriptif

Le cours a pour but d'approfondir l'algorithmique et d'introduire des notions d'informatique théorique.



haut de page

Conseils - Travail attendu - assiduité

Conseils

Je vous rappelle quelques conseils de réussite (liste non exhaustive) concernant l'organisation de votre tavail :
  • Apprendre le cours chaque semaine :
    • organiser vos prises de notes (relire, complèter, surligner, etc)
    • connaître sur le bout des doigts les définitions, les algorithmes, les exemples, etc.
    • utiliser d'autres sources d'informations pour complèter le cours (livre de cours, magasines, internet, etc.)
  • Préparer les séances de TP :
    • avoir et lire l'énoncé
    • (re)apprendre les points de cours nécessaires à la résolution des exercices
    • commencer les exercices sur papier et/ou sur machine
  • Tester son apprentissage :
    • terminer les exercices non finalisés pendant les séances
    • vérifier que vos connaissances par rapport aux objectifs du cours
    • refaire les exercices non maîtrisés
    • poser des questions à vos enseignants (email, oral, ...) sur un point particulier encore flou
    • résoudre des exercices ou réaliser des projets provenant d'autres sources (livre de cours, internet, cours ancien, imagination, etc.)
    • réfléchir sur ce vous avez appris et sur ces intéraction avec les autres enseignements ou votre environnement quoditien

Travail attendu

Vous comprendrez bien en suivant les "conseils" ci-dessus que l'apprentissage de l'enseignement nécessite un temps de travail non négligeable. Bien qu'il est difficile d'évaluer la durée nécessaire minimale qui dépend de chacun, on peut dire que les plus rapides d'entre vous pour qui le cours est acquis parfaitement à la sortie de la séance passerons au moins 1 heures de travail par semaine, et pour la plupart d'entre vous passerez plusieurs heures par semaine.


Afin de valoriser un travail régulier et de vous permettre de faire le point sur vos connaissances le plus régulièrement possible, nous organiserons plusieurs fois des devoirs pendant les séances de cours ou de TP. Il se peut que des intérrogation est lieues.


Soyez curieux !

N'hésitez pas à consulter d'autres sources d'informations en rapport de près ou de loin avec cet enseignement provenant de la bibliothèque universitaire, d'internet, de vos amis, de vos lectures... Mettez en relation le contenu de cet enseignement avec votre propre expérience et surtout les enseignements des autres disciplines que vous avez appris.

Assiduité

Ce cours d'algorithmique aborde des notions basiques qui néanmoins nécessite un investissement personnel soutenu comme toute autre enseignement. Je vous rappelle donc qu'il est important que vous assistiez à l'ensemble des cours et TP.
En conséquence, la présence aux TP est OBLIGATOIRE. Votre présente sera notée à chaque séance et sera prise en compte dans l'évaluation finale de l'enseignement.





haut de page

L'équipe d'enseignants

Sébastien Verel - chargé de cours et TP
Pooran Memari - chargé de TP
Nicolas Julien - chargé de TP

haut de page

Horaires

Cours :
jeudi 8h - 10h, amphi math
TP :
Groupe 1A : mardi 08h00 - 10h00, salle M-0-1 (SV)
Groupe 1B : mercredi 15h15 - 17h15, salle M-2-6 (PM)
Groupe 2A : mardi 10h15 - 12h15, salle M-2-6 (SV)
Groupe 2B : mercrdi 17h30 - 19h30, salle M-2-3 (NJ)

calendrier de l'enseignement au format html
calendrier de l'enseignement au format ical à mettre dans votre agenda électronique si vous le désirez.

Emploi du temps de Licence 2 MASS : html

haut de page

Evaluation

Les évaluations comprennent :
  • 1 devoir surveillé obligatoire (DS1) le jeudi 28 février entre 8h et 10h, Amphi Math
  • 1 devoir surveillé obligatoire (DS2) le Jeudi 17 avril entre 8h et 10h, Amphi Math
  • 1 devoir non surveillé (DM) entre le 20/03 et 03/04
  • 1 note (P) de TP (présences et interrogation)

La note finale est calculée de la manière suivante :
  • pour les non-dispensés : note finale = 0.35 (DS1+DS2) + 0.2 (DM) + 0.1 (P)
  • pour les dispensés : note finale = 0.35 (DS1+DS2)+ 0.3(DM)

Sujets de l'année 2007-2008 :
Sujets précèdents de l'année 2006-2007 :

haut de page

Plan et énoncés

Vous pouvez obtenir la version imprimable au format pdf du plan et surtout des objectifs ICI .

Pour que le cours consomme moins de pages, trouver l'option qui permet d'imprimer plusieurs pages (2, 4, 6 ou 8) par feuille dans Acrobat Reader et imprimer en recto-verso si vous pouvez.

Séance Titre Cours TP corr
21/01-23/01 Révisions tp00 co00
24/01-30/01 Introduction à l'algorithme cm01 tp01 co01
31/01-06/02 Notion de machine et type de données abstraits cm02 tp02 co02
07/02-13/02 Algorithmes récursifs cm03 tp03 co03
14/02-27/02 Type de données abstrait séquenciel cm04 tp04 co04
28/02-05/02 Type de données abstrait arbre cm05 tp04 co05
06/03-12/03 Relation d'ordre cm06 tp06 co06
13/03-19/03 Langages rationnels cm07 tp07 co07
20/02-26/03 Principe d'induction cm08 tp08 co08
27/03-02/04 Automate non déterministe cm09 tp09 co09
03/04-09/04 Test et Vérification d'algorithmes cm10 tp10 co10
10/04-16/04 Synthèse et complexité cm11
17/04/08 Devoir Surveillé 2


haut de page

Objectifs

Les objectifs seront modifiés d'ici janvier.

Vous trouverez ci-dessous une liste assez détaillée des objectifs du cours (au format html). Vous devrez acquérir l'ensemble de ces connaissances théoriques et pratiques tout au long de cet enseignement. Cette liste est une aide qui explicite les connaissances que l'on attend que vous sachiez au final.
Servez-vous en pour faire le point très régulièrement de votre apprentissage. Bien entendu, les évaluations porteront sur ces objectifs.
  1. connaitre une définition d'algorithme
  2. maîtriser les algorithmes conditionels
  3. maîtriser les algorithmes itératifs
  4. utiliser et écrire des fonctions
  5. Connaitre la définition de machine abstraite et type de donnés abstrait
  6. Donner le résultat d'un algorithme s'exécutant sur une machine abstraite
  7. écrire un algorithme avec une srtucture de donnée indexée
  8. écrire un algorithme itératif de recherche dans un tableau
  9. savoir écrire correctement un algorithme de plus de 10 lignes
  10. savoir démontrer à l'ade du principe de récurrence
  11. savoir définir le lien entre preuve par récurrence et algorithme récursif
  12. écrire des algorithmes récursifs comme par exemple celui calculant la factorielle et recherchant un élément par dichotomie
  13. connaitre le type de données abstrait liste
  14. connaitre le type de données abstrait pile et file
  15. écrire des algorithmes récursifs basés sur le TDA liste, en particulier le calcul de la longueur, l'extraction de sous-liste, la concaténation de listes, l'ajout et la supression déléments, l'utilisation d'accumulateur
  16. connaitre le type de données abstrait arbre
  17. écrire des algorithmes récursifs basés sur le TDA arbre, en particulier le parcours d'arbre, de filtre et de recherche d'élements
  18. connaitre la définition de relation d'ordre
  19. prouver qu'une relation binaire est une relation d'ordre
  20. connaitre l'ordre lexicographique et de la divisibilité sur les entiers
  21. donner le diagramme de Hasse d'une relation d'ordre finie
  22. construire et écrire des ensembles définis inductivement
  23. prouver par induction
  24. notion de terminaison d'algorithme
  25. savoir définir mot et language.
  26. savoir définir language rationnel
  27. savoir écrire une expression régulière simple
  28. savoir définir le langage reconnu par un automate fini
  29. connaître le théorème de Kleene
  30. définir automate à état fini reconnaissant un language rationnel simple
  31. déterminiser un automate
  32. savoir proposer un jeux de tests simples pour un algorithme
  33. connaître la différence entre jeux de tests et preuve de correction
  34. prouver la correction d'algorithmes utilisant l'affectation, les conditions simples, les itérations
  35. savoir définir les notions de complexité spatiale et temporelle
  36. connaitre le lien entre machine abstraite, type de données abstraite, terminaison, complexité et correction


haut de page

last change : jan 14, 2008