Wiki du LAMA (UMR 5127) - Contributions [fr]

INFO510 et INFO511 : Algorithmique et structures de données

2011-05-20T13:04:02Z

Pranavwright :

Cours du semestre 5 de la licence STIC TR et ETT.

Responsable (depuis 2007): Jacques-Olivier Lachaud
* 2010-2011 : Jacques-Olivier Lachaud (C/TD/TP), Mouhammad Said (TD/TP)

== Quelques ressources pour l'étudiant (2010-2011) ==

Attention, ces ressources ne servent que de compléments pour les modules INFO510 et INFO511, et ne remplacent en aucun cas les cours, TDs et TPs donnés.

# Notes de cours [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Cours/notes-de-cours.ps PostScript] [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Cours/notes-de-cours.pdf PDF]
# Fiches de TD
#* TD 1 : Structures de contrôle, fonctions, tableaux [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-1.ps PostScript] [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-1.pdf PDF]
#* TD 2 : Boucles imbriquées [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-2.ps PostScript] [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-2.pdf PDF]
#* TD 3 : Tris [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-3.ps PostScript] [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-3.pdf PDF]
#* TD 4 : Listes, Files, Piles [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-4.ps PostScript] [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-4.pdf PDF]
#* TD 5 : Implémentation des listes par curseur [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-impl-liste.ps PostScript] [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-impl-liste.pdf PDF]
#* TD 6 : Graphes [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-6.ps PostScript] [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/TDs/td-6.pdf PDF]
# TPs et autres travaux pratiques [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Tests/doc/html/index.html Pages des TPs]
#* Pour la première fois, on pourra aussi regarder la page [[Comment_compiler_le_C_%3F]]
#* Si vous n'accédez pas aux pages "manual" en salle TP, on les trouve en ligne : [[http://www.linux-france.org/article/man-fr/ Manual pages]]
# Autres ressources
#* cours Algo de Eric Sopena, Univ. Bordeaux 1, partie I [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Cours/cours-ES-1.ps Fichier PostScript]
# Annales
#* Examen INFO510 (2008-2009) : [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-INFO510-2008-2009.ps sujet Postscript], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-INFO510-2008-2009.pdf sujet PDF], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-sol-INFO510-2008-2009.ps corrigé (partiel) Postscript], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-sol-INFO510-2008-2009.pdf corrigé (partiel) PDF], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/sudoku.cxx Code C++ du Sudoku]
#* Examen INFO510 (2007-2008) : [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-INFO510-2007-2008.ps sujet Postscript], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-INFO510-2007-2008.pdf sujet PDF], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/support.ps support Postscript], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-sol-INFO510-2007-2008.ps corrigé Postscript], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-sol-INFO510-2007-2008.pdf corrigé PDF]
#* Examen INFO511 (2008-2009) : [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-INFO511-2008-2009.ps sujet Postscript], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-INFO511-2008-2009.pdf sujet PDF], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-sol-INFO511-2008-2009.ps corrigé (partiel) Postscript], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-sol-INFO511-2008-2009.pdf corrigé (partiel) PDF]
#* Examen INFO511 (2007-2008) : [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-INFO511-2007-2008.ps sujet Postscript], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-INFO511-2007-2008.pdf sujet PDF], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-sol-INFO511-2007-2008.ps corrigé Postscript], [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Examen/examen-sol-INFO511-2007-2008.pdf corrigé PDF]

== Déroulement INFO510 ==

Ceci n'est qu'une prévision.

* (Cours 1) lundi 4 octobre : Qu'est-ce que l'algorithmique ? Correction + Compromis vitesse / mémoire. Rappels d'algorithmique élémentaire (I).
* (Cours 2) mercredi 6 octobre : Rappels d'algorithmique élémentaire (II). Types complexes (Tableaux, Entités). Actions/Fonctions (I).
* (TD 1) lundi 11 octobre : Exercices sur actions/fonctions et tableaux.
* (Cours 3) mercredi 13 octobre : Actions / Fonctions (II). Récursivité. Algorithmique sur les tableaux. (I).
* (Cours 4) mercredi 13 octobre : Tri (I). Tris de base.
* (Cours 5) mardi 19 octobre : Tri (II). Tri rapide. Sélection.
* (Cours 6) vendredi 22 octobre : Structures séquentielles (I). Principe. Pile. File.
* (TD 2) vendredi 22 octobre : TD machine (TP0)
* (TD 3) mardi 2 novembre : Exercices sur actions/fonctions et tableaux.
* (Cours 7) mercredi 3 novembre : Structures séquentielles (II). Files à double entrées. Listes.
* (TD 4) mercredi 3 novembre : Exercices autour des tris.
* (TD 5) vendredi 5 novembre : Exercices sur listes. Implémentation des listes par tableaux avec chaînage.
* (TD 6) lundi 8 novembre : Applications des structures séquentielles. Hachage.
* (TD 7) mercredi 10 novembre : Applications des structures séquentielles. Radix-tri, tri fusion.
* (TP 1) vendredi 12 novembre : TP sur les tris.
* (TP 2) vendredi 12 novembre : TP sur les files à double-entrée. Application au calcul de l'enveloppe convexe. (I)
* (TP 3) mercredi 17 novembre : TP sur les files à double-entrée. Application au calcul de l'enveloppe convexe. (II)

