La programmation par contraintes est un paradigme de résolution des problèmes combinatoires sur lequel ont été bâtis des outils génériques de résolution, des solveurs. De nombreuses recherches sont menées pour élargir le champ d'application de ces outils µa des problèmes dynamiques et sur-contraints. Un axe prometteur s'appuie sur la notion d'explications. Les explications constituent une trace explicite du comportement du solveur et ont été initialement introduites pour améliorer les algorithmes de recherche arborescente. Depuis ce jour, elles ont ouvert la voie à des méthodes d'exploration plus intelligentes (mais aussi plus coûteuses) de l'espace de recherche. Cette thèse porte sur l'élaboration d'algorithmes de résolution s'appuyant sur la notion d'explications et les étudie sur des problèmes autant académiques qu'industriels. D'une part, nous examinons l'intérêt des explications dans le cadre de techniques génériques de décomposition. La mise au point d'un tel algorithme dans le contexte d'ordonnancement temps réel a montré la souplesse de la technique pour permettre la coopération de méthodes analytiques pointues avec un solveur de contraintes. D'autre part, nous montrons que le réseau d'explication constitue une information particulièrement pertinente pour révéler à un utilisateur les structures ou relations entretenues par différents éléments (variables/contraintes) du problème. Cette information, également exploitable dynamiquement par le solveur est un pas supplémentaire vers des approches de résolution génériques. Enfin, les explications ont été jusqu'ici très utilisées dans un cadre rétrospectif et pourraient l'être davantage dans un cadre prospectif (à l'image de leur exploitation par la communauté SAT). Nous revenons ainsi dans cette thèse sur des techniques de nogoods recording dans le cadre du problème de MOSP (Minimum Open Stack Problem).

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

La programmation par contraintes est souvent décrite, utopiquement, comme un paradigme déclaratif dans lequel l’utilisateur décrit son problème et le solveur le résout. Bien entendu, la réalité des solveurs de contraintes est plus complexe, et les besoins de personnalisation des techniques de modélisation et de résolution évoluent avec le degré d’expertise des utilisateurs. Cette thèse porte sur l’enrichissement de l’arsenal des techniques disponibles dans les solveurs de contraintes. D’une part, nous étudions la contribution d’un système d’explications à l’exploration de l’espace de recherche, dans le cadre spécifique d’une recherche locale. Deux heuristiques de voisinages génériques exploitant singulièrement les explications sont décrites. La première se base sur la difficulté de réparer une solution partiellement détruite, la seconde repose sur la nature non-optimale de la solution courante. Ces heuristiques mettent à jour la structure interne des problèmes traités pour construire des voisins de bonne qualité pour une recherche à voisinage large. Elles sont complémentaires d’autres heuristiques de voisinages génériques, avec lesquels elles peuvent être combinées efficacement. De plus, nous proposons de rendre le système d’explications paresseux afin d’en minimiser l’empreinte. D’autre part, nous effectuons un état des lieux des savoir-faire relatifs aux moteurs de propagation pour les solveurs de contraintes. Ces données sont exploitées opérationnellement à travers un langage dédié qui permet de personnaliser la propagation au sein d’un solveur, en fournissant des structures d’implémentation et en définissant des points de contrôle dans le solveur. Ce langage offre des concepts de haut niveau permettant à l’utilisateur d’ignorer les détails de mise en œuvre du solveur, tout en conservant un bon niveau de flexibilité et certaines garanties. Il permet l’expression de schémas de propagation spécifiques à la structure interne de chaque problème. La mise en œuvre et les expérimentations ont été effectués dans le solveur de contraintes Choco. Cette thèse a donné lieu à une nouvelle version de l’outil globalement plus efficace et nativement expliqué. / Constraint programming is often described, idealistically, as a declarative paradigm in which the user describes the problem and the solver solves it. Obviously, the reality of constraint solvers is more complex, and the needs in customization of modeling and solving techniques change with the level of expertise of users. This thesis focuses on enriching the arsenal of available techniques in constraint solvers. On the one hand, we study the contribution of an explanation system to the exploration of the search space in the specific context of a local search. Two generic neighborhood heuristics which exploit explanations singularly are described. The first one is based on the difficulty of repairing a partially destroyed solution, the second one is based on the non-optimal nature of the current solution. These heuristics discover the internal structure of the problems to build good neighbors for large neighborhood search. They are complementary to other generic neighborhood heuristics, with which they can be combined effectively. In addition, we propose to make the explanation system lazy in order to minimize its footprint. On the other hand, we undertake an inventory of know-how relative to propagation engines of constraint solvers. These data are used operationally through a domain specific language that allows users to customize the propagation schema, providing implementation structures and defining check points within the solver. This language offershigh-level concepts that allow the user to ignore the implementation details, while maintaining a good level of flexibility and some guarantees. It allows the expression of propagation schemas specific to the internal structure of each problem solved. Implementation and experiments were carried out in the Choco constraint solver, developed in this thesis. This has resulted in a new version of the overall effectiveness and natively explained tool.

Made available in DSpace on 2016-07-27T13:53:20Z (GMT). No. of bitstreams: 1 Maria Marlene Miranda Aguiar.pdf: 2856096 bytes, checksum: 0312d9287c53f88728ceed5767f2f140 (MD5) Previous issue date: 2015-05-15 / This research had as main objective to investigate the school failure in high school. To understand the relationship between low-produce students and the school routine, were adopted two guiding principles: one facing the characterization of the schools and school workers in order to identify the infrastructure of schools surveyed and explanations of the agents on the subject in question, respectively; another with document analysis, PPP and minutes of final results, in order to know if the explanations of these school agents were coherent with school documents, which the relation between the discourses of the school agents to school failure of students and the measures taken by teachers, administrators and students to face the school ineffectiveness. For this, counted up with a literature review what were possible understanding the educational discourse that is being addressed about school failure, over the last few years and the explanation for the failure of the analyzed schools. Was held also a contextual study of the history and of the laws governing public policies for education and for this level of education. Then the research was conducted in two schools, one public and one private, to analyze what think the agents of these educational institutions, on the subject in question, what they do to solve the problem of school failure of students and the what differentiates these two groups, of the public school and of the private school to conduct the solutions for school ineffectiveness of their students. It was found that the two educational institutions, as alternatives of solution this issue, held meetings to present to parents of low-produce students, gave Math tutoring in against shift or on Saturdays, make recovery of the disciplines in which students had difficulties and consequently higher reprobation, but that these measures taken by these educational institutions were not sufficient to solve the problem of school failure of their students, due to the high reprobation still to make part every day of the two schools. These agents have attributed the failure of these schools to family, the education system, students, technologies, the traditional pedagogy, society, government policies, the laws governing education, in short, all those involved in the teaching-learning process. / Esta pesquisa teve como objetivo central investigar o fracasso escolar no ensino médio. Para entender as relações entre o baixo rendimento dos alunos e o cotidiano escolar, adotaram-se dois eixos norteadores: um voltado para a caracterização das escolas e dos agentes escolares, com o intuito de identificar a infraestrutura das escolas pesquisadas e as explicações dos agentes sobre o tema em questão, respectivamente; outro, voltado para uma análise documental, PPP e atas de resultados finais, com o propósito de saber se as explicações desses agentes escolares eram coerentes com os documentos da escola, qual a relação entre esses discursos e o insucesso escolar dos alunos e quais as medidas tomadas pelos professores, gestores e alunos para enfrentar a ineficácia escolar. Para isso, contou-se com uma revisão de literatura que possibilitasse compreender o discurso educacional que vem sendo abordado sobre o fracasso escolar, ao longo dos últimos anos e as explicações para o insucesso das escolas analisadas. Realizou-se também um estudo contextualizado da história e das leis que regem as políticas públicas voltadas para a educação e para esse nível de ensino. Em seguida, foram feitas as pesquisas em duas escolas, uma pública e outra particular, para analisar o que pensam os agentes dessas instituições de ensino, sobre a temática em questão, o que eles fazem para resolver o problema do insucesso escolar dos alunos e o que diferencia esses dois grupos, o da escola pública e da escola particular, no modo de pensar e de conduzir as soluções para a ineficácia escolar dos seus alunos. Verificou-se que as duas instituições de ensino, como alternativas de enfrentamento dessa problemática, fizeram reuniões para apresentar aos pais o baixo rendimento dos alunos, ministraram aula de reforço de Matemática no contra turno ou aos sábados, fizeram recuperações das disciplinas em que os alunos tinham dificuldades e, consequentemente, maior índice de reprovação, mas que estas medidas tomadas por essas instituições de ensino não foram suficientes para solucionar o problema do insucesso escolar dos seus alunos, em função da elevada taxa de reprovação ainda fazer parte do cotidiano das duas escolas. Esses agentes atribuíram o fracasso destas escolas à família, ao sistema educacional, aos alunos, às tecnologias, à pedagogia tradicional, à sociedade, às políticas de governo, às leis que regulamentam o ensino, em suma, todos os envolvidos no processo ensino-aprendizagem.

Les recherches sur la norme d'internalité (Beauvois & Dubois, 1988) ont établi l'existence d'une valorisation des explications internes dans le jugement social, tout en mettant en évidence le caractère non homogène de cette valorisation suivant les types d'explications internes. Dans ce cadre, le point de vue défendu dans cette thèse est que l'internalité réfère à la fois au lieu de causalité et au degré de contrôle qu'exerce l'individu sur l'origine des événements. L'objectif général de cette thèse était donc d'appréhender le rôle des dimensions de lieu de causalité et de contrôle interne dans l'attribution d'utilité sociale aux explications causales. Trois séries de recherches ont été conduites. La première avait pour objectif de cerner l'impact des dimensions causales (Weiner, 1979) sur l'attribution de valeur sociale par le biais de manipulation a priori des registres explicatifs (études 1 et 2) et par le biais de la perception qu'en ont les sujets (étude 2). La deuxième, visait à clarifier l'influence des dimensions de lieu de causalité et de contrôle interne sur l'attribution de valeur sociale, en dépassant certaines limites soulevées par la première série de recherches (études 3, 4, 5). La troisième, proposait d'articuler les champs de recherches sur la norme d'internalité et sur les théories implicites de l'intelligence, afin de confirmer l'importance du degré de contrôle interne dans l'attribution d'utilité sociale (études 6.a, 6.b, 6.c). De façon générale, les résultats étayent l'approche normative de l'internalité, les individus recourant à des explications du registre interne ayant fait l'objet d'une plus forte attribution de valeur sociale. De plus, ils soutiennent l'hypothèse d'une influence du lieu de causalité interne et du contrôle interne sur l'attribution d'utilité sociale

En août 2005, British Airways mit quatre jours à rétablir ses vols après une grève d'une journée d'un de ses sous-traitants. En interconnectant et intégrant leurs systèmes d'aide à la décision, les entreprises deviennent de plus en plus soumises aux changements. Parallèlement, avec le développement de technologies comme les puces RFID et la localisation par GPS les entreprises sont capables de suivre en temps réel le déroulement des opérations sur le terrain. Dans cette thèse nous nous intéressons au cas des problèmes de satisfaction de contraintes dans un cadre dynamique. En effet, depuis de nombreuses années la programmation par contraintes a fait la preuve de son efficacité pour résoudre des problèmes d'optimisation (tournées de véhicules, ordonnancements, etc) dans le cadre statique. Cependant le contexte dynamique soulève encore de nombreuses difficultés. Nous proposons donc un ensemble d'outils permettant la gestion et la prise en compte des événements, survenant de manière inattendue, dans le cadre de la programmation par contraintes. Chaque outil repose sur une approche particulière des problèmes dynamiques (tuples interdits, recherche locale, explications) et offre ainsi un éclairage différent et complémentaire.

La programmation par contraintes, carrefour de diverses disciplines, a montré son intérêt dans de nombreux domaines d'application. De nombreux problèmes réels sont dynamiques : le système de contraintes les définissant n'est donc pas figé. Pour résoudre un problème dynamique, il faut assurer une certaine incrémentalité et être capable de traiter les systèmes de contraintes contradictoires. En effet, il est souvent indispensable de fournir une solution quitte à ne pas respecter certaines contraintes. On parle alors de relaxation de contraintes.<br /><br />Durant cette thèse, nous nous sommes intéressés à la définition d'un système de relaxation de contraintes permettant de maintenir une propriété donnée dans un environnement dynamique. Nous avons mené ces travaux depuis une présentation abstraite d'un tel système jusqu'à son implémentation.<br /><br />Nous présentons un schéma algorithmique général abstrait de la recherche d'une solution à un problème sur-contraint basée sur l'exploration en meilleur d'abord d'un espace de configurations. Nous en donnons trois instances pour traiter les contraintes linéaires sur les rationnels, les Constraint Satisfaction Problems et les CSP numériques. Les deux dernières sont définies à l'aide d'un système de maintien de déduction dont la ma\^\itrise raisonnée nous a permis de donner une implémentation de ces instances ayant une bonne complexité : le système DECorum.<br /><br />Nous montrons, par le biais d'un certain nombre d'expérimentations, que l'utilisation de DECorum permet de retrouver les résultats classiques sur la transition de phase, de résoudre raisonnablement des problèmes de grande taille et d'utiliser la structure du problème résolu pour améliorer la recherche.<br /><br />Enfin, nous proposons la contrainte one-of permettant de modéliser et de résoudre une disjonction de contraintes en tirant profit du mécanisme d'exploration de DECorum. Nous validons l'intérêt de la contrainte one-of sur des problèmes d'ordonnancement : les Open-Shop.

La programmation par contraintes est souvent décrite, utopiquement, comme un paradigme déclaratif dans lequel l'utilisateur décrit son problème et le solveur le résout. Bien entendu, la réalité des solveurs de contraintes est plus complexe, et les besoins de personnalisation des techniques de modélisation et de résolution évoluent avec le degré d'expertise des utilisateurs. Cette thèse porte sur l'enrichissement de l'arsenal des techniques disponibles dans les solveurs de contraintes. D'une part, nous étudions la contribution d'un système d'explications à l'exploration de l'espace de recherche, dans le cadre spécifique d'une recherche locale. Deux heuristiques de voisinages génériques exploitant singulièrement les explications sont décrites. La première se base sur la difficulté de réparer une solution partiellement détruite, la seconde repose sur la nature non-optimale de la solution courante. Ces heuristiques mettent à jour la structure interne des problèmes traités pour construire des voisins de bonne qualité pour une recherche à voisinage large. Elles sont complémentaires d'autres heuristiques de voisinages génériques, avec lesquels elles peuvent être combinées efficacement. De plus, nous proposons de rendre le système d'explications paresseux afin d'en minimiser l'empreinte. D'autre part, nous effectuons un état des lieux des savoir-faire relatifs aux moteurs de propagation pour les solveurs de contraintes. Ces données sont exploitées opérationnellement à travers un langage dédié qui permet de personnaliser la propagation au sein d'un solveur, en fournissant des structures d'implémentation et en définissant des points de contrôle dans le solveur. Ce langage offre des concepts de haut niveau permettant à l'utilisateur d'ignorer les détails de mise en œuvre du solveur, tout en conservant un bon niveau de flexibilité et certaines garanties. Il permet l'expression de schémas de propagation spécifiques à la structure interne de chaque problème. La mise en œuvre et les expérimentations ont été effectués dans le solveur de contraintes Choco. Cette thèse a donné lieu à une nouvelle version de l'outil globalement plus efficace et nativement expliqué.

La programmation par contraintes est un sujet de recherche qui tire profit de nombreuses autres disciplines : mathématiques discrètes, analyse numérique, intelligence artificielle, recherche opérationnelle et calcul formel. Elle a prouvé son intérêt et son efficacité dans de nombreux domaines : optimisation combinatoire, ordonnancement, finance, simulation et synthèse de composants, diagnostic de panne, biologie moléculaire, ou encore problèmes géométriques. Néanmoins, un certain nombre de limitations et de difficultés ont été identifiées dans le domaine : conception d'algorithmes génériques et stables, traitement des problèmes dynamiques, accessibilité des concepts et des outils, ...<br /><br />Dans ce document, nous plaidons pour l'utilisation de la notion d'explication au sein de la programmation par contraintes. Notre but est double : non seulement présenter un tableau général des explications (définition, génération et utilisations) mais aussi montrer comment leur utilisation permet de contribuer à lever certains des problèmes ouverts en programmation par contraintes. Nous présentons aussi une démarche générale de résolution de problème dans un environnement expliqué. Enfin, nous montrons comment ce nouveau sujet semble promis à un bel avenir.