Utilisateur:Claudeh5/transit2

L'algorithme de Ford-Dantzig résout un problème de plus court chemin. Il sert à trouver un chemin optimal (le plus court ou bien le plus long) entre deux sommets d'un graphe orienté. Le graphe peut être avec ou sans circuit et les poids (longueur) peuvent être positifs ou négatifs (contrairement à l'algorithme de Dijkstra). L'étude portera ici sur le principe du plus court chemin car c'est le plus utilisé.

Entrées - Sorties

Entrées :

Tableau G_SUCC
Tableau G_ANT

Sortie :

Un système de chemin représenté par un arbre qui peut être appelé arbre final par exemple.

Structure de donnée

Intéressons nous d'abord de savoir comment on va organiser toutes nos données.

Voici les différents éléments qui vont composer notre algorithme :

Tableau de listes chainées - G_SUCC (Contient les successeurs des différents sommets)
Tableau de listes chainées - G_ANT (Contient les antécédents des différents sommets)
Un point d'origine x0 (Bloc mémoire stockant un entier)
Tableau - Long (Contient la longueur d'un plus court chemin de x0 à x)
Tableau - ANT (Contient les antécédents dans l'arbre final)
Tableau de liste chainées - SUCC (Contient les successeurs dans l'arbre final)

Principe de l'algorithme

On construit un arbre qui atteint tous les sommets du graphe depuis x0.
On améliore au mieux cet arbre pour avoir la meilleure solution possible.

Amélioration de l'arbre

Soit d(a,b) la longueur de l'arc entre les sommets F et G. Si entre deux points F et G : Long(F) + d(F,G) < Long(G) alors le chemin n'est pas optimal. Dans ce cas :

On modifie l'antécédent de G par F (au lieu de J par exemple).
On modifie les successeurs de J (on enlève G) et F (on ajoute G). On remarque que G transite mais est toujours atteint.

Algorithme

1. Initialisation

    * Construire un arbre dont la racine est x0 qui atteint tous les sommets.
    * Calculer la longueur Long(x) associée à tout x accessible. 
     (Mettre une valeur d'erreur autrement, par exemple +inf)

2. Corps

tant que !cdt_arret faire
    chercher un arc plus court tel que Long(y) > Long(x) + d(x,y)
    /* ---- principe de correction successive ---- */ 
    si arc(x,y) n'existe pas alors 
         cdt_arret
    sinon
         si y est entre x0 et x dans l'arbre alors
              cdt_arret
         sinon
              modifier l'antécédent de y dans l'arbre par x (Cf:3.1)
              ajuster Long(y) pour les sommets atteignables depuis y dans l'arbre
         fin si
    fin si
fin tant que

Le problème est-il résolu ?

Il faut voir avec du recul l'algorithme donné précédemment, on a deux possibilités de finir l'algorithme :

Le stop d'échec

Ce stop (cdt_arret) est réalisé par le test si y est entre x0 et x dans l'arbre alors. En effet, ici on obtient un circuit de longueur négative. Le problème ne convient donc pas à cet algorithme.

Le stop de réussite

Ce stop (cdt_arret) est réalisé par le test si arc(x,y) n'existe pas alors. En effet, ici ce test correspond à la non existence d'un chemin plus court : Long(y) > Long(x) + d(x,y) ne peut être trouvé.

Liens internes

Sources

Cours dispensé à l'Institut supérieur d'informatique, de modélisation et de leurs applications (ISIMA)

{{Portail|mathématiques}} [[Catégorie:Algorithme de la théorie des graphes|Dantzig-Ford]] [[Catégorie:Algorithme de recherche]]

==========================================================

En mathématiques, on appelle suite implicite une suite définie comme solution d'une équation de la forme $f_{n}(x)=0$ . À défaut de pouvoir trouver une expression explicite de la suite, on peut déterminer son comportement asymptotique.

Méthode pour étudier une suite implicite

L'étude d'une suite implicite se fait en 3 étapes :

Trouver un encadrement de la suite.
En déduire un équivalent : on obtient un développement asymptotique à un terme.
Réinjecter autant de fois que nécessaire le développement de la suite dans l'équation pour augmenter le nombre de termes.

Nous allons appliquer cette méthode dans un exemple.

Un exemple de suite implicite

On note pour tout $n\in \mathbb {N}$ , $x_{n}$ l'unique solution positive de l'équation $x^{n}+nx-1=0$ . On va chercher un développement asymptotique de $x_{n}$ ,.

Encadrement de la suite

Il est aisé de montrer que la fonction $f_{n}:x\mapsto x^{n}+nx-1$ est strictement croissante sur $\mathbb {R} _{+}^{*}$ . On remarque d'autre part que $f_{n}\left({\frac {1}{n}}\right)>0$ , et que $f_{n}\left({\frac {1}{n+1}}\right)<0$ .

Cela nous donne donc un encadrement de la suite : ${\frac {1}{n+1}}<x_{n}<{\frac {1}{n}}$

Équivalent de la suite

L'encadrement nous permet de dire que $x_{n}$ est équivalent à ${\frac {1}{n}}$ . Autrement dit, on obtient un développement asymptotique à un terme : $x_{n}={\frac {1}{n}}+\circ \left({\frac {1}{n}}\right)$ .

Développement asymptotique à deux termes

Pour montrer le principe, on ne va réinjecter qu'une fois dans l'équation, mais la méthode peut se répéter indéfiniment, la limite étant uniquement calculatoire. Pour ne pas avoir à manipuler de symbole $\circ$ , on pose $y_{n}=x_{n}-{\frac {1}{n}}$ . On réinjecte dans l'équation : $x_{n}^{n}+n\left({\frac {1}{n}}+y_{n}\right)-1=0$ . Après simplifications, on peut écrire : $y_{n}=-{\frac {x_{n}^{n}}{n}}$ .

De plus, $(nx_{n})^{n}=\exp(n\ln(x_{n}))$ et $n\ln(nx_{n})\sim n(nx_{n}-1)=-nx_{n}^{n}\to 0$ . Ainsi, ${\frac {x_{n}^{n}}{(1/n)^{n}}}\to 1$ .

On en déduit donc que $y_{n}\sim -{\frac {1}{n^{n+1}}}$ , cela complète ainsi le développement asymptotique de notre suite pour obtenir finalement le développement asymptotique à deux termes recherché :

Développement asymptotique à deux termes — On obtient ainsi ${}\quad x_{n}={\frac {1}{n}}-{\frac {1}{n^{n+1}}}+\circ \left({\frac {1}{n^{n+1}}}\right)$

Articles connexes

{{Portail|Analyse}} [[Catégorie:Analyse réelle]]

=======================================================================================================================

Djamil AÏSSANI est Mathématicien et Homme de Culture Algérien.

Biographie

Spécialiste des Probabilités, de la Recherche Opérationnelle et de l’Évaluation de Performance. Ses recherches concernent les Sciences exactes et technologiques (Mathématique et Informatique, Mathématiques appliquées à la science de l’ingénieur, Mathématiques industrielles–cf. http://www.lamos.org). Cependant, ce sont ses travaux sur l’histoire des sciences (Maghreb et Méditerranée), sur les méthodes d’analyse (Histoire anthropologique, intellectuelle et livresque du Maghreb) et ses rapports avec le monde artistique (Théâtre, Iconographie, Musique) qui l’ont fait connaître du grand public (cf. http://www.gehimab.org). Son engagement pour la sauvegarde du patrimoine matériel et immatériel de l’Algérie (lors de la décennie noire), et particulièrement de la Kabylie, a fait l’objet d’analyses scientifiques. Une thèse de Doctorat, intitulée : Le Groupe d’Études sur l’Histoire des Mathématiques à Béjaia (GEHIMAB) : une association indépendante à la recherche du patrimoine d’une ville et de sa province dans l’Algérie d’aujourd’hui, dirigée par Fanny Colonna, a été soutenue en 2006 à l’E.H.E.S.S. Paris (cf. M.A. Hadibi, Revue Insaniyat). Citons également les articles d’anthropologues et de journalistes chevronnés (Judith Scheele, Atilio Gaudio, Tassadit Yacine, Ghania Mouffok, Chawki Amari,…). Le 10 juillet dernier, un article de la philosophe Fadela Hebbadj sous le titre « Histoire et Sens au Maghreb », a fait la une du Journal Médiapart (Paris).

Notes et Références

[1] Ghania Mouffok, Le hasard et l’histoire ou une utopie en construction : portrait de Djamil Aïssani. In the Book : « Le Patrimoine de l’Eau en Algérie : Mémoire et Permanence », AREA–Ed [Barzak] Ed. , Alger, 2012, pp. 114–119. (ISBN 978-9931-325-20-8).

[2] Fanny Colonna, M.A. Hadibi, GEHIMAB : une association indépendante à la recherche du patrimoine d’une ville et de sa province dans l’Algérie d’Aujourd’hui. Thèse de Doctorat en Anthropologie, E.H.E.S.S., Paris, 2006 (C.R. dans la Revue Insaniyat n° 39–40, CRASC Ed., 2008, pp. d 155–164.

[3] Chawki Amari, L’Association GEHIMAB des mathématiques au secours du patrimoine. Et « Découvrir–Toudja et Béjaia, histoire d’eaux », El Watan, 21 mai 2010, p. 16.

[4] Fadela Hebbadj, Histoire et Sens au Maghreb, Journal Médiapart (France), la une du 11 juillet 2013.

[5] Judith Scheele, Recycling baraka : knowledge, politics and religion in contemporary Algeria. In « Comparative Studies in Society and History », The Cambridge Journal, Vol. 49, Issue 2, Avril 2007, pp. 304–328.

[6] Interview « s’impliquer et travailler », In l’Hebdomadaire « Université Info » n° 61, Alger (Bab Ezzouar), Octobre 1997, pp. 5-6.

[7] Soufi Berrezk-Allah, Les échanges intellectuels Béjaia–Tlemcen : une approche artistique innovante et des faits historico-culturels inédits » suivi de « L’esprit de Mashdaly ravive la séculaire Médersa Ya`coubiyya ».Revue El-Djawhara, n° 13, Octobre 2011, pp. 10–15 et 20–24.

[8] Samir Hadj Allaoua, Deux décennies de lumière. In El Watan n° 6740 du 15 décembre 2012, pp.20.

Références connexes

[1] M.A. Hadibi, Les mathématiciens et le patrimoine local : usages et stratégie : le cas du Groupe d’Études et de Recherche sur l’Histoire des Mathématiques à Bougie. Séminaire d’Aix-Marseille Iremam (Salem Chaker et all.), Juin 2013.

[2] CFI (Canal France International), « Avec le Professeur Djamil Aïssani ». In « Béjaia–Tourisme et Développement durable, les facteurs de rapprochement entre les peuples ». Dossier Journalistique, COPEAM Ed., 2008, pp. 4–9.

[3] Judith Scheele, Manuscript conservation in contemporary Algeria. In the Book « The Trans–Saharan Book Trade–Manuscript Culture, Arabic Literacy and Intellectual History in Muslim Africa », Brill Ed., 2010, pp. 300–309. E- (ISBN 978-9004-1936-11).

[4] Fadela Hebbadj, Le cheminement passionnant d’un mathématicien nommé Pr Djamil AÏSSANI, Journal La Voix de l’Oranie du 17 juillet 2013.

[5] Interview «Pour faire une recherche sérieuse, il faut des moyens », In Journal en ligne « Béjaia Aujourd’hui », Novembre 2012.

[6] Tarek Meyal, Groupe d’Études et de Recherche sur l’Histoire des Mathématiques à Béjaia : célébration du 20e anniversaire. In Le Courrier d’Algérie n° 2673 du 17 décembre 2012, pp. 10. 128.

[7] Paul Gardes and Ahmed Djebbar, References of Djamil Aïssani. In the Book :”Mathematics in Africa History and Cultures : an Annoted Bibliography”. Africa Mathematical Union Ed., South Africa, 2007, pp. 28–33. (ISBN 978-1-4303-1537-7).

[8] Monther Ben Milad, La Galerie de Peinture et des Arts Graphiques Emile Aubry de Béjaia. Revue : « Les Cahiers de la Peinture », n° 354, Paris, 2003, pp. 16–17.

Publications

Mathématiques. Voir dans les bases de données MR (Mathematical Reviews) ou bien (Zentralblatt für Mathematik)
Informatique (Évaluation de Performance). Voir dans la base de données DBLP.
Mathématiques appliquées à la science de l’ingénieur. Vori dans la base de données SCOPUS ou bien Knowledge of Science.
Mathématiques industrielles. Voir sur le site (http://www.lamos.org/documen2012/FORUM_ENTREPRISES_PUBLICATIONS2010.pdf ) ou bien sur le site (http://www.univ-bejaia.dz/documents/labo/ FORUM_ENTREPRISES_PUBLICATIONS2010.pdf)
Méthodes d’Analyse. Voir dans la base de données International African Bibliography. (ISSN 1865-9640).

Autres activités :

- Production d’expositions ; - Organisation de Colloques ; - Fondation de Musées ; - Participation à la production de pièces de Théâtre

Quelques ouvrages récents

[1] Scheele Judith et Aïssani D., Monographie de la Commune Mixte de Sidi Aïch de Auguste Veller (1888), Ibis Press Edition, Paris, 2004 . (ISBN 2-910728 -45-5).

[2] Aïssani D., Lobrano G. et Sid Ahmed A., Acteurs Locaux et Patrimoine Immatériel : le rôle des villes historiques de la Méditerranée, ISPROM (Rome)/PUBLISUD (Paris) Editions, 2004. (ISBN 2-86600-987-8).

[3] Aïssani D. et Hachi S., Béjaia, Centre de Transmission du Savoir, C.N.R.P.A.H. Alger Éditions, Nouvelle Série n° 4, 2008, 188 pages, (ISBN 978-9961-716-23-6) (dépôt légal 2279-2008).

[4] Aïssani D. et Mechehed D.E., Manuscrits de Kabylie : Catalogue de Collection Ulahbib, 2e édition, Nouvelle série n° 4 : C.N.R.P.A.H. Ed., Alger, 2010, 245 pages. (ISBN 978-9961-716-38-0).

[5] Aïssani D. et Djehiche M., Les Echanges Intellectuels Béjaia–Tlemcen, Ministère de la Culture Ed., Décembre 2012, 172 pages. (ISBN 978- 9961-9981-8-2). (dépôt légal: 4176–2011)

[6] Aïssani D., Les Rapports Béjaia–Tlemcen et la Tradition Scientifique du Maghreb, Aglaë Ed., Alger, 2012, 160 pages. (ISBN 978-9961-9869-9-8). (dépôt légal: 15–2012).

[7] Aïssani D. et Djehiche M., Les Manuscrits Scientifiques du Maghreb, Département Expositions Ed., Ministère de la Culture, Tlemcen/Alger, Août 2012, 165 pages. (ISBN 978-9931-361-06-0).

[8] Ben Naoum A. et Aïssani D., « Histoire et Sens : Idles, Adekker d Cena n Lexwan », CNRPAH Ed., Nouvelle série n° 17, 500 pages. (ISBN 978 - 9961-716-54-0).

[9] Aïssani D. et Djehiche M., Al Mubadalat al-Fikriya ma Bayna Bijaya wa Tilimsan, Livre d’Art, Département Expositions Ed., Ministère de la Culture, Tlemcen/Alger, Janvier 2013, 150 pages. (ISBN 978-9961- 9981-9-9). (en arabe)

[10] Aïssani D. et Djehiche M., Al Makhtutat al-`Ilmiyya lil Maghrib, Département Expositions Ed., Ministère de la Culture, Tlemcen/Alger, Février 2013, 165 pages. (ISBN 978-9931-361-06-0). (en arabe)

Liens

{{Portail|Algérie| mathématiques}} {{DEFAULTSORT:Aissani, djamel}} [[Catégorie:Mathématicien algérien]]