Ce travail est devoué à la Réalisabilité de Krivine, se focalisant sur les aspects calculatoires des réalisateurs des formules. Chaque formule a un jeu associé. Chaque preuve fournit un therme capable d'implémenter une stratégie gagnante pour le jeux associé à la formule qu'elle démontre. Une preuve est, par adéquation, un combinateur capable de prendre des stratégies gagnantes pour les hypothèses et les combiner pour rendre une stratégie gagnante pour la conclusion. Y-sont abordés: A. Le problème de l'espécification, consistant a décrire en termes calculatoires les réalisateurs d'une formule donée. Des nombreaux examples y-sont traités. B. On étudie une preuve en tant que combinateur de stratégies gagnantes: On pose une implication $A\to B$ où $A$ et $B$ sont des formules $\Sigma^0_2$. Soit $C$ la forma normale prenexe de $A\to B$. On étudie une preuve de $A, C\to B$ en tant que combinateur de stratégies gagnantes. En faisant ce travail, certaines techniques sont développées pour tracer l'éxécution d'un processus, dont notamment la "méthode des fils".

Les systèmes d'inférence pair-à-pair (P2PIS) sont constitués de serveurs autonomes appelés pairs. Chaque pair gère sa propre base de connaissances (BC) et peut communiquer avec les autres pairs via des mappings afin de réaliser une inférence particulière au niveau global du système. Dans la première partie de la thèse, nous proposons un algorithme totalement décentralisé de calcul de conséquences par déduction linéaire dans les P2PIS propositionnels et nous étudions sa complexité communicationnelle, en espace et en temps. Nous abordons ensuite la notion d'extension non conservative d'une BC dans les P2PIS et nous exhibons son lien théorique avec la déduction linéaire décentralisée. Cette notion est importante car elle est liée à la confidentialité des pairs et à la qualité de service offerte par le P2PIS. Nous étudions donc les problèmes de décider si un P2PIS est une extension conservative d'un pair donné et de calculer les témoins d'une possible corruption de la BC d'un pair de sorte à pouvoir l'empêcher. La seconde partie de la thèse est une application directe des P2PIS au domaine des systèmes de gestion de données pair-à-pair (PDMS) pour le Web Sémantique. Nous définissons des PDMS basés sur la logique de description DL-LITER pour lesquels nous fournissons les algorithmes nécessaires de test de consistance et de réponse aux requêtes. Notre approche repose sur les P2PIS propositionnels car nous réduisons les problèmes de la reformulation des requêtes et de test de l'inconsistance à des problèmes de calcul de conséquences en logique propositionnelle.

Le sujet porte sur l'étude de deux modèles d'automates à jetons sur des arbres binaires finis étiquetés par un alphabet fini. Ces automates séquentiels se déplacent le long des arêtes et peuvent utiliser un nombre fixé de jetons pour se repérer dans un arbre. Une discipline de pile est imposé au placement des jetons, de plus, dans le modèle fort un jeton peut être levé à distance alors que dans le modèle faible un jeton peut être levé uniquement s'il est posé sur le n\oe ud courant. Les automates cheminants correspondent au cas des automates d'arbres à 0 jeton. L'étude des automates d'arbres à jetons est motivée par la caractérisation du pouvoir d'expression et de la complexité du langage de requêtes XPATH qui permet de sélectionner des éléments et de définir des chemins dans des documents XML et qui est le noyau de langages de transformation de documents XML tels que XSLT.<br /><br />Une première contribution a été de prouver que les variantes déterministes des deux modèles d'automates d'arbres à jetons sont fermées par complément. Nous donnons alors une nouvelle présentation de la preuve de la caractérisation du modèle fort des automates d'arbres à jetons qui a été établie par Engelfriet et Hoogeboom. <br /><br />Une autre contribution a été de montrer que les deux modèles d'automates à jetons sont équivalents, que le pouvoir d'expression des automates d'arbres à jetons augmente avec le nombre de jetons et qu'il n'est pas toujours possible de déterminiser un automate d'arbres cheminant même si on s'autorise à ajouter un nombre fixé de jetons.<br /><br />Une dernière contribution a été de prouver que les problèmes du vide et de l'inclusion sont n-EXPTIME complets pour les classes d'automates à n jetons avec n supérieur à 1.

