No / k-Clique detection enables computer scientists and sociologists to analyze social networks' latent structure and thus understand their structural and functional properties. However, the existing k-clique-detection approaches are not applicable to signed social networks directly because of positive and negative links. The authors' approach to detecting k-balanced trusted cliques in such networks bases the detection algorithm on formal context analysis. It constructs formal contexts using the modified adjacency matrix after converting a signed social network into an unweighted one. Experimental results demonstrate that their algorithm can efficiently identify the trusted cliques.

O problema de empacotamento em faixas de peças irregulares consiste em cortar um conjunto de peças bidimensionais a partir de um objeto de largura fixa utilizando o menor comprimento possível. Apesar de sua importância econômica para diversos setores industriais, há poucos trabalhos que abordam o problema de forma exata devido a sua dificuldade de resolução. Recentemente, Toledo et al. (2013) propuseram um modelo inteiro misto para este problema, no qual as peças são posicionadas em uma malha de pontos. Este modelo obteve bons resultados, provando a otimalidade para instâncias com até 21 peças. No entanto, o modelo possui um grande número de restrições de não-sobreposição, que cresce rapidamente de acordo com a discretização utilizada e a quantidade de peças distintas que devem ser alocadas. Neste trabalho, são propostas novas formulações matemáticas baseadas neste modelo, com o objetivo de reduzir o número de restrições. Na primeira abordagem, são propostos dois modelos reduzidos que mostraram ser eficientes para instâncias com poucas repetições de peças. Na segunda abordagem, foi proposto um modelo de cobertura por cliques para o problema. Este modelo obteve desempenho igual ou superior ao modelo da literatura para todas as instâncias avaliadas, obtendo uma solução ótima para instâncias com até 28 peças. / The irregular strip packing problem consists of cutting a set of two-dimensional pieces from an object of fixed width using the smallest possible length. Despite its economic importance for many industrial sectors, few exact studies have been made on this problem due to its difficulty of resolution. Recently, Toledo et al. (2013) proposed a mixed-integer model to this problem in which the pieces are placed on a grid. This model has worked successfully proving the optimality for instances up to 21 pieces. However, the model has a large number of non-overlapping constraints, which grows quickly in accordance with the discretization resolution and number of distinct pieces. In this work, we propose new mathematical formulations based on this model in order to reduce the number of constraints. In the first approach, we present two reduced models that have shown to be effective for instances with few repetitions of pieces. In the second approach, it was proposed a clique covering model for the problem. This model achieved a greater or equal performance than the literature for all instances, getting an optimal solution for instances up to 28 pieces.

O problema de empacotamento em faixas de peças irregulares consiste em cortar um conjunto de peças bidimensionais a partir de um objeto de largura fixa utilizando o menor comprimento possível. Apesar de sua importância econômica para diversos setores industriais, há poucos trabalhos que abordam o problema de forma exata devido a sua dificuldade de resolução. Recentemente, Toledo et al. (2013) propuseram um modelo inteiro misto para este problema, no qual as peças são posicionadas em uma malha de pontos. Este modelo obteve bons resultados, provando a otimalidade para instâncias com até 21 peças. No entanto, o modelo possui um grande número de restrições de não-sobreposição, que cresce rapidamente de acordo com a discretização utilizada e a quantidade de peças distintas que devem ser alocadas. Neste trabalho, são propostas novas formulações matemáticas baseadas neste modelo, com o objetivo de reduzir o número de restrições. Na primeira abordagem, são propostos dois modelos reduzidos que mostraram ser eficientes para instâncias com poucas repetições de peças. Na segunda abordagem, foi proposto um modelo de cobertura por cliques para o problema. Este modelo obteve desempenho igual ou superior ao modelo da literatura para todas as instâncias avaliadas, obtendo uma solução ótima para instâncias com até 28 peças. / The irregular strip packing problem consists of cutting a set of two-dimensional pieces from an object of fixed width using the smallest possible length. Despite its economic importance for many industrial sectors, few exact studies have been made on this problem due to its difficulty of resolution. Recently, Toledo et al. (2013) proposed a mixed-integer model to this problem in which the pieces are placed on a grid. This model has worked successfully proving the optimality for instances up to 21 pieces. However, the model has a large number of non-overlapping constraints, which grows quickly in accordance with the discretization resolution and number of distinct pieces. In this work, we propose new mathematical formulations based on this model in order to reduce the number of constraints. In the first approach, we present two reduced models that have shown to be effective for instances with few repetitions of pieces. In the second approach, it was proposed a clique covering model for the problem. This model achieved a greater or equal performance than the literature for all instances, getting an optimal solution for instances up to 28 pieces.

