algorithmique - publié le 06/03/2009

Résumé du document

Algorithmique, cours de 60 slides powerpoint



Algorithme = suite d'actions que devra effectuer un automate pour arriver à partir d'un état initial, en un temps fini, à un résultat





Mémoire, pointeurs

Organisation d'un programme

Structures de données: listes, arbres, tables...

Algorithmique: exemple des tris

Extraits

[...] void tree_postorder( TreeNode_t* p_root, void do_it)( Data_t* ) ) { TreeNode_t* p_node = NULL; if( p_root NULL ) { return; } p_node = p_root->p_first_child_; while( p_node = NULL ) { tree_postorder( p_node, do_it p_node = p_node->p_next_; } p_root->p_data_ return; } Arbres: parcours in-order < number > Parcours de gauche à droite: Sur la position courante: l'enfant le plus à gauche a la priorité puis la position courante puis les autres enfants void tree_inorder( TreeNode_t* p_root, void do_it)( Data_t* ) ) { TreeNode_t* p_node = NULL; if( p_root NULL ) { return; } p_root is a leaf if( p_root_->p_first_child_ NULL ) { p_root->p_data_ return; } tree_inorder( p_root->p_first_child_, do_it ( p_root->p_data_ p_node = root p_first_child_->p_next_; while( p_node = NULL ) { tree_inorder( p_node, do_it p_node = p_node->p_next_; } return; } Structures de données complexes: Les Graphes N1 N2 N3 N9 N7 N6 N5 N8 N4 N10 N12 N11 N14 N13 N16 N15 N18 N17 < number > Types et définitions : ouvert, fermé, connexe, non connexe, Cyclique/acyclique orienté / non orienté valués / non valués Applications : Réseaux routiers/ferroviaires, aérien, Ordonnancement de taches en Recherche opérationnelle problèmes de flux (hydraulique, files d'attente, etc.) Opérations: chemin le plus court fermeture transitive tri topologique flux maximum . Partie IV Algorithmes et complexité : exemple des tris < number > Exemple : Algorithmes de tri Tri d'un tableau de taille n : n possibilités Applications: bases de données géométrie algorithmique . [...]

[...] Les tableaux Taille fixe, en général Réajustement de taille coûteux en temps Insertion d'élément onéreuse en temps. Accès indexé (de 0 à n-1 pour un tableau de n éléments) Stockage compact < number > Liste chaînée : Spécifications Créer une liste vide Ajouter un élément (début / fin / milieu) Retirer un élément (début / fin / milieu) Détruire une liste Trier les éléments d'une liste < number > Notre but est d'écrire une librairie de programmation qui pourra être utilise par du code client (n'importe quel programme qui a besoin d'utiliser des listes chaînées). [...]

[...] les schémas de boucle while( . . } do{ . } while( . ) L'allocation dynamique de chaque Data_t est nécessaire (sinon, les valeurs entrées sont perdues) Que se passe-t-il a la fin de la fonction ? [...]

[...] S'assurer de ne jamais perdre l'adresse d'une zone allouée dynamiquement. Dans un programme, toute allocation par malloc ou calloc doit être suivie d'une désallocation par free < number > Fichier list.c: #include “list.h” #include “defs.h” Dans defs.h : defs de Bool_t, #define MALLOC(T) (T*)malloc( sizeof(T) etc. void list_error( char* message ) { printf( “List Error: %s\n”, message } List_t* list_create( void ) { List_t* p_new_list = MALLOC( List_t if( p_new_list NULL ) { list_error( “Could not allocate new list” return NULL; } p_new_list->p_first_ = NULL; p_new_list->p_last_ = NULL; p_new_list->nb_elements_ = retrurn p_new_list; } int list_insert_item( List_t* p_list, Data_t* p_data ) { if( p_list NULL p_data NULL ) { list_error( “NULL Parameter ” return FALSE; } p_node = MALLOC( Node_t if( p_node NULL ) { . [...]

[...] Pourquoi faire de l'info a Geol Modélisation de plus en plus employée dans l'industrie et la recherche. Elements finis (modélisation d'écoulements, déformations et rupture) Géostatistique et Analyse des données Modélisation géométrique Systèmes experts et recherche opérationnelle de la promo99 dans l'info Cette année: TDs et projets 2A de programmation (Cf Christine Fay-Varnier) Eventuellement projet de labo Plan Mémoire, pointeurs Organisation d'un programme Structures de données: listes, arbres, tables . Algorithmique: exemple des tris < number > Partie I La mémoire < number > Les mémoires . [...]