0
Créez votre
plan de formation
Faire financer ma formation
4 Ects Code UE : NFA006 CPF

Structures de données

Donner les notions fondamentales de structures de données et de leur utilisation, et montrer comment les implanter à bon escient dans un langage de programmation de haut niveau. Faire comprendre l'importance de la spécification rigoureuse des structures de données, le pourquoi de l'étude de la complexité des algorithmes qui les manipulent, les principes de mise en oeuvre de ces structures.

Objectifs :
Donner les notions fondamentales de structures de données et de leur utilisation, et montrer comment les implanter à bon escient dans un langage de programmation de haut niveau. Faire comprendre l'importance de la spécification rigoureuse des structures de données, le pourquoi de l'étude de la complexité des algorithmes qui les manipulent, les principes de mise en oeuvre de ces structures.

Compétences visées :
- Savoir évaluer la complexité d'un algorithme simple en fonction de la taille des données.
- Savoir abstraire les principales structures de données, les spécifier et les implanter.
- Etre capable de choisir la bonne structure de donnée pour un problème de programmation quelconque.
- Etre capable d'écrire, de modifier et d'exécuter un algorithme manipulant une structure de données.

Pré-requis :
Ce cours suppose une connaissance minimale en algorithmique et en programmation.

Notions préliminaires
Rappel succinct des propriétés et caractéristiques essentielles des supports de mémorisation, tels que la mémoire centrale, les disques et les bandes. Notion de complexité des algorithmes : mesure d'efficacité en fonction de la taille du problème.
Les structures de données
Les structures séquentielles et les structures arborescentes. Principaux algorithmes liés à ces structures. Différentes techniques d'implantation de ces structures : avantages et inconvénients.
L'utilisation des structures
Principaux algorithmes de tri. Généralités et méthodes simples. Méthodes efficaces. Mesures et comparaisons entre ces algorithmes.
Principes de la recherche d'informations. Recherche séquentielle dans une liste quelconque. Recherche dichotomique dans une liste ordonnée pour laquelle on dispose de l'accès par le rang. Gestion d'un tas : solution efficace pour rechercher le plus petit élément d'un ensemble.
Utilisation de structures arborescentes pour la recherche. Les arbres binaires de recherche : recherche, adjonction et suppression. Évaluation de la complexité logarithmique en moyenne de ces opérations, et comparaison avec les structures séquentielles. Évaluation de la complexité au pire linéaire : amélioration par rééquilibrage donnant les arbres AVL. Analyse des opérations simples de rotation ponctuelle pour conserver l'équilibre.
Généralisation des arbres AVL aux arbres balancés pour prendre en compte une caractéristique des disques : la taille des blocs transférés. Application aux fichiers séquentiels indexés.
Recherche utilisant la notion de hachage : principes et méthodes de résolution des collisions.
Remarque : Implantations proposées au moyen de paquetages Ada génériques disponibles en machine (ou modules Java ou C++), pour que les élèves puissent les utiliser lors de travaux pratiques personnels, et apprennent ainsi les notions fondamentales de réutilisation du logiciel.

Modalités de validation :
Examen

Sélectionnez votre ville puis ajoutez à votre plan de formation la session qui vous convient :
  • 100% Internet
Ajouter
octobre 2017 - janvier 2018

Ajouter
octobre 2018 - janvier 2019

Ajouter
février 2019 - juin 2019

Ajouter
octobre 2019 - janvier 2020

Ajouter
février 2020 - juin 2020

Modalité Volume horaire Employeur (OPCA) Pôle emploi Moi même
40H 600 € 520 € 120 €

Où et quand s’inscrire ?

Vous pouvez contacter le Cnam par téléphone au 0972 311 312 (prix d'un appel local) :
du lundi au vendredi : 9h00 - 13h00 / 14h00 - 17h30

Brest

Tél : 0 972 311 312
brest@cnam-bretagne.fr

Horaires d’accueil toute l’année

Du lundi au vendredi

10h00 - 13h00 / 14h00 - 17h30

Du 22 janvier au 17 février 2018

Du lundi au vendredi

10h00 - 13h00 / 14h00 - 18h30

Samedi

9h30 - 13h30

En savoir +

Lannion

Tél : 0 972 311 312
lannion@cnam-bretagne.fr

Horaires d’accueil toute l’année

Mardi, jeudi

10h00 - 13h00 / 14h00 - 17h30

 

Du 22 janvier au 17 février 2018

Lundi, mardi, jeudi

10h00 - 12h45 / 14h00 - 18h30

Samedi

9h30 - 12h00

En savoir +

Lorient

Tél : 0 972 311 312
lorient@cnam-bretagne.fr

Horaires d’accueil toute l’année

Uniquement sur rendez-vous (contact téléphonique : 02 57 62 02 40)

 

Du 22 janvier au 17 février 2018

Période spéciale d'inscription - ouverture du lundi au samedi matin inclus

Uniquement sur rendez-vous (contact téléphonique : 02 57 62 02 40)

En savoir +

Quimper

Tél : 0 972 311 312
quimper@cnam-bretagne.fr En savoir +

Rennes

Tél : 0 972 311 312
rennes@cnam-bretagne.fr

Horaires d’accueil toute l’année

Du lundi au vendredi

10h00 - 13h00 / 14h00 - 17h30

Du 22 janvier au 17 février 2018

Du lundi au vendredi

10h00 - 13h00 / 14h00 - 18h30

Samedi

9h30 - 13h30

En savoir +

Saint-Brieuc

Tél : 0 972 311 312
ploufragan@cnam-bretagne.fr

Horaires d’accueil toute l’année

Du lundi au vendredi

10h00 - 13h00 / 14h00 - 17h30

Du 22 janvier au 17 février 2018

Du lundi au vendredi

10h00 - 13h00 / 14h00 - 18h30

Samedi

9h30 - 13h30

En savoir +

Saint-Malo

Tél : 0 972 311 312
saint-malo@cnam-bretagne.fr En savoir +

Vannes

Tél : 0 972 311 312
vannes@cnam-bretagne.fr

Horaires d’accueil toute l’année

Lundi, mardi, jeudi, vendredi

10h00 - 13h00 / 14h00 - 17h30

Du 22 janvier au 17 février 2018

Lundi, mardi, jeudi, vendredi

10h00 - 13h00 / 14h00 - 18h30

Samedi

9h30 - 13h30

En savoir +

Vitré

Tél : 0 972 311 312
vitre@cnam-bretagne.fr

Horaires d’accueil toute l’année

Du lundi au vendredi

09h00 - 12h30  / 13h30 - 17h00

Du 22 janvier au 17 février 2018

Période spéciale d'inscription

Du lundi au vendredi

09h00 - 12h30 / 13h30 - 17h00

En savoir +

Formation à distance

En savoir +
Télécharger le dossier d’inscription