== Déroulement INFO511 ==

* (Cours 1) lundi 8 novembre : Arbres (I)
* (Cours 2) mardi 9 novembre : Arbres (II)
* (TD 1) mardi 9 novembre : Exercices sur les arbres.
* ...

== Historique ==

* 2009-2010 : Jacques-Olivier Lachaud (C/TD/TP), Laurent Boyer (TD/TP)
* 2008-2009 : Jacques-Olivier Lachaud (C/TD/TP), Laurent Boyer (TD/TP)
* 2007-2008 : Jacques-Olivier Lachaud (C/TD/TP)

[http://writing-help.org/ Writing help]

INFO505 : algorithmes de graphes

2011-05-20T13:04:00Z

Pranavwright :

Ce wiki est un complément de cours pour la seconde partie du cours « info-505 : graphes et algorithmes ». Cette seconde partie traite de la partie algorithmique plus que de la partie théorique des graphes. La participation au wiki est fortement encouragée.

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style ''PrenomNom''...)

Je vous conseille d'aller lire [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

==Administration==

===TD et TP===

-- à venir

===Compléments de cours / TD / TP===

-- à venir

===Références===

La partie « Algorithmes sur les graphes » du livre « ''Introduction à l'algorithmique'' » de Cormen, Leiserson et Rivest est un bon complément. Il contient des exemples, applications et preuves de certaines propriétés des algorithmes étudiés en cours...

-----------------
-----------------

==Introduction, quelques dates==

Euler, problèmes des ponts de Königsberg (1736), notion de graphe eulérien

def : un graphe est eulérien si ...

def : un graphe est hamiltonien si ...

problèmes de complexité

Kuratowski 1930, notion de graphe planaire, contre exemple : K_5 et K_{3,3}

exemple des maisons et des usines

théorème de Kuratowski

Appel et Haken 1976, théorème des 4 couleurs (preuve par ordinateur)

problématiques de graphes dans les réseaux (Internet, télécommunications, ...)

==Graphes et arbres, préliminaires==

===Définitions===

...

:'''Vocabulaire :'''
:* sommets adjacents
:* arêtes adjacentes
:* arête incidente
:* degré d'un sommets, degré entrant / degré sortant

===Arbres===

...

===Représentation des graphes===

listes d'adjacence

matrice d'adjacence

matrice d'incidence

'''Question :''' quelle est la meilleure représentation ?

==Parcours de graphes : largeur et profondeur==

===Parcours en largeur===

====Principe du parcours====

on utilise une file pour les prochains sommets à traiter