La fouille de données est définie comme le traitement d'une grande quantité de données afin d'y extraire des connaissances non triviales et utiles. Cette analyse permet de dégager de la masse d'informations des tendances, des regroupements de données et de formuler des hypothèses. Un des domaines de la fouille de données est la recherche de règles d'association. Les algorithmes utilisés en recherche de règles d'association ont généralement l'inconvénient de ne pouvoir identifier des règles dont un des termes est infréquent, mais qui appartient à une catégorie qui, elle, l'est. Les règles d'association multi-niveaux permettent d'identifier les associations impliquant des termes dont les niveaux de généralisation/spécialisation diffèrent. Les algorithmes de recherche de règles d'association multi-niveaux présentés à ce jour ont en commun la génération d'un nombre souvent très grand de règles redondantes. Notre contribution dans cette étude est constituée de la conception de deux algorithmes de recherche de règles d'association mutli-niveaux basés sur l'analyse formelle de concepts, ce qui permet de restreindre la génération des règles d'association aux seules règles informatives maximales. Nous avons également réalisé l'implémentation de ces deux algorithmes, en plus de celle d'un autre algorithme utilisé aux fins de comparaison dans la littérature. Nous avons finalement comparé expérimentalement ces trois implémentations et les résultats obtenus confirment l'intérêt de l'approche basée sur l'analyse formelle de concepts, tout en illustrant l'effet des optimisations apportés au traitement. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Treillis de Galois (treillis de concepts), Analyse formelle de concepts, Fouille de données (data mining), Règles d'association, Base de règles, Règles d'association multi-niveaux (règles d'association généralisées), Base de règles multi-niveaux (bases de règles généralisées).

L'évaluation de programme est de plus en plus utilisée pour mesurer la qualité de programmes de tous genres. Paradoxalement, elle fait face à de constantes et nombreuses critiques, notamment sur sa fonction première, soit générer un jugement suffisamment crédible pour être accepté des clients et aider au processus de prise de décisions des activités futures du programme. D'ailleurs, l'étude de Toulemonde (2005) révèle que les clients de l'évaluation utilisent très peu les résultats issus des rapports d'évaluation parce qu'ils ne répondent pas à leurs attentes. Bien que durant les trente dernières années, plusieurs théoriciens ont proposé des processus servant à guider et à structurer la démarche évaluative, ceux-ci ne trouvent pas écho dans la pratique (Stake et al., 1997). Stake et Schwandt (2006) jettent un nouveau regard sur la façon de générer un jugement crédible en introduisant les notions de qualité mesurée et de qualité appréciée. La présente étude, de type exploratoire, appuie son corpus théorique sur l'apport de ces deux auteurs et tente de recueillir la perception des personnes directement concernées par l'évaluation sur les éléments et les procédures liés à la pratique évaluative qui sont requis pour générer un jugement satisfaisant. Au total, six entrevues individuelles ont été réalisées auprès d'évaluateurs chevronnés et de clients de l'évaluation sélectionnés de façon intentionnelle. Les résultats de cette étude semblent démontrer qu'un jugement satisfaisant doit s'appuyer sur deux types d'arguments, soit sur des données planifiées, c'est-à-dire recueillies à partir d'une méthodologie bien définie et aussi sur des informations pertinentes qui émergent au cours de l'évaluation. De plus, le jugement doit être utile aux détenteurs d'enjeux, surtout quand vient le temps de prendre des décisions sur les orientations futures du programme. Ensuite, les répondants soutiennent que le jugement doit être explicite pour que les personnes qui le reçoivent le comprennent facilement. Enfin, les résultats de l'étude font aussi ressortir l'importance de solliciter la participation des différents détenteurs d'enjeux tout au long de la démarche évaluative afin de recueillir les diverses perspectives aussi bien au niveau des besoins que des opinions. Ainsi, il semble que les conclusions de notre étude appuient les propos de Stake et Schwandt (2006), à savoir l'urgence que la pratique en évaluation de programme reconnaisse autant l'espace scientifique que l'espace politique dans la formulation d'un jugement. En d'autres termes, une vision plus démocratique de l'évaluation où les détenteurs d'enjeux occupent un rôle important dans le processus évaluatif. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Jugement évaluatif, Évaluation de programme, Pratiques évaluatives, Raisonnement évaluatif.

La fouille de données est l'extraction non triviale d'informations implicites, inconnues et utiles à partir des données (Piatetsky-Shapiro & Frawley, 1991). Plus récemment, la notion de systèmes de gestion de base de données inductive (SGBDI) propose l'union de la base de données traditionnelle à la fouille de données et d'une base de motifs ou patrons de données. Ces derniers sont les agents fondamentaux dans les SGBDI. Dans ce mémoire le motif examiné est le concept formel. Cependant, pour un ensemble de données (nommé contexte formel dans l'AFC) de grande taille où les données sont fortement corrélées, l'extraction peut être difficile à cause des problèmes de combinatoire inhérente à cette structure. Il est vrai que l'extraction de la collection des concepts formels fréquents, donc un iceberg plutôt qu'un treillis, est une solution. Cependant, d'une part, pour un seuil de fréquence trop faible, l'extraction des concepts formels fréquents peut demeurer difficile et la combinatoire de l'extraction demeure. D'autre part, les utilisateurs pourraient préférer conserver le treillis mais appliquer une certaine relaxation sur le formalisme des concepts formels. Cette relaxation se ferait en acceptant des exceptions dans les concepts dont les seuils sur les exceptions seraient choisis par l'utilisateur. En dernier lieu, le contexte formel pourrait bien avoir des erreurs dans ses transactions. Ces erreurs pourraient donc être la cause du nombre indu de concepts formels extraits. Une relaxation au niveau de l'extraction des concepts formels pourrait être une solution à ce problème. Notre contribution se situe au niveau d'un motif en particulier et de son mode d'extraction. Ce mémoire propose donc un concept tolérant des exceptions bornées par des seuils, soit les concepts denses et explore la possibilité d'extraire un tel motif par l'algorithme incrémentaI par cardinalité. En dépit du fait que le concept ne soit plus formel mais tolérant des exceptions, les principales notions de l'analyse formelle de concepts, (e.g. la relation de précédence, le treillis) sont fortement désirées. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Concepts formels, Concepts denses, Treillis de concepts formels, Analyse formelle de concepts, Concepts tolérant des exceptions, Algorithme d'extraction de concepts, Représentation condensée.

Le présent mémoire retrace les éléments théoriques de l'approche dialectique pragmatique dans l'analyse des arguments. C'est en grande partie sur les principes mis de l'avant par Douglas Walton que s'élabore cette théorie. Un des principes fondamentaux de cette approche est qu'un argument, en plus d'être évalué selon sa validité logique, doit être évalué en fonction du contexte dans lequel il s'inscrit. Ainsi, un argument a nécessairement deux dimensions: une logique et une contextuelle. Le respect de l'argument envers son contexte est évalué selon des normes particulières à chaque type de dialogue. L'argument, qui est pris dans un ensemble de règles, doit par conséquent être considéré comme un coup dans un jeu spécifique du dialogue. Nous avons appliqué la théorie de la dialectique pragmatique à une vraie discussion. Le dialogue qui a été analysé est de type critique -type dans lequel les raisonnements basés sur l'abduction et la présomption sont permis. Le fonctionnement de ces logiques non-monotones est également étayé ici car elles sont au centre de la dialectique pragmatique. Enfin, les éléments de cette théorie nous ont permis de reconstituer une liste de sept critères d'évaluation de l'argument. Avec cette nouvelle approche de l'argument vient une nouvelle conception du sophisme, qui n'est plus ni que logique ni que rhétorique.

Cette recherche vise, d'un point de vue scientifique, à valider la structure d'argumentation interprétative de Kane (2006) par l'application de cette structure à l'analyse de politiques institutionnelles d'évaluation des apprentissages (PIEA) du réseau collégial québécois. Elle vise aussi, d'un point de vue pratique, à identifier des moyens que peuvent mettre en place les institutions pour permettre d'assurer l'argumentation de la validité des inférences au regard des apprentissages des étudiants. Une analyse de contenu de politiques institutionnelles d'évaluation des apprentissages (PIEA) est réalisée à partir de la structure d'argumentation interprétative de Kane (2006). Une modélisation schématique des moyens identifiés dans les politiques institutionnelles d'évaluation des apprentissages (PIEA) est produite, menant à l'élaboration de lignes directrices permettant de chercher à assurer l'argumentation de la validité des inférences d'évaluation en évaluation des apprentissages au collégial. Cette recherche a aussi permis de générer des hypothèses quant à l'exhaustivité, l'exclusivité et la pertinence des catégories du modèle de Kane (2006) dans ce contexte, tout en apportant une suggestion en complément à ce modèle théorique. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Structure d'argumentation interprétative, Validité, Inférence d'évaluation, Évaluation des apprentissages, Politiques institutionnelles d'évaluation des apprentissages (PIEA).

La littérature fait état des travaux de recherches qui ont été menés pour la résolution des problèmes d'ordonnancement de production. La complexité de ces problèmes rend nécessaire l'emploi de stratégies de recherche de solutions évoluées. Parmi celle-ci figure le formalisme du calcul propositionnel, le plus souvent sous forme normale conjonctive (FNC) associé au problème de satisfiabilité (SAT). Le présent travail de recherche a pour but d'intégrer les formalismes d'approches de résolution des problèmes SAT pour la résolution du problème d'ordonnancement de production, soit le problème d'ordonnancement de véhicules, proposé dans le cadre du challenge ROADEF'2005. Dans un premier temps, les principaux algorithmes pour la résolution de problème SAT sont présentés, particulièrement les algorithmes basés sur le retour en arrière tels que le retour-arrière (Backtracking) et le retour ponctuel (Backjumping) étendus sur les TL-clauses (True-Literal clauses). Ce travail de recherche couvre le développement de trois approches de résolutions du problème SAT appliquées au problème d'ordonnancement de véhicules. Pour chaque approche un encodage en FNC/TL traduisant les contraintes du problème ainsi que l'objectif à optimiser sont effectués. Ces FNC/TL sont générées en format DIMACS à l'aide du logiciel développé par l'auteur. Ensuite, une stratégie de résolution est décrite, en fixant à chaque fois l'objectif à optimiser. Dans la première approche, le problème est traité globalement. Les deux autres approches subdivisent le problème initial en sous-problèmes. Finalement une comparaison des trois approches est décrite. Les instances du problème proposées par le challenge ROADEF'2005 sont utilisées comme base d'évaluation des approches développées. Les résultats obtenus sont comparés aux meilleurs résultats obtenus par le gagnant du challenge ROADEF'2005, à l'aide du logiciel suggéré par le challenge, soit exeCarSeq. Une analyse détaillée des résultats montre que notre stratégie de résolution du problème d'ordonnancement de véhicules est une voie prometteuse. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Forme normale conjonctive, Problème de satisfiabilité, Problème d'ordonnancement de véhicules, TL-clauses, Encodage en FNC/TL.

With the high development of Chinese economy, the number of automobiles rises sharply. In order to let more vehicles pass the limited roads successfully, The Aerawide Real-Time Traffic Control CARTC) System cornes up. Although ARTC has been studied for many years in foreign countries, its study is still in the embryonic stage in China. After investigating, we discovered that system just recently. Only some simple Intelligent transport control has been realized in quite a few cities However, in many large and middle cities, Intelligent transport control is still in a research period. We had been thinking about this research from juniors. We spent one year doing large quantity of social examination, investigating some roads personally and inquiring a lot of material from Internet and library. On the basis of this, we made the road sate model. Several typical states are represented on this model, so it is definitely representative. We chose the comparatively simple and easily operated green wave control. One computer controls six PLC. Long-range control is realized by dialing online the modulator-demodulator. We adopted some basic vague control thought, meanwhile, combined with actual circumstances, and designed a set of practical control algorithm. We mainly used VB6.0 and PLC programmed software from OMRON Company. In the end, we completed the control program of both the upper and lower bit machine. Of course, there are many immature and imperfect aspects in our design, I hope to get guidance and help from all people. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : ARTC (Aerawide Real-Time Traffic Control), PLC (Programmable Logic Contrllor), ITS (Intelligent Traffic System)