Description d'un système de vision stéréoscopique. Le but est de mettre en correspondance deux images d'une même scène acquises de deux points de vue différents et de reconstituer ensuite la structure tridimensionnelle de la scène. Des segments de droite sont extraits de l'image de gauche et de l'image de droite. Ces segments sont groupes convenablement afin de former des structures locales 2d. Sur la base de ces groupements, chaque image est décrite par un graphe relationnel ou les nœuds représentent les segments et les arcs représentent des relations structurelles entre les segments. La mise en correspondance des deux descriptions monoculaires obtenues est réalisée en trouvant des structures similaires entre les deux descriptions, ce qui est équivalent a la recherche d'un isomorphisme

Cette thèse vise à la mise en œuvre et à l'évaluation de techniques d'extraction de relations sémantiques à partir d'un corpus multilingue aligné. Ces relations seront extraites par transitivité de l'équivalence traductionnelle, deux lexèmes possédant les mêmes équivalents dans une langue cible étant susceptibles de partager un même sens. D'abord, nos observations porteront sur la comparaison sémantique d'équivalents traductionnels dans des corpus multilingues alignés. A partir des équivalences, nous tâcherons d'extraire des "cliques", ou sous-graphes maximaux complets connexes, dont toutes les unités sont en interrelation, du fait d'une probable intersection sémantique. Ces cliques présentent l'intérêt de renseigner à la fois sur la synonymie et la polysémie des unités, et d'apporter une forme de désambiguïsation sémantique. Elles seront créées à partir de l'extraction automatique de correspondances lexicales, basée sur l'observation des occurrences et cooccurrences en corpus. Le recours à des techniques de lemmatisation sera envisagé. Ensuite nous tâcherons de relier ces cliques avec un lexique sémantique (de type Wordnet) afin d'évaluer la possibilité de récupérer pour les unités arabes des relations sémantiques définies pour des unités en anglais ou en français. Ces relations permettraient de construire automatiquement un réseau utile pour certaines applications de traitement de la langue arabe, comme les moteurs de question-réponse, la traduction automatique, les systèmes d'alignement, la recherche d'information, etc.

Ha Minh Lam et M. Morales ont introduit une classe d'idéaux binomiaux qui est une extension binomiale d'idéaux monomiaux libres de carrés.Étant donné I un idéal monomial quadratique de k[x] libre de carrés et J une somme d'idéaux de scroll de k[z] qui satisfont certaines conditions, nous définissons l'extension binomiale de I comme B=I+J. Le sujet de cette thèse est d'étudier le nombre p plus grand tel que les sizygies de B son linéaires jusqu'au pas p-1. Sous certaines conditions d'ordre imposées sur les facettes du complexe de Stanley-Reisner de I nous obtiendrons un ordre > pour les variables de l'anneau de polynomes k[z]. Ensuite nous prouvons pour un calcul des bases de Gröbner que l'idéal initial in(B), sous l'ordre lexicographique induit par l'ordre de variables >, est quadratique libre de carrés. Nous montrerons que B est régulier si et seulement si I est 2-régulier. Dans le cas géneral, lorsque I n'est pas 2-régulier nous trouverons une borne pour l'entier q maximal qui satisfait que les premier q-1 sizygies de B son linéaires. En outre, en supossant que J est un idéal torique et en imposant des conditions supplémentaires, nous trouveron une borne supérieure pour l'entier q maximal qui satisfait que les premier q-1 sizygies de B son linéaires. En imposant des conditions supplémentaires, nous prouverons que les deux bornes sont égaux.