on garde un tableau d'états pour ne pas parcourir plusieurs fois les sommets
(sinon, on risque de faire des boucles et le parcours ne s'arrêtera jamais)

on essaie de partir de tous les sommets pour être sûr de parcourir tout le graphe
(si par exemple, le graphe est non connexe)

====Algorithme====

====Complexité====

complexité en O(n+m) pour des graphes en listes d'adjacence

complexité en O(n*n) pour des graphes en matrice d'adjacence

====Application====

calcul des distances à un sommet donné

calcul des distances entre deux sommets donnés

tester si un graphe est biparti (pas vu en cours)

===Parcours en profondeur===

====Principe====

on pourrait utiliser une pile pour parcourir les sommets, mais c'est plus simple si on écrit un algorithme récursif

en plus des états et de la foret couvrante, on garde un « temps de parcours » pour chaque sommet
(temps de début et temps de fin)

====Algorithme====

====Complexité====

O(n+m) pour des graphes en listes d'adjacence

====Application====

calcul des composantes fortement connexes dans un graphe orienté (en TP)

tri topologique dans un graphe acyclique

==Arbres couvrants==

-- Nous verrons en fait uniquement l'algorithme de Prim

But : trouver un arbre de poids minimal sur un graphe non-orienté avec des poids sur les arêtes

===Algorithme de Prim===

====Algorithme====

on construit un arbre en partant d'un sommet et en rajoutant des arêtes adjacentes

====Complexité====

O(n*n) pour la variante simple, mais on peut faire du O(m*log(n)) ou même O(m+n*log(n))
(c'est mieux quand il n'y a pas trop d'arêtes dans le graphe)

===Algorithme de Kruskal===

====Algorithme====

on construit un arbre en regroupant petit à petit des des morceaux d'arbre
(on part avec un arbre trivial pour chaque sommet)

====Complexité====

O(n*m) ; mais si on se débrouille bien : O(n*log(n))

==¿¿ Chemin optimaux ??==

-- Si le temps le permet

===Algorithme de Dijkstra===

===Algorithme de Bellman===

==¿¿ Flot maximal ??==

-- si le temps le permet

===Algorithme de Ford-Fulkerson===

[http://cvresumewriters.com/ resume writers]

Géométrie discrète

2011-05-20T13:03:58Z

Pranavwright :

= Discussion autour de bibliothèques et de codes sur la géométrie discrète =

== Objectifs généraux ==

L'objectif est de fournir un noyau stable pour développer des applications utilisant des techniques de géométrie discrète. Autour de ce noyau, un certain nombre de petits applicatifs pourra être proposé. De même, la création de certains plug-in pour des plateformes classiques sera envisagé. Un tel effort collectif de la communauté vise à répondre aux enjeux suivants :
* faciliter le développement de nouveaux algorithmes/outils en géométrie discrète ;
* faciliter la communication de résultats concrets à la communauté, permettre par exemple des comparisons précisions/robustesse/temps de calcul entre différentes approches ;
* mieux diffuser les travaux de géométrie discrète dans d'autres communautés, notamment le traitement et l'analyse d'image, la reconnaissance des formes, la géométrie algorithmique
* accélérer la formation des nouveaux arrivants en géométrie discrète, faciliter le démarrage des thèses, accroître le développement de la communauté

== Wishlist scientifique ==

Ce que doit pouvoir fournir la lib (attention c'est en vrac)

* Définition d'images nD
* I/O sur les images 2D et 3D (--> VKT/ITK ?)
** ''Ne pas se limiter à 2/3 formats semble indispensable pour atteindre l'objectif de diffusion des outils GeoDis comme celui de démarrage des thèses. Sans tomber dans l'extrème des formats exotiques, mieux vaut prévoir large. Liste à compléter spécifique sur ce point ?'' (SebF 16 juin 2009)
** ''Si on branche avec un truc comme VTK/ITK, on aura l'avantage de pas avoir à faire ça : ces bibliothèques ont déjà tous les loaders possibles''--[[Utilisateur:Dcoeurjo|Dcoeurjo]] 17 juin 2009 à 14:38 (CEST)
** ''Certes, mais on ajoute une dépendance très forte avec une autre lib.'' --[[Utilisateur:SebF|SebF]] 17 juin 2009 à 17:15 (CEST)
** ''Les I/O images peuvent être mis dans un package séparé du noyau."" --[[Utilisateur:Lachaud|Lachaud]] 18 juin 2009 à 10:18 (CEST)
** ''Mais il est peut-être bon d'avoir un mécanisme I/O minimal indépendant, genre pgm en 2D ou simplevol en dim sup. "" --[[Utilisateur:Lachaud|Lachaud]] 18 juin 2009 à 10:34 (CEST)
* Modélisation de la surface d'un objet
* Modélisation d'une partition en objets <s>(--> Carte combi)</s>
** Graphe d'adjacence --[[Utilisateur:Gdamiand|Gdamiand]] 26 juin 2009 à 17:32 (CEST) (pour avoir une sd light permettant de représenter les régions et les adjacences, ensuite mettre les cartes combinatoires à coté dans un module séparé car c'est gros...).
** + arbre d'inclusion ? (ou une SD graphe avec arêtes valué)

* Itérateurs/Circulateurs
** Sur le volume (ligne, colonne, coupe isothetique,...)
** Sur une région (les voxels de la région)
** Sur les régions (rag ? <s>--> carte combi + arbre d'inclusion ?</s>)
** Sur la surface d'une région (border tracking, support géodésique autour d'un surfel,...)

* Noyau arithmétique (pgcd,...) ( --> passerelle BOOST ?)
* Noyau algèbre linéaire ( --> passerelle BOOST ?)
* Noyau GeoAlgo ( --> passerelle CGAL ??)

* Noyau Géométrique
** objets : point, droite discrète, plan, cercles, polynomes, coniques, simplexes en dims sup (Je ferais la distincton objets euclidiens et discrets --[[Utilisateur:Lachaud|Lachaud]] 18 juin 2009 à 10:15 (CEST))
*** objets (topologiques) discrets : pixel/voxel avec topologie Rosenfeld (couples), spel/surfel avec topologie Hermann/Udupa (couples aussi), cellules avec topologie cellulaire (standard)
*** objets (géométriques) discrets (arithmétique): point, droite, plan, cercle, polynome (fait-on beaucoup mieux en discret ?)
*** objets (géométriques) discrets (arithmétique + sous-ensemble): segments, morceaux de ce qu'il y a au-dessus
*** objets (géométriques) continus (?) : est-ce que nous prenons nos outils ou nous nous basons sur une bibliothèque externe même au niveau du noyau ?
** Intersection objects
** Reconnaissance
** Reconstruction géométrique
** <s>(ex Algorithmes géo discrète ('''est-ce que ce serait pas dans le noyau géometrique ci dessus ça ?--[[Utilisateur:Dcoeurjo|dcoeurjo]] 17 juin 2009 à 16:21 (CEST)''') ok pour moi --[[Utilisateur:Lachaud|Lachaud]] 18 juin 2009 à 10:15 (CEST))</s>
** extraction segments maximaux, couverture tangentielle, en temps optimal
** extraction segments flous maximaux, ..., en temps optimal
** algorithmes basés préimage : extraction de droites, plans discrets
** transformées en distance (chanfrein ou autres), extraction d'axe médian
** algorithmes de polygonalisation, polyédrisation
** estimateurs géométriques
** convexité discrète
** transformation d'objets, rajout de bruits suivant différents modèles.--[[Utilisateur:Kerautret|Kerautret]] 23 juin 2009 à 21:58 (CEST)

''Pourquoi la topo discrète n'auraient elle pas son "noyau" ? La notion de connexité, comme celle de point simple, est aussi centrale en GeoDis que la reconstruction géométrique, non ?'' --[[Utilisateur:SebF|SebF]] 17 juin 2009 à 17:56 (CEST)
Je suis d'accord aussi. Néanmoins, il faut sans doute un noyau de noyaux qui décrit les éléments de bases : pixels/voxels, surfels, objets ? --[[Utilisateur:Lachaud|Lachaud]] 18 juin 2009 à 10:15 (CEST)

* Algorithmes topo discrète
** suivi de surface (ouvert/fermé), suivi de bord
** test de connexité, découpage en composantes connexes, étiquetage en composante connexe
** points simples binaires, points simples multilabels
** amincissement, squeletisation
** complexes cubiques, effondrements

Ce qu'il pourrait y avoir autour (dans le cadre de plug-in ?):

* visualisation 2D/3D d'objets discrets. Visualiser des données associées à chaque cellule. Interaction ?
* synthèse d'objets discrets
** ''Oui (pas pourrait). Indispensable pour le côté comparaisons des méthodes. Tout monde doit pouvoir facilement travailler sur les même objets synthétiques.'' --[[Utilisateur:SebF|SebF]] 17 juin 2009 à 17:28 (CEST)
* outil de visu et d'analyse de primitives discretes
* plugins de calcul d'estimateurs discrets pour l'analyse quantitative

*Page web permettant de d'obtenir directement des résultats d'estimateur ou autres sans passer par du code? Appel d'un script php sur un serveur. --[[Utilisateur:Kerautret|Kerautret]] 23 juin 2009 à 21:58 (CEST)

* Algo de segmentation ?
** split and merge
** modèle déformables

==== Tentative structure ====

* Niveau 1
** [[NombresArithmétiqueAlgèbre]]
**[[ObjetsDiscrets]]

<code>
<Geometrical Kernel> <Topological Kernel>
{droite,plan,...,reco,inter} {bord, region, iterateurs,tracking}

<Topological Analysis Toolbox> <Border Processing ToolBox> <Region Processing Toolbox> <Arith. Image Processing Toolbox>
{Euler, ...} {Estimateurs, MC,...} {Skel Topo, DT, Axe median} {rotation arith., scaling}

<Visualisation Toolbox> <CGAL Binding> <VTK Binding> <VIGRA Binding> ...
|
|
<Paraview Plugin>

</code>

[[ Structuration ImaGene ]] (je mets ici ma structure pour voir comment je peux la projeter dans un tel découpage --[[Utilisateur:Lachaud|Lachaud]] 18 juin 2009 à 14:46 (CEST))

== Wishlist technique ==

* Langage, systèmes
** Langage choisi : C++ ?
** Systèmes : Linux, MacOS, Windows ?

* Noyau(x) commun(s)
** Contenu du ou des noyaux
** dépendance par rapport à d'autres bibliothèques
:: Cette question me semble très importante pour définir ce qui est dans le noyau et ce qui est extérieur. Par exemple, il ne me semble pas souhaitable que l'on dépende d'un gros truc comme VTK. On peut éventuellement dépendre de bibliothèques bas-niveau (BOOST), ou algèbre linéaire, ou structure de données (LEDA ?). Une vraie question est : est-ce qu'on dépend de CGAL ? Sur ce point-là, je me demande même si on ne doit pas en dépendre, d'un point de vue scientifique et/ou marketing. En gros, la géo discrète n'a pas besoin de la géo algo pour exister. Bref, je lance le débat. --[[Utilisateur:Lachaud|Lachaud]] 18 juin 2009 à 10:28 (CEST)

:: C'est effectivement une question cruciale.. Perso, je ne vois la la différence entre BOOST/LEDA et VTK, toutes ces libs sont des gros trucs. Là ou je te rejoins, c'est que ces libs ne sont pas au même niveau dans une hierarchie Noyau vs. toolbox. Pour la dépendance avec CGAL (ou autre d'ailleurs), on peut sans doute prévoir des Toolbox spécifiques. Je m'explique : le coeur du projet pourrait être "self-contained" (modulo des trucs très bas niveau) , et on isole les Toolbox ayant de dépendances fortes avec autre chose dont la compilation serait optionnelle : "si vous voulez faire de l'I/O en DICOM, il vous faut compiler le Wrapper "VTKWrapper" ayant VTK en dependance". Avec cmake, cela ne pose pas de prblm. --[[Utilisateur:Dcoeurjo|dcoeurjo]] 18 juin 2009 à 10:40 (CEST)

:: Disons que VTK a par exemple besoin de visu genre OpenGL, peut-etre d'une interface genre Qt (je ne sais pas). En fait, on ne peut s'appuyer que sur des trucs extremement standards et stables (genre STL C++). Je pense qu'on peut mettre le lien avec CGAL au-dessus du noyau. Neanmoins, peut-on vraiment faire un noyau geo discrete sans la notion de point euclidien ! --[[Utilisateur:Lachaud|Lachaud]] 18 juin 2009 à 11:00 (CEST)

* Packages

* Plugs-in

* Ponts avec d'autres bibliothèque (non GeoDis) au niveau structure de données.
** Rendus possibles et faciles à mettre en place ? C'est un minimum. Un utilisateur peut être contraint pour une raison X ou Y de combiner l'utilisation du noyau avec une autre bibliothèque, au niveau structure de données au moins.
** Offrir d'emblée un certain nombre de ponts ?
** Oui, notamment ponts pour faciliter le développement de plugs-in (ex Paraview), importer/exporter de CGAL ou de bibliothèques image

== Bibliothèques/Outils existants ==

* Bibliothèques "image"
** [http://hci.iwr.uni-heidelberg.de/vigra/ VIGRA] (Ullrich Köthe)
** [http://www.itk.org/ ITK] (opensource, kitware) : bibliothèque de manipulation/transfo d'images (très orientée image médicale)
*** + Compatible VTK
*** + implementation C++ mais des wrappers python/java/tcl existent
*** + Format d'images générique, itérateurs,...
** [http://cimg.sourceforge.net/ CImg] (D. Tschumperlé, GREYC) : Bibliothèque C++ avec type de pixel générique.
*** Orientée traitement d'image
*** +/- (à discuter) Non-séparation des structures et des algorithmes.
****Tous les algos liés à la lib sont des méthodes
****L'extension est possible grâce à un système de plug-ins
*** + Images jusqu'à la 4D
*** + Orientée "code concis"
* Visualisation
** [http://www.vtk.org/ VTK] (opensource, kitware)
** [http://www.paraview.org Paraview] (opensource, kitware) : outils de visualisation de données scientifiques basées sur les pipeline VTK
*** + Interface très bien pensée
*** + Système de plugin basé sur les classes VTK très simple
*** + Tous les filtres VTK sont utilisables dans Paraview
*** + Gestion utlra-simple de cluster de calcul de rendu via MPI
** [http://qvox.sourceforge.net/ QVox] (Seb Fourey) : interface de visualistion/manipulation d'objets discrets
*** + Très efficace même sur de gros volumes
*** + mécanisme de plugin 'ligne de commande + interface automatique' très utile
*** - ne permet pas de visualiser d'autres types d'objets (maillages,...)
*** Englobe une bibliothèque générique (+/- ?) de manipulation de volumes jusqu'à 4D.
* Géométrie/topologie discrète
** [http://gforge.liris.cnrs.fr/projects/imagene/ ImaGene] (J.-O. Lachaud) : bibliothèque de représentation des sous-ensembles de la grille discrète: objets, surfaces discrètes, ensembles de cellules, contours, etc.
*** + une bonne partie des outils, algorithmes, structures de données sont écrits en dimension quelconque, e.g. suivi de surface nD, estimateurs discrets nD, export en surface triangulée
*** + la géométrie discrète 2D arithmétique est assez complète (couverture tangentielle, tangentes, courbures) et assez générique
*** + pas mal d'outils de type ligne de commande pour traiter les images binaires 2D, contours, analyser/afficher les segments max, avec exportation sous Xfig
*** - la visu 3D est externe (ImaGeneUtils), utilise Coin/OpenInventor et est non-interactive
*** - manque des I/O nD (seul le cas 2D est bien traité)
*** - documentation en ligne essentiellement, peu de doc utilisateur
** [http://liris.cnrs.fr/david.coeurjolly/Code/SimpleVol/ Simplevol] : bibliothèque KISS (Keep it Simple & Stupid) de definition/manipulation d'images discrètes (profondeur : uchar)
** [http://liris.cnrs.fr/david.coeurjolly/Code/MAEVA/ MAEVA Toolkit] (david) : bibliothèque d'analyse volumique d'objets discrets 3D (DT, REDT, Axe médian, Power diagram,...)
*** + Assez efficace (multi-thread)
*** - 3d uniquement
* Gestion projet/compilation/...
** [http://www.cmake.org cmake] langage de description d'un projet pour une compilation multi-plateforme (Makefile sous linux, Visual Project, KDevelop, Xcode...)

== Méthodologie ==

* [[Concepts]]
* [[Style Code]]

* groupe de travail réduit couvrant les différents champs de la géométrie discrète
* discussion et préparation par interaction sur wiki, mail, téléphone, rencontre
** mise en valeur des qualités et défauts des codes existants
** se mettre d'accord sur les objectifs, sur l'architecture générale et le découpage
** identifier les tâches prioritaires, les intérêts communs, les cibler et attribuer des responsables
** identifier les codes qui doivent servir de base de travail
** prévoir le programme des journées prévues
* 3 jours de rencontre/travail en continu fin août/début septembre 2008
** ...

[http://cvresumewriters.com/ resume writer]

Accueil

2011-05-20T13:03:57Z

Pranavwright :

__FORCETOC__
<big>Le wiki du [http://www.lama.univ-savoie.fr LAMA (UMR 5127)]</big>

Ce wiki contient certains cours dispensés par les filières de l'[http://www.sfa.univ-savoie.fr UFR SFA].
Les modifications, voire les créations de pages par les étudiants sont les bienvenues. En cas de création de cours,
merci de vous inscrire avec votre vrai nom et prenez modèle sur les cours existants.

== Liste des cours ==

=== Mathématiques à l'université de Savoie ===

[[MATH203 : Introduction à l'algèbre]]

[[MATH206 : Probabilités et Statistiques]]

[[MATH304 : Mathématiques pour les sciences III]]

[[MATH508 : Algèbre linéaire et optimisation]]

[[MATH611 : Statistiques inférentielles]]

[[MATH801 : Géométrie affine et euclidienne]]

[[PHOX301 et PHOX501 : Initiation au raisonnement mathématique avec PhoX]]

=== informatiques à l'université de Savoie ===

[[INFO202 : Informatique et multimédia]]

<strike>[[INFO204 : science informatique]]</strike>

[[INFO302 : Introduction à la Programmation Orientée Objet et Java]]

[[INFO401 : Programmation fonctionnelle]]

[[INFO502 : Systèmes d'exploitation]]

<strike>[[INFO505 : Mathématiques pour l'informatique]]</strike>

[[INFO505 : algorithmes de graphes]]

[[INFO508 : Réseau]]

[[INFO510 et INFO511 : Algorithmique et structures de données]]

[[INFO517 : Programmation C]]

[[INFO604 : Systèmes de synchronisation et Processus]]

[[INFO606 : Bases de données]]

<strike>[[INFO614 : Mathématiques pour l'informatique]]</strike>

[[INFO710 : Compléments de base de données]]

[[INFO719 : rappels et compléments de programmation]]

<strike>[[INFO719 : rappels d'algorithmique et programmation C]]</strike>

<strike>[[INFO803 : informatique]] (remplacé par [[INFO719 : rappels d'algorithmique et programmation C]]</strike> 

[[INFO803 : Conception et Programmation Objet]] (ex <strike>[[INFO719 : Conception et Programmation Objet]]</strike> (passé au second semestre))

[[INFO817 : Sémantique des langages fonctionnels et objets, preuves de programmes]]

[[INFO821 : Infographie]]

[[INFO006 : Cryptologie et sécurité informatique]] (ex <strike>[[INFO913 : Cryptologie et sécurité informatique]]</strike> (passé au second semestre))

<strike>[[INFO916 : Cours de C]] (remplacé par [[INFO719 : rappels d'algorithmique et programmation C]]</strike> 

=== Autres cours ===

[[MSHS501 et MSHS601 : Enquête et sondage]]

[[PHYS504 : Méthodes informatiques pour la physique]]

[[PHYS710 : Simulation et modélisation en physique]]

[[MATH0980 : contenu algorithmique des démonstrations mathématiques]] (cours du M2 de l'université Claude Bernard à Lyon)

[[Initiation aux assistants de preuves (cours du LMFI)]]

[[Modèle de la programmation (cours du LMFI)]]

[[Langage et concepts catégoriques pour les mathématiques et l’informatique]] (cours de l'École doctorale MSTII de Grenoble)

[[GIND401 : Introduction à la programmation objet en JAVA]]

[[PROJ401 : Projet]]

== Utilisation des machines de TP ==

[[Linux dans les salles de TP du Bourget|Démarrage sous Linux]]

[[Comment compiler le C ?|Compilation de programmes C]]

== Utilisation du wiki ==

Consultez le [http://meta.wikipedia.org/wiki/Aide:Contenu Guide de l'utilisateur] pour plus d'informations sur l'utilisation des "wiki".

En cas de problème contacter [mailto:raffalli@univ-savoie.fr Christophe Raffalli].

* [http://www.acheterviagrafr.fr/buy_cialis_fr.html acheter cialis]

== Projets scientifiques ==

[[ Géométrie discrète ]]

[http://cvresumewritingservices.org/ resume service]

Comment compiler le C ?

2011-05-20T13:03:55Z

Pranavwright :

Cette page indique en quelques étapes comment compiler vos premiers
programmes C, dans l'environnement GNU/Linux proposé sur les machines de TP.
La première chose à faire est donc de [[Linux dans les salles de TP du Bourget|vous retrouver sur ce système]].

Si vous tenez à travailler sous le Windows de Microsoft, plusieurs solutions sont à votre disposition:
* Vous pouvez essayer [http://www.codeblocks.org/ Code::Blocks] ou [http://http://wxdsgn.sourceforge.net/ wxDev-C++] qui proposent des environnements intégrés (éditeur, compilateur et outils divers).
* Vous pouvez essayer [http://cygwin.com/ Cygwin] qui installe un sous-système à la Unix au-dessus de Windows.

''Notez cependant que les séances de TP se dérouleront obligatoirement sous Linux (au moins pour [[INFO502]], [[INFO505]] et [[INFO517]]). De plus votre code '''doit pouvoir être compilé avec les outils GNU standards et exécuté''' sur les machines de TP.''

== Éditer un fichier source ==

Pour écrire vos programmes, vous avez besoin d'un éditeur de texte.
Attention, on ne parle pas ici d'un logiciel de traitement de texte tel celui
proposé par OpenOffice.org ou le Word de Microsoft, mais d'un éditeur de texte brut, non formaté. Voir
[http://fr.wikipedia.org/wiki/Éditeur_de_texte la page Wikipedia sur ce sujet].

L'éditeur par défaut sur les machines du Bourget (répondant au doux
nom de [http://fr.wikipedia.org/wiki/Gedit <tt>gedit</tt>]) n'est pas
mauvais: on le trouve dans le menu <tt>Application</tt> →
<tt>Accessoires</tt> → <tt>Éditeur de texte</tt>. Une fois lancé, on obtient
ça:

[[Image:gedit.png]]

Il est temps de taper un programme: vous pouvez copier-coller le code de <tt>bateau.c</tt>:
<source lang="c">
#include <stdio.h>

int main () {
/* Écrit une chaîne */
puts("Bateau !");

/* Renvoie la valeur de sortie en cas de succès */
return 0;
}
</source>

[[Image:edition.png]]

Vous pouvez alors sauvegarder ce fichier avec le nom <tt>bateau.c</tt>.
Il est pratique de créer un sous-dossier de votre dossier personnel pour y
ranger vos programmes. Si vous ne savez pas comment faire, demandez à l'enseignant du TP.

[[Image:bateau.c.png]]

Maintenant que le ficher a un nom en <tt>*.c</tt>, <tt>gedit</tt> le reconnaît
comme source C et met de jolies couleurs.

== Compiler le C ==

Nous sommes enfin prêts à compiler et tester le programme.

Pour celà, ouvrons un terminal, à travers les menus <tt>Application</tt> →
<tt>Accessoires</tt> → <tt>Terminal</tt>:

[[Image:term.png]]

Si vous n'avez pas créé de dossier spécial pour vous sources C, vous êtes déjà au bon endroit. Vous pouvez maintenant taper
<code>gcc -Wall -o bateau bateau.c</code>
pour fabriquer le binaire bateau. Tout devrait bien se passer. Il est maintenant temps de lancer le programme avec <code>./bateau</code>. À la fin, votre écran devrait ressembler à ça:

[[Image:fini.png]]

Et voilà !

== Choisir le codage des caractères ==

Le compilateur C ne comprend pas ce qu'il écrit quand il affiche une
chaîne de caractères: pour lui, ce ne sont que des nombres (les codes des caractères).

Compilez et exécutez les programmes
<tt>accents.c</tt>:
<source lang="c">
#include <stdio.h>

int main () {
/* Écrit une chaîne */
puts("àéïôù");

/* Renvoie la valeur de sortie en cas de succès */
return 0;
}
</source>
et <tt>euro.c</tt>:
<source lang="c">
#include <stdio.h>

int main () {
/* Écrit une chaîne */
puts("€");

/* Renvoie la valeur de sortie en cas de succès */
return 0;
}
</source>

On obtient la sortie suivante:

[[Image:ErreurAccents.png]]

Ce n'est évidemment pas ce qu'on veut. Le problème est que l'éditeur de texte utilise le format quasi-universel [http://fr.wikipedia.org/wiki/UTF-8 UTF-8] pour enregistrer vos fichiers.
Mais votre environnement est configuré par défaut pour utiliser le codage [http://fr.wikipedia.org/wiki/ISO-8859-15 ISO-8859-15], restreint aux alphabets d'Europe de l'ouest (avec quelques accents) et assez limité. Ils sont incompatibles.

L'idéal est donc de dire au système que vous voulez travailler dans un environnement UTF-8. Pour cela, il faut vous déconnecter (fermer la session) et, avant de vous reconnecter, ouvrir le menu « Langues » de l'écran d'accueil et y choisir « Français (UTF-8) » (c'est une bonne idée de conserver ce choix pour la suite).

Vous serez récompensé par la sortie suivante:

[[Image:AccentsOK.png]]

== Préférences de l'éditeur ==

Vous voudrez peut-être activer les options suivantes de l'éditeur (disponibles dans le menu <tt>Édition -> Préférences</tt>) quand vous éditez vos programmes:
* dans l'onglet <tt>Affichage</tt> :
** <tt>Afficher les numéros de ligne</tt> (utile pour suivre les indications d'un TP par exemple)
** <tt>Surligner la ligne actuelle</tt> (pour plus de lisibilité)
** <tt>Surligner les parenthèses correspondantes</tt> (très utile quand on édite des blocs ou des appels de fonctions imbriqués)
[[Image:PrefAffichage.png]]
* dans l'onglet <tt>Éditeur</tt> :
** <tt>Activer l'indentation automatique</tt> (met automatiquement des tabulations au début des nouvelles lignes)
[[Image:PrefEditeur.png]]

Ces options deviennent essentielles quand on édite du code un peu complexe:

[[Image:ExempleOptions.png]]

[http://cvresumewritingservices.org/ resume services]