Prior research has shown that both lead users and opinion leaders may propel the diffusion of innovation. This raises the question of whether lead users and opinion leaders are positioned similarly in social networks, which we address using a sample of 23 school classes consisting of 537 children. Research among children is very scarce in this particular domain. Our statistical analyses based on hierarchical linear modeling reveal two general results: first, lead users among children appear to possess a variety of links between clusters; second, opinion leaders are locally positioned within clusters of children and have many direct links. (authors' abstract)

Les réseaux de capteurs corporels représentent un enjeu sociétal important en permettant des soins de meilleure qualité avec un coût réduit. Ces derniers sont utilisés pour détecter des anomalies dès leur apparition et ainsi intervenir au plus vite. Les capteurs sont soumis à de nombreuses contraintes de fiabilité, robustesse, taille et consommation. Dans cette thèse, les différentes opérations réalisées par les réseaux de capteurs corporels sont analysées. La consommation de chacune d'elles est évaluée afin de guider les axes de recherche pour améliorer l'autonomie énergétique des capteurs. Un capteur pour la détection d'arythmie sur des signaux cardiaques est proposé. Il intègre un traitement du signal via l'utilisation d'un réseau de neurone à cliques. Le système proposé est simulé et offre une exactitude de classification de 95 % pour la détection de trois types d'arythmie. Le prototypage du système via la fabrication d'un circuit mixte analogique/numérique en CMOS 65 nm montre une consommation du capteur de l'ordre de 1,4 μJ. Pour réduire encore plus l'énergie, une nouvelle méthode d'acquisition est utilisée. Une architecture de convertisseur est proposée pour l'acquisition et le traitement de signaux cardiaques. Cette dernière laisse espérer une consommation de l'ordre de 1,18 nJ pour acquérir les paramètres tout en offrant une exactitude de classification proche de 98 %. Cette étude permet d'ouvrir la voie vers la mise en place de capteurs très basse consommation pouvant durer toute une vie avec une simple pile. / Body area sensor networks gained great focused through the promiseof better quality and cheaper medical care system. They are used todetect anomalies and treat them as soon as they arise. Sensors are under heavy constraints such as reliability, sturdiness, size and power consumption. This thesis analyzes the operations perform by a body area sensor network. The different energy requirements are evaluated in order to choose the focus of the research to improve the battery life of the sensors. A sensor for arrhythmia detection is proposed. It includes some signal processing through a clique-based neural network. The system simulations allow a classification between three types of arrhythmia with 95 % accuracy. The prototype, based on a 65 nm CMOS mixed signal circuit, requires only 1.4 μJ. To further reduce energy consumption, a new sensing method is used. A converter architecture is proposed for heart beat acquisition. Simulations and estimation show a 1.18 nJ energy requirement for parameter acquisition while offering 98 % classification accuracy. This work leads the way to the development of low energy sensor with a lifetime battery life.

L'objectif des travaux présentés dans ce mémoire est la représentation de formes tridimensionnelles ainsi que la reconstruction tridimensionnelle a partir de coupes sériées. Après avoir défini le cadre exact de la reconstruction tridimensionnelle a partir de coupes sériées, le premier chapitre analyse les différentes étapes et les méthodes généralement employées pour effectuer cette reconstruction. Les chapitre 2 et 3 s'attachent a la description et a la représentation de formes tant bidimensionnelles que tridimensionnelles. Le chapitre 3 developpe ainsi une methode de squelettisation tridimensionnelle permettant d'obtenir un squelette filaire. Le chapitre 4 est consacre a la description de deux méthodes de reconstruction tridimensionnelle opérant par inférence de formes. La methode utilisant l'inférence structurelle de graphes de la ligne médiane est ensuite développée. Elle passe par une nécessaire étape, chapitre 5, de mise en correspondance de graphes de la ligne médiane. Différentes méthodes de mise en correspondance sont présentées, finalement la methode procédant par recherche de cliques dans un graphe est développée. La construction du graphe de mise en correspondance est tout d'abord présentée, ensuite la recherche de cliques est abordée a l'aide de méthodes heuristiques de parcours (recuit simule et algorithmes génétiques). Le chapitre 6 développe le processus d'inférence de graphes de la ligne médiane mis en œuvre, il permet d'inférer des coupes intermediaires qui sont empilées pour finalement donner le volume tridimensionnel recherche. Le chapitre 7 est consacre a la présentation des divers résultats et de leurs conséquences, il présenté aussi d'autres applications possibles des différentes techniques developpees

Nous présentons d'abord les théorèmes du No Free Lunch en nous basant sur le papier de D.H. Wolpert et W.G. Macready (version IEEE 1997) mais aussi les multiples réactions que ces résultats ont provoquées dans la communauté de l'optimisation. Convaincus dès lors de l'intérêt d'une approche globale des problèmes et de la nécessité de la recherche de propriétés générales - et spécialement des invariances par symétries -, nous tentons ensuite de mettre en oeuvre cette méthode dans le cadre de la coloration de graphes simples et non orientés. Ce champ est retenu en raison de son intérêt propre, mais aussi pour son caractère de modèle fécond dans de multiples problèmes d'optimisation. Nous faisons émerger la notion de décomposition d'un graphe en cliques maximales et celle de suites constructives qui permettent de reconstruire un graphe à partir de ses composants élémentaires (primary cliques), véritables équivalents des nombres premiers pour les entiers naturels. Nous produisons un algorithme principal et en étudions deux cas singuliers; ensemble ils fournissent une partition de l'ensemble des colorations valides du graphe étudié. Par suite nous retrouvons le polynôme chromatique de manière formelle, indépendamment du nombre de couleurs disponibles. Nous établissons une correspondance de Galois entre colorations valides et sous-graphes engendrés par des familles emboîtées de cliques maximales pourvu qu'elles soient des décompositions complètes de sous-graphes croissants du graphe total.