Dissertations / Theses: 'Algorithmes de course'

1

Nguyen, Vu-Linh. "Imprecision in machine learning problems." Thesis, Compiègne, 2018. http://www.theses.fr/2018COMP2433.

Full text

Abstract:

Nous nous sommes concentrés sur la modélisation et l'imprécision dans les problèmes d'apprentissage automatique, où les données ou connaissances disponibles souffrent d'imperfections importantes. Dans ce travail, les données imparfaites font référence à des situations où certaines caractéristiques ou les étiquettes sont imparfaitement connues, c'est-à-dire peuvent être spécifiées par des ensembles de valeurs possibles plutôt que par des valeurs précises. Les apprentissages à partir de données partielles sont couramment rencontrés dans divers domaines, tels que la biostatistique, l'agronomie ou l'économie. Ces données peuvent être générées par des mesures grossières ou censurées, ou peuvent être obtenues à partir d'avis d'experts. D'autre part, la connaissance imparfaite fait référence aux situations où les données sont spécifiées avec précision, cependant, il existe des classes qui ne peuvent pas être distinguées en raison d'un manque de connaissances (également appelée incertitude épistémique) ou en raison d'une forte incertitude (également appelée incertitude aléatoire). Considérant le problème de l'apprentissage à partir de données partiellement spécifiées, nous soulignons les problèmes potentiels liés au traitement de plusieurs classes optimales et de plusieurs modèles optimaux dans l'étape d'inférence et d'apprentissage, respectivement. Nous avons proposé des approches d'apprentissage actif pour réduire l'imprécision dans ces situations. Pourtant, la distinction incertitude épistémique/aléatoire a été bien étudiée dans la littérature. Pour faciliter les applications ultérieures d'apprentissage automatique, nous avons développé des procédures pratiques pour estimer ces degrés pour les classificateurs populaires. En particulier, nous avons exploré l'utilisation de cette distinction dans les contextes d'apprentissage actif et prudent We have focused on imprecision modeling in machine learning problems, where available data or knowledge suffers from important imperfections. In this work, imperfect data refers to situations where either some features or the labels are imperfectly known, that is can be specified by sets of possible values rather than precise ones. Learning from partial data are commonly encountered in various fields, such as bio-statistics, agronomy, or economy. These data can be generated by coarse or censored measurements, or can be obtained from expert opinions. On the other hand, imperfect knowledge refers to the situations where data are precisely specified, however, there are classes, that cannot be distinguished due to a lack of knowledge (also known as epistemic uncertainty) or due to a high uncertainty (also known as aleatoric uncertainty). Considering the problem of learning from partially specified data, we highlight the potential issues of dealing with multiple optimal classes and multiple optimalmodels in the inference and learning step, respectively. We have proposed active learning approaches to reduce the imprecision in these situations. Yet, the distinction epistemic/aleatoric uncertainty has been well-studied in the literature. To facilitate subsequent machine learning applications, we have developed practical procedures to estimate these degrees for popular classifiers. In particular, we have explored the use of this distinction in the contexts of active learning and cautious inferences

APA, Harvard, Vancouver, ISO, and other styles

2

Naseem, Jat Sadaf. "Genetic algorithms for university course timetabling problems." Thesis, University of Leicester, 2012. http://hdl.handle.net/2381/10997.

Full text

Abstract:

The university course timetabling problem is a difficult optimisation problem due to its highly-constrained nature. Finding an optimal, or even a high quality, timetable is a challenging task, especially when resources (e.g., rooms and time slots) are limited. In the literature, many approaches have been studied to solve this problem. In this thesis, we investigate genetic algorithms to solve the problem because they have been successfully used for a wide range of real-world problems. However, for university course timetabling problems, traditional genetic algorithms are not usually considered as efficient solvers. In this thesis, we investigate genetic algorithms to acquire good solutions for university course timetabling problems. Several ideas are introduced to increase the general performance of genetic algorithms on these problems. Local search strategies are introduced into the traditional genetic algorithm to enhance its performance for the university course timetabling problem. This differs from many works in the literature because it works on time slots of the timetable rather than events directly. A guided search approach is also introduced into genetic algorithms to produce high quality individuals into the population. In the guided search technique, the best parts of selected individuals from the current population are stored in an extra memory (or data structure) and are re-used to guide the generation of new individuals for subsequent populations. In addition to solving university course timetabling problems as a single-objective optimisation problem, we also tackle the multi-objective university course timetabling problem. We integrate the above proposed approaches into multi-objective evolutionary algorithms and propose a framework of multi-objective evolutionary algorithms based on local search and guided search strategies for the multi-objective university course timetabling problem. This framework is then instantiated into a set of multi-objective evolutionary algorithms for the multi-objective university course timetabling problem based on a set of multi-objective evolutionary algorithms that are typically used for general multi-objective optimisation problems. Computational results based on a set of well-known university course timetabling benchmark instances, show the effectiveness of the proposed approaches for both single- and multi-objective university course timetabling problems.

APA, Harvard, Vancouver, ISO, and other styles

3

DANTAS, VITOR CAVALCANTI. "ALGORITHMS FOR POST ENROLLMENT-BASED COURSE TIMETABLING." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2009. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=13807@1.

Full text

Abstract:

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR Problemas de Programação de Horários (PPHs) tem sido amplamente estudados, dada a sua importância prática e teórica. A maioria das variações do problema pertence µa classe NP-Difícil. Em geral, trata-se da alocação de recursos materiais e humanos no espaço e no tempo, visando a otimização de um conjunto de objetivos definidos. Na Programação de Horários de Cursos Universitários, por exemplo, o objetivo pode ser a satisfação do corpo docente e o desempenho acadêmico dos alunos. Nos últimos anos, as formulações de PPHs propostas pela International Timetabling Competition (ITC) tem sido bastante utilizadas, sendo notável a predominância de métodos baseados em busca local e metaeurísticas entre as abordagens propostas recentemente. Este trabalho tem como objetivo propor algoritmos para o Problema de Programação de Horários Pós-Matrícula da ITC, focando principalmente em métodos heurísticos baseados em Programação Matemática. Entre os modelos de Programação Linear Inteira Mista que propomos para este problema, destaca-se o modelo baseado na Formulação de Representantes Assimétricos para o Problema de Coloração de Grafos. Abordamos a aplicação da heurística de Local Branching e propomos um esquema de resolução por Geração de Colunas, como forma de viabilizar o tratamento dos modelos propostos, uma vez que a complexidade de tais modelos representa um desafio para os resolvedores de Programação Linear Inteira Mista atualmente disponíveis. Timetabling Problems have been widely studied, given its practical and theorical relevance. Most of its variations belong to the NP-Hard class of problems. In general, it is about allocation of material and human resources in time and space, aiming to optimize some set of defined objetives. In University Course Timetabling, for example, the objective might be the satisfaction of professors and the academic performance of students. In the last years, the formulations for timetabling problems proposed by the In- ternational Timetabling Competition (ITC) have been widely adopted. The predominance of meta-heuristics and local search-based methods is remark- able among the recently proposed approaches. The objetive of this thesis is to propose algorithms for the Post Enrolment-based Course Timetabling Problem of the ITC, focusing on Mathematical Programming-based heuris- tic methods. Among the Mixed Integer Linear Programming models that we propose for this problem, we highlight the one based on the Asymetric Representatives Formulation for the Graph Coloring Problem. We explore the application of the Local Branching heuristic and we propose a Column Generation solution procedure, as an attempt to handle the proposed models, given that the complexity of such models poses a challenge for currently available Mixed Integer Linear Programming solvers.

APA, Harvard, Vancouver, ISO, and other styles

4

Karrolla, Sanjay. "WEB APPLICATION FOR GRADUATE COURSE ADVISING SYSTEM." CSUSB ScholarWorks, 2017. https://scholarworks.lib.csusb.edu/etd/606.

Full text

Abstract:

The main aim of the course recommendation system is to build a course recommendation path for students to help them plan courses to successfully graduate on time. The Model-View-Controller (MVC) architecture is used to isolate the user interface (UI) design from the business logic. The front-end of the application develops the UI using AngularJS. The front-end design is done by gathering the functionality system requirements -- input controls, navigational components, informational components and containers and usability testing. The back-end of the application involves setting up the database and server-side routing. Server-side routing is done using Express JS.

APA, Harvard, Vancouver, ISO, and other styles

5

Lovelace, April L. "On the Complexity of Scheduling University Courses." DigitalCommons@CalPoly, 2010. https://digitalcommons.calpoly.edu/theses/245.

Full text

Abstract:

It has often been said that the problem of creating timetables for scheduling university courses is hard, even as hard as solving an NP-Complete problem. There are many papers in the literature that make this assertion but rarely are precise problem definitions provided and no papers were found which offered proofs that the university course scheduling problem being discussed is NP-Complete. This thesis defines a scheduling problem that has realistic constraints. It schedules professors to sections of courses they are willing to teach at times when they are available without overloading them. Both decision and optimization versions are precisely defined. An algorithm is then provided which solves the optimization problem in polynomial time. From this it is concluded that the decision problem is unlikely to be NP-Complete because indeed it is in P. A second more complex timetable design problem, that additionally seeks to assign appropriate rooms in which the professors can teach the courses, is then introduced. Here too both decision and optimization versions are defined. The second major contribution of this thesis is to prove that this decision problem is NP-Complete and hence the corresponding optimization problem is NP-Hard.

APA, Harvard, Vancouver, ISO, and other styles

6

Ritzenthaler, Christophe. "Problèmes arithmétiques relatifs à certains familles de courbes sur les corps finis." Paris 7, 2003. https://tel.archives-ouvertes.fr/tel-00003070.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Dhumal, Sayali. "WEB APPLICATION FOR GRADUATE COURSE RECOMMENDATION SYSTEM." CSUSB ScholarWorks, 2017. https://scholarworks.lib.csusb.edu/etd/605.

Full text

Abstract:

The main aim of the course advising system is to build a course recommendation path for students to help them plan courses to successfully graduate on time. The recommendation path displays the list of courses a student can take in each quarter from the first quarter after admission until the graduation quarter. The courses are filtered as per the student’s interest obtained from a questionnaire asked to the student. The business logic involves building the recommendation algorithm. Also, the application is functionality-tested end-to-end by using nightwatch.js which is built on top of node.js. Test cases are written for every module and implemented while building the application.

APA, Harvard, Vancouver, ISO, and other styles

8

Rao, Michaël. "Décompositions de graphes et algorithmes efficaces." Metz, 2006. http://docnum.univ-lorraine.fr/public/UPV-M/Theses/2006/Rao.Michael.SMZ0607.pdf.

Full text

Abstract:

Ce mémoire traite de la décomposition modulaire ainsi que différentes de ses généralisations. Dans un premier temps, on explique comment se servir de décompositions pour résoudre efficacement certains problèmes sur les graphes. En particulier, en utilisant la décomposition modulaire, on obtient des algorithmes linéaires pour les problèmes " ensemble stable ", " clique ", " nombre chromatique " et " partition en cliques " sur les graphes sans P_5 et gem induit. On étudie également comment la décomposition en coupes peut servir pour calculer le nombre chromatique, et on exhibe une nouvelle classe de problèmes de partitionnements pour lesquels on peut obtenir des algorithmes polynomiaux sur les graphes de largeur de clique bornée. Dans un second temps, on s'intéresse à généraliser la décomposition modulaire. On étudiera une nouvelle décomposition appelée décomposition bi-joint. On donne notamment différentes caractérisations des graphes complètement décomposables par cette décomposition, et un algorithme linéaire pour la calculer. On donne également des généralisations paramétrées de la décomposition modulaire, qui s'avèrent relativement proches de la largeur de clique This thesis deals with the modular decomposition and several of its generalizations. In a first time we show how graph decompositions can be used to solve efficiently some problems on graphs. We show how the modular decomposition can be used to obtain linear algorithms for " independent set ", " clique ", " chromatic number " and " partition into cliques " on (P_5,gem)-free graphs. We also show how the split decomposition can be used to compute the chromatic number, and we give a new class of vertex partitioning problems which can be solved in polynomial time on graphs of bounded clique width. In a second time, we are interested to generalize the modular decomposition. We study a new decomposition called the bi-join decomposition. We give in particular several characterizations of completely decomposable graphs, and a linear time decomposition algorithm. We introduce some parametrized generalization of the modular decomposition, and we show that theses generalizations are relatively close to the clique width

APA, Harvard, Vancouver, ISO, and other styles

9

Silva, Jose, Noel Varela, Jesus Varas, Omar Lezama, José Maco, and Martín Villón. "Comparison of bioinspired algorithms applied to the timetabling problem." Springer Science and Business Media Deutschland GmbH, 2021. http://hdl.handle.net/10757/654075.

Full text

Abstract:

The problem of timetabling events is present in various organizations such as schools, hospitals, transportation centers. The purpose of timetabling activities at a university is to ensure that all students attend their required subjects in accordance with the available resources. The set of constraints that must be considered in the design of timetables involves students, teachers and infrastructure. This study shows that acceptable solutions are generated through the application of genetic, memetic and immune system algorithms for the problem of timetabling. The algorithms are applied to real instances of the University of Mumbai in India and their results are comparable with those of a human expert. Revisión por pares

APA, Harvard, Vancouver, ISO, and other styles

10

Despiegel, Vincent. "Boîtes de substitutions : courbes hyperelliptiques et algorithmes de minimalisation." Université Joseph Fourier (Grenoble), 2007. http://www.theses.fr/2007GRE10162.

Full text

Abstract:

Les travaux effectués au cours de cette thèse portent sur l'optimisation de boîtes de substitutions vis à vis de la cryptanalyse linéaire et différentielle. Parallèlement à ceci, le but est de les rendre résistantes aux attaques algébriql ! telles que celles proposées par N. Courtois et 1. Pieprzyk, et ainsi de combler une faiblesse potentielle de l'AES. Pour cela, on explore diverses pistes. Dans un premier temps, la généralisation des boîtes de substitution elliptiques proposées par R. Gillard et F. Leprevost aux courbes hyperelliptiques permet d'augmenter sensiblement l'espace de recherche de boîtes de substitutions satisfaisantes et conduit à des résultats similaires. Dans un second temps, des algorithmes de minimalisation de boîtes de substitutions vis à vis des paramètres de résistance linéaire et différentielle permettent, à l'aide de stratégies gloutonnes et de permutations judicieusement choisies, d'obtenir des résultats qui s'approchent de la boîte de substitution de l'AES Ln this thesis, the airn is the optimisation ofkey tools usually used in blocks cyphers: substitution boxes. The goal is the optimization of their linear and differential resistance and their protection against algebraic attacks, developped by ! N. Courtois and 1. Pieprzyk, which are a potential weakness of the AES (Advanced Encryption System). Various means of optimization are studied. First, the generalisation of elliptic substitution boxes developped by R. Gillard and F. Leprevost to hyperelliptic curves leads to similar results, but increased the space of research. Secondly, we develop minirnalisation algorithms of substitution boxes, relatively to linear and differential resistance. A greedy heuristic and clever choices of permutations leads to results close to the substitution box of the AES

APA, Harvard, Vancouver, ISO, and other styles

11

Nigro, Abdelmalek. "Algorithmes progressifs stables pour l'approximation de courbes et surfaces." Phd thesis, Université Joseph Fourier (Grenoble), 1995. http://tel.archives-ouvertes.fr/tel-00346056.

Full text

Abstract:

Dans cette étude, nous traitons un problème d'interpolation de données dans le plan ou dans l'espace. Ce problème se distingue des autres problèmes existants par le fait que les points sont obtenus progressivement, c'est-à-dire à un instant donné, seules sont connues les données jusqu'à cet instant. Les méthodes utilisées sont basées sur l'utilisation de splines récurrentes, i.e., chaque morceau de la spline à l'étape i (correspondant à l'information i) est calculé en fonction des morceaux précédents par un raccordement paramétrique ou géométrique. L'algorithme ainsi construit est régi par une relation de récurrence dont nous étudions la stabilité numérique. Les données ont été interpolées de deux manières différentes: ― par une fonction spline vectorielle: dans ce cas la stabilité est démontrée au moyen des paramètres de forme issus du raccordement géométrique entre les sections de la spline. Ainsi, nous avons donné un nouveau rôle aux paramètres de forme qui consiste à absorber les oscillations provenant du calcul itératif. ― par une représentation scalaire des données: chaque morceau de la spline appartient à un espace de dimension n, engendré par une famille de fonctions ayant certaines propriétés. On démontre que la stabilité est en fait obtenue par le choix même des fonctions de base de l'espace

APA, Harvard, Vancouver, ISO, and other styles

12

Dehry, Nicolas. "Multicoupes et sous-graphes induits : complexité et algorithmes." Paris, CNAM, 2008. http://www.theses.fr/2008CNAM0598.

Full text

Abstract:

In this thesis, we consider some problems of graph theory. First, we deal with cut and multicut probems and then, we study induced subgrpah problems. Nevertheless, these two parts share a common purpose : detremining a general overview of the cimplexity of theses problems by proving NP-completeness results or by d"esigning polynomial algrotithms with low running times. In the first part, we tackle cut and multicut problems. We study the consequences of the addition of a cardinality constraint and show the NP-completeness of the general cases. Besides, we give complexity results for some particular graphs such as directed stars and undirected paths, and for the polynomial cases, we design several algorithms using dynamic programming or lagrangian relaxations. Next, we generalize these problems by considering multicriteria versions of the (multi)cut problems. We obtain some NP-completeness results in some very specific classes of graphs like undirected paths and cycles. In the secon part, we focus on the detection of specific induced subgraphs. More precisely, we look for induced paths, induced cycles or induced trees covering a given set of vertices. After proving the NP-completeness of the general cases, we consider the cases where the number of prescribed vertives is fixed. Finally , we also some structural results for C3 free graphs Dans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problémes de coupes et de multicoupes pouis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néammoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problémes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP-complètude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynominaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des typologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits ouvrant un ensemble T de sommets donnés. Après avouir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas ou la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large

APA, Harvard, Vancouver, ISO, and other styles

13

Bertone, Cristina. "Polynomial factorization and curve decomposition algorithms." Nice, 2010. http://www.theses.fr/2010NICE4012.

Full text

Abstract:

Les courbes algébriques affines sont un outil qui est appliqué dans plusieurs domains, par example le CAGD. Elles sont définies par des polynômes, mais souvent elles ont plusieurs composantes irréductibles distinctes. Dans cette thèse on développe des algorithmes efficaces pour la décomposition d’une courbe definie par des polynômes rationelles. Dans la première partie on présente un algorithme de factorisation absolue pour polynômes en deux variables (problème equivalent à la décomposition de courbes dans le plan). On part de l’algorithme existent TKTD et on améliore la définition de l’extension de corps nécessaire à la factorisation, utilisant des techniques modulaires et l’algorithme LLL pour identifier un nombre algébrique de son approximation p-adique. Dans la deuxième partie on passe au problème de décomposer une courbe dans l’espace tridimensionel: l’équivalent de la factorisation pour le cas du plan est la décomposition primaire d’un idéal pour le cas des 3 dimensions. D’abord on montre des bornes sur les degrées des surfaces qui séparent les différentes composantes, utilisant des résultats classiques de géometrie algébrique, comme le "Lifting problem" ou la regularité de Castelnuovo-Mumford. Après, on considère un algorithme de décomposition classique, mais pas efficace du point de vue computationel, auquel on applique les techniques modulaires. On obtient un algorithme modulaire qui donne la fonction d’Hilbert des composantes réduites de la courbe. Les deux algorithmes principales ont été testés sur plusieurs examples et comparés avec le temps d’exécution d’autres logiciels Affine algebraic curves are a tool applied in different fields, for instance CAGD. They are defined using polynomials, but they often have several different irreducible components. In this thesis we develop efficient algorithms to decompose a curve defined by rational polynomials. In the first part we present an absolute factorization algorithm for bivariate polynomials (this problem is equivalent to the decomposition of a curve in the plane). We start from the existing algorithm TKTD and we improve the definition of the algebraic extension needed for the factorization, using modular techniques and the LLL algorithm to identify an algebraic number form its p-adic approximation. In the second part we pass to the problem of decomposing a curve in the three-dimensional space: the corresponding technique of the factorization for the case of the plan is the primary decomposition of an ideal for the three-dimensional case. At first, we show some bounds on the degrees of the surfaces separating the different components, using some classical results of algebraic geometry, as the "Lifting problem" or the Castelnuovo-Mumford regularity. After this, we apply consider a classical algorithm of decomposition, which is not efficient for computations, and we apply on it the modular techniques. We obtain a modular algorithm giving the Hilbert function for the reduced components of the curve. The two main algorithms were tested on several examples and compared with the executions times of other softwares

APA, Harvard, Vancouver, ISO, and other styles

14

Chammas, Kristoffer, and Simon Sirak. "An Evaluation of the Great Deluge Algorithm in Course Timetabling : As Applied to the KTH-Inspired University Course Timetabling Problem." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-259907.

Full text

Abstract:

The University Course Timetabling Problem (UCTP) can be loosely described as assigning events (e.g lectures) to rooms and timeslots in a way that results in a feasible timetable that is optimal according to some custom criteria. The problem has become increasingly relevant as more programs become available in universities. Due to the complexity of UCTP, the problem is usually solved approximately using heuristics. The KTH-inspired UCTP is a variant of the UCTP that is adapted to KTH Royal Institute of Technology. However, few heuristics have been implemented for this variant of UCTP. Therefore, this study introduces an implementation of The Great Deluge heuristic to the KTH-inspired UCTP, and compares it to a state-of-the-art solver for KTH-inspired UCTP. The Great Deluge implementation was compared against the state-of-the-art KTH-inspired UCTP solver for different time limits. For each time limit, the output timetable quality was recorded over several executions. The comparison was done on two problem instances of varying complexity. The results suggest a behavior that varies over time. For larger time limits, GD produced better timetables than the state-of-the-art and the overall quality of timetables was consistent over several executions. For smaller time limits, GD produced worse timetables than the state-of-the-art and the overall quality of timetables was inconsistent over several executions. A few potential causes for the improved performance during the later stages of execution were found through further analysis of the results. Perhaps the biggest potential cause was utilizing the greedy behavior obtained during the mid to late stages of execution. ”The University Course Timetabling Problem” (UCTP) handlar i grova drag om att, baserat på ett antal kriterier, schemalägga föreläsningar, övningar och laborationer på ett optimalt sätt. Problemets relevans har ökat allt eftersom universitet utökar sina programutbud. På grund av komplexiteten hos UCTP löses problemet vanligtvis approximativt med hjälp av heuristiker. ”KTH-inspired UCTP” är en KTH-anpassad variant av UCTP för vilken endast ett fåtal heuristiker har implementerats. Denna variant har exempelvis inte lösts av en vanlig heuristik inom UCTP, ”The Great Deluge” (GD). Denna studie fokuserar därför på att applicera GD på ”KTH-inspired UCTP” och jämföra denna med äldre implementationer, med fokus på den bästa tillgängliga implementationen. GD-implementationen jämförs med den bästa tillgängliga implementationen för ”KTH-inspired UCTP” för olika tidsgränser. Kvaliteten hos de resulterande schemana evalueras och sparas sedan över flera körningar. Jämförelsen gjordes på två probleminstanser av olika komplexitet. Resultatet av jämförelsen föreslår att GD producerade bättre scheman för högre tidsgränser men sämre scheman för lägre tidsgränser. Vidare analys föreslår att denna förbättring beror på utnyttjandet av det giriga beteendet som vår GD-implementation uppvisar vid senare delar av exekvering.

APA, Harvard, Vancouver, ISO, and other styles

15

Berggren, Robert, and Timmy Nielsen. "Investigating the Reliability of Known University Course Timetabling Problem Solving Algorithms with Updated Constraints." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-229695.

Full text

Abstract:

Scheduling lectures, exams, seminars etc. for a university turns out to be a harder task than what it seems to be at first glance. This problem is known as the University Course Timetabling Problem (UCTP). The UCTP has been hosted for a number of competitions throughout the years by an organization called Practice and Theory of Automated Timetabling (PATAT). Because of these competitions, the problem has been given a standard description and set of constraints as well as standard problem instances for easier comparison of research and work on the subject. However, setting a standard like this have a major drawback; no variety is introduced since new research for finding the greatest method to solve the UCTP is forced to focus on a specific set of constraints, and algorithms developed will only be optimized with these constraints in consideration. In this research we compared five well known UCTP algorithms with the standard set of constraints to a different set of constraints. The comparisons showed a difference in the rank of performance between the algorithms when some constraints were changed to fit a certain need. The differences were not great but big enough to state that previous research declaring what algorithms are best for the UCTP problem cannot be relied upon unless you use close to identical sets of constraints. If the goal is to find the best algorithm for a new set of constraints then one should not rely on a single previously defined great algorithm but instead take two or three of the top performing ones for the greatest chance of finding the most optimized solution possible. Schemaläggning av föreläsningar, tentamen, seminarier etc. för ett universitet visar sig vara en svårare uppgift än vad det verkar vid första anblicken. Detta problem är känt som University Course Timetabling Problem (UCTP). UCTP har varit centralt i ett antal tävlingar genom åren av organisationen Practice and Theory of Automated Timetabling (PATAT). På grund av dessa tävlingar har problemet fått en standardbeskrivning och en uppsättning specifika begränsningar samt standard problemdata för enklare jämförelse av forskning och arbete i ämnet. Att sätta denna typ av standard har dock en stor nackdel; ingen variation tillförs då ny forskning för att hitta den bästa optimeringsmetoden inom UCTP tvingas att fokusera på en specifik uppsättning begränsningar och algoritmer som utvecklas kommer då endast att optimeras med dessa begränsningar i beaktande. I den här rapporten jämförde vi fem välkända UCTP algoritmer med standarduppsättningen av begränsningar mot en annan uppsättning begränsningar. Jämförelserna visade en skillnad i prestationsordningen mellan algoritmerna när vissa begränsningar ändrats för att passa ett visst behov. Skillnaderna var inte enorma men tillräckligt stora för att påvisa att tidigare forskning som förklarar vilka algoritmer som är bäst för UCTP-problemet ej är pålitlig om du inte använder nära till identiska uppsättningar av begränsningar. Om målet är att hitta den bästa algoritmen för en ny uppsättning begränsningar, bör man inte lita på en tidigare definierad effektiv algoritm utan istället använda sig utav två eller tre av de starkaste algoritmerna för den största chansen att hitta den mest optimerade lösningen.

APA, Harvard, Vancouver, ISO, and other styles

16

Breakiron, Daniel Aubrey. "Evaluating the Integration of Online, Interactive Tutorials into a Data Structures and Algorithms Course." Thesis, Virginia Tech, 2013. http://hdl.handle.net/10919/23107.

Full text

Abstract:

OpenDSA is a collection of open source tutorials for teaching data structures and algorithms. It was created with the goals of visualizing complex, abstract topics; increasing the amount of practice material available to students; and providing immediate feedback and incremental assessment. In this thesis, I first describe aspects of the OpenDSA architecture relevant to collecting user interaction data. I then present an analysis of the interaction log data gathered from three classes during Spring 2013. The analysis focuses on determining the time distribution of student activity, determining the time required for assignment completion, and exploring \credit-seeking" behaviors and behavior related to non-required exercises. We identified clusters of students based on when they completed exercises, verified the reliability of estimated time requirements for exercises, provided evidence that a majority of students do not read the text, discovered a measurement that could be used to identify exercises that require additional development, and found evidence that students complete exercises after obtaining credit. Furthermore, we determined that slideshow usage was fairly high (even when credit was not ordered), and skipping to the end of slideshows was more common when credit was offered but also occurred when it was not. Master of Science

APA, Harvard, Vancouver, ISO, and other styles

17

Mahmood, Asad. "Algorithmes d'adaptation pour la couche physique de systèmes multi-porteuses." Phd thesis, Télécom ParisTech, 2008. http://pastel.archives-ouvertes.fr/pastel-00004691.

Full text

Abstract:

Les systèmes multi-porteuses (MCM) actuelles n'atteignent pas leurs potentiel en raison de non-adaptation des paramètres de fonctionnement (e.g. taille de constellation, taux de codage, puissance émis etc.) par rapport l'état de canal (CSI) sur chaque sous-porteuse Cette thèse aborde le problème de la complexité des algorithmes d'adaptation en proposant des nouveaux algorithmes d'optimisation pour MCM. La complexité des algorithmes est ciblé sur le plan théorique / algorithmique ainsi que sur la coté architecture. La conception d'un nouvel algorithme de Bit-Loading (adaptation par rapport taille de constellation) est fait basé sur un rythme d'allocation présent dans l'allocation optimale/greedy. Le nouveau algorithme a une complexité beaucoup plus faible que d'autres algorithmes. Ensuite, développements théoriques et conception d'un nouvel algorithme de répartition optimale de puissance totale, en tenant compte la contrainte de puissance-maximale, est fait. Taux de codage étant un paramètre importante de la couche physique, une nouvelle méthode d'optimisation du profil d'irrégularité des codes LDPC irrégulière basé sur la quantification du phénomène de l'effet de vague (= ' Wave-Effect') est proposé avec les développements théoriques conduisant à une méthode de calcul efficace. Finalement, en utilisant les aspects adaptatif architecturale, une nouvelle méthodologie pour l'optimisation des ressources architecture pour un algorithme d'adaptation donné, en tenant compte les contraintes temporel de la canal de la transmission en temps réel., a été proposé.

APA, Harvard, Vancouver, ISO, and other styles

18

Bertone, Cristina. "Algorithmes de Factorisation de Polynomes et de Décomposition de Courbes." Phd thesis, Université de Nice Sophia-Antipolis, 2010. http://tel.archives-ouvertes.fr/tel-00560802.

Full text

Abstract:

Les courbes algébriques affines sont un outil qui est appliqué dans plusieurs domains, par example le CAGD. Elles sont définies par des polynômes, mais souvent elles ont plusieurs composantes irréductibles distinctes. Dans cette thèse on développe des algorithmes efficaces pour la décomposition d'une courbe definie par des polynômes rationelles. Dans la première partie on présente un algorithme de factorisation absolue pour polynômes en deux variables (problème equivalent à la décomposition de courbes dans le plan). On part de l'algorithme existant TKTD et on améliore la définition de l'extension de corps nécessaire à la factorisation, utilisant des techniques modulaires et l'algorithme LLL pour identifier un nombre algébrique de son approximation p-adique. Dans la deuxième partie on passe au problème de décomposer une courbe dans l'espace tridimensionel: l'équivalent de la factorisation pour le cas du plan est la décomposition primaire d'un idéal pour le cas des 3 dimensions. D'abord on montre des bornes sur les degrées des surfaces qui séparent les différentes composantes, utilisant des résultats classiques de géometrie algébrique, comme le "Lifting problem" ou la regularité de Castelnuovo-Mumford. Après, on considère un algorithme de décomposition classique, mais pas efficace du point de vue computationel, auquel on applique les techniques modulaires. On obtient un algorithme modulaire qui donne la fonction d'Hilbert des composantes réduites de la courbe. Les deux algorithmes principales ont été testés sur plusieurs examples et comparés avec le temps d'exécution d'autres logiciels.

APA, Harvard, Vancouver, ISO, and other styles

19

Kaufmann, Alain. "Algorithmes distribués pour l'intersection de courbes et surfaces de Bézier." Grenoble 1, 1990. http://www.theses.fr/1990GRE10128.

Full text

Abstract:

L'intersection de courbes de Bézier est une méthode naturellement parallèle car elle sépare un problème en plusieurs sous-problèmes similaires, et utilise donc un nombre croissant de processeurs durant la phase de séparation des solutions. Sur l'hypercube employé, la meilleure répartition testée des tâches consiste à satisfaire le plus grand nombre de processseurs. L'intersection surface/plan est composée d'une phase de subdivision, naturellement parallèle car générant un nombre croissant de tâches similaires ; et d'une phase de reconstruction des courbes d'intersection, qui comporte de moins en moins de tâches. De plus, pour effectuer de façon rapide cette reconstruction, il est nécessaires de conserver des liens entre les réseaux de Bézier obtenus par subdivision. La présence de ces liens va entraîner alors des contraintes quant à la répartition des tâches et/ou la topologie du réseau d'interconnexion des processeurs. L'expérimentation indique que ce sont les liens de voisinages ou ceux basés sur l'arbre de subdivision qui se révèlent obtenir les meilleurs résultats

APA, Harvard, Vancouver, ISO, and other styles

20

Habaieb, Hamadi. "Contribution à l'étude critique des algorithmes de prévision de crue en temps réel : exemples de l'Aveyron et de la Medjerdah." Toulouse, INPT, 1987. http://www.theses.fr/1987INPT015H.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Morain, François. "Courbes elliptiques et tests de primalité." Lyon 1, 1990. http://www.theses.fr/1990LYO10170.

Full text

Abstract:

Nous decrivons dans cette these l'application de la theorie des courbes elliptiques definies sur les corps finis a la construction d'algorithmes efficaces de primalite exacte. Nous faisons le lien entre le probleme de la representation des nombres premiers par des formes quadratiques binaires et la theorie du corps de classe. A ce propos, nous donnons un algorithme rapide de construction du corps de classe d'un corps quadratique imaginaire a l'aide des fonctions de weber. Nous en deduisons le calcul des invariants des courbes elliptiques a multiplication complexe dans un corps fini en resolvant par radicaux l'equation de definition du corps de classe, dans le corps des complexes d'abord, modulo un nombre premier ensuite. Nous montrons comment generaliser les algorithmes de preuve de primalite les plus classiques (reciproques du theoreme de fermat) en utilisant les courbes elliptiques. A l'encontre de son concurrent le plus serieux (sommes de jacobi), l'algorithme qui en resulte produit un certificat de primalite. D'un point de vue pratique, nous detaillons toutes les phases de l'implantation de l'algorithme, d'abord sur une station de travail, puis sur plusieurs stations d'une maniere distribuee. A chaque etape, nous presentons les meilleurs algorithmes connus pour resoudre chaque probleme particulier (calculs sur les courbes elliptiques, recherche de racines de polynomes modulo un nombre premier,. . . ). Nous decrivons egalement l'utilisation d'un multiplicateur hardware pour le calcul du produit de grands entiers, qui permet d'accelerer considerablement les calculs. Enfin, nous utilisons le programme pour la recherche de nombres premiers de cent chiffres (utiles en cryptographie) et pour la certification de nombres de trois cents a trois mille chiffres

APA, Harvard, Vancouver, ISO, and other styles

22

Sandh, David, and Lucas Knutsäter. "University Course Scheduling Optimization under Uncertainty based on a Probability Model." Thesis, Malmö universitet, Fakulteten för teknik och samhälle (TS), 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:mau:diva-20353.

Full text

Abstract:

In this thesis, we present a way to model uncertainty when optimizing the UniversityTimetabling Problem. It is an NP-hard, combinatorial and highly constrained problem.In this thesis, we first propose a standardized model based on the data from MalmöUniversity. Then, we propose our extended model, which, during the creation of the solution, accounts for the probability of unexpected events to occur and changes the solution accordingly. To implement our model, we use a Particle Swarm Optimization (PSO) algorithm.In our experiments, we find problems with the algorithm converging too early.We analyze the performance of our extended model compared to the standardized model,using a benchmark devised by us, and find that it performs well, reducing the number ofconstraint violations by 32%. We then suggest further areas of research in regards to thisuncertainty model.

APA, Harvard, Vancouver, ISO, and other styles

23

Bernède, Jean-Pierre. "Algorithmes adaptatifs et qualitatifs de prévision des crues en temps réel : application au cas de l'Aveyron." Toulouse, INPT, 1990. http://www.theses.fr/1990INPT060H.

Full text

Abstract:

A partir des hypotheses de conservation du gradient temporel intrinseque de hauteur (ou debit) en une station de prevision, de conservation de masse en regime transitoire a surface libre et par des essais de simulation sur la riviere aveyron, nous mettons en relief le role suffisamment explicatif, en situation de prevision de crues, des termes de gradients temporels, intrinseque de hauteur (ou debit), extrinseque de debit, associes a une hypothese de fermeture (sur les apports lateraux) par une integrale de dirac sur la pluie. Il en resulte dans un premier temps un modele de prevision des crues en temps reel, adaptatif par optimisation (sous contraintes) de l'erreur precedente, en association avec des lois qualitatives d'anticipation sur les variations de tendance a convexite negative. Finalement pour mieux prendre en compte la diversite des crues nous proposons un modele a ponderation evolutive sur le gradient temporel intrinseque du champ des hauteurs anamorphoses, sur le gradient temporel extrinseque de debit aux stations explicatives amonts et sur l'integrale de dirac de la pluie. L'anamorphose du champ des hauteurs et les parametres du modele sont indexes a un arbre de lois qualitatives analysant les changements potentiels de tendance en cours de realisation de l'evenement

APA, Harvard, Vancouver, ISO, and other styles

24

Fouh, Mbindi Eric Noel. "Building and Evaluating a Learning Environment for Data Structures and Algorithms Courses." Diss., Virginia Tech, 2015. http://hdl.handle.net/10919/51951.

Full text

Abstract:

Learning technologies in computer science education have been most closely associated with teaching of programming, including automatic assessment of programming exercises. However, when it comes to teaching computer science content and concepts, learning technologies have not been heavily used. Perhaps the best known application today is Algorithm Visualization (AV), of which there are hundreds of examples. AVs tend to focus on presenting the procedural aspects of how a given algorithm works, rather than more conceptual content. There are also new electronic textbooks (eTextbooks) that incorporate the ability to edit and execute program examples. For many traditional courses, a longstanding problem is lack of sufficient practice exercises with feedback to the student. Automated assessment provides a way to increase the number of exercises on which students can receive feedback. Interactive eTextbooks have the potential to make it easy for instructors to introduce both visualizations and practice exercises into their courses. OpenDSA is an interactive eTextbook for data structures and algorithms (DSA) courses. It integrates tutorial content with AVs and automatically assessed interactive exercises. Since Spring 2013, OpenDSA has been regularly used to teach a fundamental data structures and algorithms course (CS2), and also a more advanced data structures, algorithms, and analysis course (CS3) at various institutions of higher education. In this thesis, I report on findings from early adoption of the OpenDSA system. I describe how OpenDSA's design addresses obstacles in the use of AV systems. I identify a wide variety of use for OpenDSA in the classroom. I found that instructors used OpenDSA exercises as graded assignments in all the courses where it was used. Some instructors assigned an OpenDSA assignment before lectures and started spending more time teaching higher-level concepts. OpenDSA also supported implementing a ``flipped classroom'' by some instructors. I found that students are enthusiastic about OpenDSA and voluntarily used the AVs embedded within OpenDSA. Students found OpenDSA beneficial and expressed a preference for a class format that included using OpenDSA as part of the assigned graded work. The relationship between OpenDSA and students' performance was inconclusive, but I found that students with higher grades tend to complete more exercises. Ph. D.

APA, Harvard, Vancouver, ISO, and other styles

25

Salman, Alzahraa, and Rouwayd Hanna. "A Comparative Study between Genetic Algorithm, Simulated Annealing and a Hybrid Algorithm for solving a University Course Timetabling Problem." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-229432.

Full text

Abstract:

Every year, universities are faced with the problem of having to schedule events to various resources such as lecturers, classrooms and time slots while considering different constraints. The University Course Timetabling Problem is a NP-complete combinatorial optimization problem that, if solved manually, requires great investment in time and money. Thus finding an algorithm that automates this process would prove beneficial for society. The aim of this thesis is to compare the performance of a Genetic Algorithm-Simulated Annealing hybrid implementation with the performance of each of the algorithms individually for solving the University Course Timetabling Problem. The data sets used were inspired by the Royal Institute of Technology in Stockholm. The results showed that Simulated Annealing performed better than the other two algorithms, with respect to time consumption. However, the hybrid algorithm showed great promise of actually producing a feasible solution before terminating as the complexity of the problem increased, for example in the biggest data set tested. Varje år står universitetet inför problemet med att planera händelser till olika resurser, såsom föreläsare, klassrum och tidsluckor, med hänsyn till flertal fördefinierade villkor. Universitetsschemaläggningsproblemet är ett NP-fullständigt kombinatoriskt optimeringsproblem som kräver mycket tid och pengar om det löses manuellt. Att hitta en algoritm som automatiserar denna process skulle därför vara till nytta för samhället. Syftet med denna avhandling är att jämföra prestandan för en Genetisk Algoritm-Simulerad Glödning hybrid implementering med prestandan för var och en av algoritmerna individuellt för att lösa Universitetsschemaläggningsproblemet. Datamängderna som används är inspirerade av Kungliga Tekniska Högskolan i Stockholm. Resultaten visade att Simulerad Glödning presterade bättre än de andra två algoritmerna, med hänsyn till tidskonsumtion. Hybrid algoritmen visade dock ett stort potential att faktiskt ta fram en acceptabel lösning, innan den terminerar, när komplexiteten av datat ökade, till exempel i det största datasetet som testades.

APA, Harvard, Vancouver, ISO, and other styles

26

Tuitman, Jan. "Counting points in families of nondegenerate curves." Paris 6, 2010. http://www.theses.fr/2010PA066247.

Full text

Abstract:

Dans cette thèse nous considérons le problème du calcul de la fonction zêta et du nombre de points rationnels d'une courbe algébrique nondégénérée sur un corps fini. En utilisant les techniques de deformation en cohomologie rigide de Kedlaya et Lauder, nous développons un algorithme pour calculer ces objets dans ce cadre très général. Nous donnons de nouveaux resultats sur la structure intégrale de la cohomologie rigide des courbes nondégénérées, et à l'aide de quelques résultats récents sur les équations différentielles p-adiques, nous arrivons à améliorer les bornes pour la précision p-adique suffisante pour effectuer les calculs de façon prouvablement correcte. Notre algorithme a la même complexité asymptotique que l'algorithme existant de Castryck, Denef et Vercauteren, mais une implementation dans le système de calcul formel Magma montre que notre algorithme est plus pratique.

APA, Harvard, Vancouver, ISO, and other styles

27

Coeurjolly, David Miguet Serge Tougne Laure. "Algorithmique et géométrie discrète pour la caractérisation des courbes et des surfaces." Lyon : Université Lumière Lyon 2, 2002. http://demeter.univ-lyon2.fr:8080/sdx/theses/lyon2/2002/coeurjolly_d.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Dewaghe, Laurent. "Calcul du nombre de points sur une courbe elliptique dans un corps fini." Lille 1, 1996. https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/1996/50376-1996-354.pdf.

Full text

Abstract:

Ma thèse apporte des résultats théoriques et pratiques concernant le meilleur algorithme connu - algorithme de schoof-elkies-atkin (sea) - pour le calcul du nombre de points sur une courbe elliptique dans un corps fini de très grande caractéristique. Cela a permis de déterminer le nombre de points d'une courbe sur un corps de caractéristique étant un nombre record. Plus précisément, je décris, tout d'abord, quelques propriétés des polynômes intervenants dans sea (et plus généralement associes à la courbe elliptique e : polynômes de division, polynômes de division exacte, polynômes de semi-division et les polynômes modulaires), en particulier, je donne la forme de leur décomposition en facteurs irréductibles sur le corps de base. De plus, je montre le lien entre la réductibilité des polynômes modulaires et des polynômes de division. D'autre part, dans le cas d'un bon nombre premier, je donne la complexité des différentes déterminations d'une valeur propre du Frobenius de la courbe elliptique et j'accélère la phase finale de cette détermination, en évitant le calcul des ordonnées des points sur la courbe, dans certains cas que l'on précise

APA, Harvard, Vancouver, ISO, and other styles

29

Viry, Laurence. "Traitement de couche limite et méthodes Pic : algorithmes et approche objet." Nancy 1, 2000. http://docnum.univ-lorraine.fr/public/SCD_T_2000_0015_VIRY.pdf.

Full text

Abstract:

Le travail exposé dans ce document se compose de deux parties relativement indépendantes. _ La première relève de l'analyse et de la simulation numérique d'un problème physique lié au formage électromagnétique en haute fréquence. Le comportement asymptotique du modèle met en évidence l'existence d'une couche limité au voisinage de la surface du conducteur. Une écriture simplifiée d'un modèle numérique de notre problème a permis de dégager deux sous-problèmes à perturbation singulière, un problème elliptique classique et un problème elliptique avec transmission du phénomène électromagnétique. Nous étudions de façon complète en dimension un d'espace une méthode de décomposition de domaine sans recouvrement basée sur un schéma de résolution en différences finies et nous montrons, que pour un bon choix de la décomposition de domaine et de bonnes conditions limités à la frontière du métal, l'algorithme fournit une approximation uniforme de la solution et la vitesse de convergence du schéma itératif est super linéaire. Puis, nous généralisons à la dimension 2, dans le cadre de géométries circulaires. Une implémentation des algorithmes étudiés, utilisant une approximation de type éléments finis nous a fourni de bons résultats, quant à la précision de la solution obtenue et la vitesse de convergence. Ceci nous laisse penser que ces algorithmes devraient s'adapter à des géométries plus complexes. _ La seconde partie est plus de nature calcul scientifique avec - des aspects informatiques : par la mise en évidence de l'apport de la programmation orientée objet (p. O. O) pour répondre à des critères de qualité d'un code (exactitude, robustesse, extensibilité, réutilisabilité), et l'implémentation d'un code pic (particle-in-cell) de la physique des plasmas. - et des aspects plus numérique : par une étude comparative des méthodes de correction du champ électrique dans un modèle pic. Une première approche consiste à faire un calcul des densités de telle façon que l'équation de conservation de la charge soit vérifiée. La seconde approche consiste à effectuer une correction des champs électriques après la résolution des équations de Maxwell The work exposed in this document is made up of two relatively independant parts. _ The first part deals with mathematical and numerical simulations for a model of high frequency electromagnetic shaping of liquid metals. The asymptotic analysis gives prominence to the existence of singular perturbation problems with a weak layer closeness of the conductor surface. From our numerical model simplified formulation emerge two kinds of singular perturbation problems, classical elliptic problem and elliptic problem with electromagnetic transmission. We study in details a domain decomposition without recovering based on finite difference framework in one dimensional space to solve the transmission problem. We show that, for a good choice of the domain decomposition and boundary conditions at the artificial interface, we obtain a uniform approximation of the solution and the iterative procedure convergence rate which is superlinear. Then, we generalize these results into a two dimensional space for the radial case and we apply our results to enhanced finite element computations. We obtained rigorous convergence and accuracy estimates which seems to indicate that these schemes could be extended to more general geometries. _ The second part deals with a problem in computer science from - a computer science point of view: underlining opportunities of the objectoriented paradigm for advanced P. LC (Particle-In-Cell in plasma physic) modelling, with these known advantages : increased fiexibility, extensibility, robustness and so on. A two-dimensional relativistic electromagnetic PIC code implementation has been made. - a numerical point of view : a comparative study about electrical field correction in electromagnetic PIC plasma simulations is done. We analyze two techniques for reducing electric field error: the first one consists in using a charge conservating method to compute charge and current density onto the Maxwell discretization mesh, the second one is to use one divergence correction of electric fields based on the reformulated Maxwell system

APA, Harvard, Vancouver, ISO, and other styles

30

Zhao, Jinhua. "Maximum Bounded Rooted-Tree Problem : Algorithms and Polyhedra." Thesis, Université Clermont Auvergne‎ (2017-2020), 2017. http://www.theses.fr/2017CLFAC044/document.

Full text

Abstract:

Étant donnés un graphe simple non orienté G = (V, E) et un sommet particulier r dans V appelé racine, un arbre enraciné, ou r-arbre, de G est soit le graphe nul soit un arbre contenant r. Si un vecteur de capacités sur les sommets est donné, un sous-graphe de G est dit borné si le degré de chaque sommet dans le sous-graphe est inférieur ou égal à sa capacité. Soit w un vecteur de poids sur les arêtes et p un vecteur de profits sur les sommets. Le problème du r-arbre borné maximum (MBrT, de l’anglais Maximum Bounded r-Tree) consiste à trouver un r-arbre borné T = (U, F) de G tel que son poids soit maximisé. Si la contrainte de capacité du problème MBrT est relâchée, nous obtenons le problème du r-arbre maximum (MrT, de l’anglais Maximum r-Tree). Cette thèse contribue à l’étude des problèmes MBrT et MrT.Tout d’abord, ces deux problèmes sont formellement définis et leur complexité est étudiée. Nous présentons ensuite des polytopes associés ainsi qu’une formulation pour chacun d’entre eux. Par la suite, nous proposons plusieurs algorithmes combinatoires pour résoudre le problème MBrT (et donc le problème MrT) en temps polynomial sur les arbres, les cycles et les cactus. En particulier, un algorithme de programmation dynamique est utilisé pour résoudre le problème MBrT sur les arbres. Pour les cycles, nous sommes amenés a considérer trois cas différents pour lesquels le problem MBrT se réduit à certains problèmes polynomiaux. Pour les cactus, nous montrons tout d’abord que le problème MBrT peut être résolu en temps polynomial sur un type de graphes appelé cactus basis. En utilisant une série de décompositions en sous-problèmes sur les arbres et les cactus basis, nous obtenons un algorithme pour les graphes de type cactus.La deuxième partie de ce travail étudie la structure polyédrale de trois polytopes associés aux problèmes MBrT et MrT. Les deux premiers polytopes, Bxy(G,r,c) et Bx(G,r,c) sont associés au problème MBrT. Tous deux considèrent des variables sur les arêtes de G, mais seuls Bxy(G,r,c) possède également des variables sur les sommets de G. Le troisième polytope, Rx(G,r), est associé au problème MrT et repose uniquement sur les variables sur les arêtes. Pour chacun de ces trois polytopes, nous étudions sa dimension, caractérisons certaines inégalités définissant des facettes, et présentons les moyens possibles de décomposition. Nous introduisons également de nouvelles familles de contraintes. L’ajout de ces contraintes nous permettent de caractériser ces trois polytopes dans plusieurs classes de graphes.Pour finir, nous étudions les problèmes de séparation pour toutes les inégalités que nous avons trouvées jusqu’ici. Des algorithmes polynomiaux de séparation sont présentés, et lorsqu’un problème de séparation est NP-difficile, nous donnons des heuristiques de séparation. Tous les résultats théoriques développés dans ce travail sont implémentés dans plusieurs algorithmes de coupes et branchements auxquels une matheuristique est également jointe pour générer rapidement des solutions réalisables. Des expérimentations intensives ont été menées via le logiciel CPLEX afin de comparer les formulations renforcées et originales. Les résultats obtenus montrent de manière convaincante la force des formulations renforcées Given a simple undirected graph G = (V, E) with a so-called root node r in V, a rooted tree, or an r-tree, of G is either the empty graph, or a tree containing r. If a node-capacity vector c is given, then a subgraph of G is said to be bounded if the degree of each node in the subgraph does not exceed its capacity. Let w be an edge-weight vector and p a node-price vector. The Maximum Bounded r-Tree (MBrT) problem consists of finding a bounded r-tree T = (U, F) of G such that its weight is maximized. If the capacity constraint from the MBrT problem is relaxed, we then obtain the Maximum r-Tree (MrT) problem. This dissertation contributes to the study of the MBrT problem and the MrT problem.First we introduce the problems with their definitions and complexities. We define the associated polytopes along with a formulation for each of them. We present several polynomial-time combinatorial algorithms for both the MBrT problem (and thus the MrT problem) on trees, cycles and cactus graphs. Particularly, a dynamic-programming-based algorithm is used to solve the MBrT problem on trees, whereas on cycles we reduce it to some polynomially solvable problems in three different cases. For cactus graphs, we first show that the MBrT problem can be solved in polynomial time on a so-called cactus basis, then break down the problem on any cactus graph into a series of subproblems on trees and on cactus basis.The second part of this work investigates the polyhedral structure of three polytopes associated with the MBrT problem and the MrT problem, namely Bxy(G, r, c), Bx(G, r, c) and Rx(G, r). Bxy(G, r, c) and Bx(G, r, c) are polytopes associated with the MBrT problem, where Bxy(G, r, c) considers both edge- and node-indexed variables and Bx(G, r, c) considers only edge-indexed variables. Rx(G, r) is the polytope associated with the MrT problem that only considers edge-indexed variables. For each of the three polytopes, we study their dimensions, facets as well as possible ways of decomposition. We introduce some newly discovered constraints for each polytope, and show that these new constraints allow us to characterize them on several graph classes. Specifically, we provide characterization for Bxy (G, r, c) on cactus graphs with the help of a decomposition through 1-sum. On the other hand, a TDI-system that characterizes Bx(G,r,c) is given in each case of trees and cycles. The characterization of Rx(G,r) on trees and cycles then follows as an immediate result.Finally, we discuss the separation problems for all the inequalities we have found so far, and present algorithms or cut-generation heuristics accordingly. A couple of branch-and-cut frameworks are implemented to solve the MBrT problem together with a greedy-based matheuristic. We compare the performances of the enhanced formulations with the original formulations through intensive computational test, where the results demonstrate convincingly the strength of the enhanced formulations

APA, Harvard, Vancouver, ISO, and other styles

31

Mohamed, Sidi Mohamed Ahmed. "K-Separator problem." Thesis, Evry, Institut national des télécommunications, 2014. http://www.theses.fr/2014TELE0032/document.

Full text

Abstract:

Considérons un graphe G = (V,E,w) non orienté dont les sommets sont pondérés et un entier k. Le problème à étudier consiste à la construction des algorithmes afin de déterminer le nombre minimum de nœuds qu’il faut enlever au graphe G pour que toutes les composantes connexes restantes contiennent chacune au plus k-sommets. Ce problème nous l’appelons problème de k-Séparateur et on désigne par k-séparateur le sous-ensemble recherché. Il est une généralisation du Vertex Cover qui correspond au cas k = 1 (nombre minimum de sommets intersectant toutes les arêtes du graphe) Let G be a vertex-weighted undirected graph. We aim to compute a minimum weight subset of vertices whose removal leads to a graph where the size of each connected component is less than or equal to a given positive number k. If k = 1 we get the classical vertex cover problem. Many formulations are proposed for the problem. The linear relaxations of these formulations are theoretically compared. A polyhedral study is proposed (valid inequalities, facets, separation algorithms). It is shown that the problem can be solved in polynomial time for many special cases including the path, the cycle and the tree cases and also for graphs not containing some special induced sub-graphs. Some (k + 1)-approximation algorithms are also exhibited. Most of the algorithms are implemented and compared. The k-separator problem has many applications. If vertex weights are equal to 1, the size of a minimum k-separator can be used to evaluate the robustness of a graph or a network. Another application consists in partitioning a graph/network into different sub-graphs with respect to different criteria. For example, in the context of social networks, many approaches are proposed to detect communities. By solving a minimum k-separator problem, we get different connected components that may represent communities. The k-separator vertices represent persons making connections between communities. The k-separator problem can then be seen as a special partitioning/clustering graph problem

APA, Harvard, Vancouver, ISO, and other styles

32

Forsberg, Mikael. "Local search hybridization of a genetic algorithm for solving the University Course Timetabling Problem." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-229677.

Full text

Abstract:

The University Course Timetabling Problem (UCTP) is the problem of assigning locations (lecture halls, computer rooms) and time slots (time and date) to a set of events (lectures, labs) while satisfying a number of constraints such as avoiding double-bookings. Many variants of problem formulations exist, and most realistic variants are thought to be NP-hard. A recent trend in solving hard scheduling problems lies in the application of hybrid metaheuristics, where improvements are often found by hybridizing a population-based approach with some form of local search. In this paper, an implementation of a Genetic Algorithm (GA) that solves the UCTP is hybridized with local search in the form of Tabu Search (TS). The results show significant improvements to the performance and scalability over the non-hybridized GA. Two application strategies for the TS are investigated. The first strategy performs a switch-over from the GA to the TS, while the second interleaves the two algorithms. The effectiveness of each application strategy is seen to depend on the characteristics of the individual algorithms. Schemaläggningsproblemet UCTP (University Course Timetabling Problem) består av problemet att tilldela platser (föreläsningssalar, laborationssalar) och tidpunkter (datum och klockslag) till en mängd tillställningar (föreläsningar, laborationer) under kravet att upprätthålla en mängd restriktioner, exempelvis att undvika dubbelbokningar. Det finns många varianter av problemformuleringen och de flesta realistiska formuleringer anses ge upphov till NP-svåra optimeringsproblem. En förhållandevis ny trend för lösningsmodeller till svåra schemaläggningsproblem ligger i tillämpningen av hybrida metaheuristiker, där förbättringar ofta ses när populationsbaserade algoritmer kombineras med någon typ av lokalsökning. I denna rapport undersöks en UCTP-lösning baserad på en Genetisk Algoritm (GA) som hybridiseratsmed en lokalsökning i form av en Tabusökning (TS). Resultaten visar på signifikanta förbättringar i prestanda och skalbarhet jämfört med den icke-hybridiserade GA:n. Två appliceringsstrategier för TS undersöks. Den första strategin utgörs av att byta algoritm från GA till TS, medan den andra utgörs av att sammanfläta de två algoritmerna. Appliceringsstrategiernas effektivitet ses bero av de individuella algoritmernas egenskaper.

APA, Harvard, Vancouver, ISO, and other styles

33

Jeannin, Pierre. "Contrôle des courbes et surfaces rationnelles par vecteurs massiques." Lille 1, 1988. http://www.theses.fr/1988LIL10111.

Full text

Abstract:

On propose une nouvelle description des courbes et des surfaces rationnelles dans l'optique de leur traitement informatique en CAO, CFAO, DAO. Le contrôle se fait à l'aide des polynômes de Bernstein par la donnée d'un certain nombre de vecteurs massiques. On développe des techniques de recherche de polygones et réseaux massiques, notamment pour les coniques et les quadratiques. La matière de cette thèse peut être qualifiée de géométrie algorithmique.

APA, Harvard, Vancouver, ISO, and other styles

34

Alghamdi, Bandar. "Etude des méthodes d'ordonnancement sur les réseaux de capteurs sans fil." Thesis, Reims, 2015. http://www.theses.fr/2015REIMS010/document.

Full text

Abstract:

Les Wireless Body Area (WBAN) sont une technologie de réseau sans fil basée sur les radio-fréquences qui consiste à interconnecter sur, autour ou dans le corps humain de minuscules dispositifs pouvant effectuer des mesures (capteurs). Ces réseaux sont considérés comme les plus critiques dans les réseaux de capteurs sans fil. Ils sont basés sur des architectures de réseaux auto-organisés. Chacun des capteurs corporels reçoit ou envoie des paquets du ou au coordinateur du réseau. Ce dernier est responsable de l'ordonnancement des tâches pour l'ensemble des noeuds fils. L'ordonnancement dans les WBAN nécessite un mécanisme dynamique et adaptatif pour gérer les cas d'urgence qui peuvent se produire et permet ainsi d'améliorer les paramètres les plus importants comme la qualité de la transmission, le temps de réponse, le débit, le taux de paquets délivres, etc.Dans ces travaux de thèse, nous avons proposé trois techniques d'ordonnancement qui sont : la méthode semi-dynamique; la méthode dynamique et la méthode basée sur la priorité. De plus, une étude sur les plateformes WBAN est présentée. Dans cette étude, nous avons proposé une classification et une évaluation qualitative des plateformes déjà existantes. Nous avons aussi étudier les modèles de mobilité en proposant une architecture permettant de les décrire. Nous avons aussi mis en place une procédure de diagnostique afin de détecter rapidement des maladies épidémiques dangereuses. Par la suite, ces différentes propositions ont été validées en utilisant deux méthodes afin de vérifier leur faisabilité. Ces méthodes sont la simulation avec OPNET et l'implémentation réelle sur des capteurs TelosB et TinyOS The Wireless Body Area Network (WBAN) is the most critical field when considering Wireless Sensor Networks (WSN). It must be a self-organizing network architecture, meaning that it should be able to efficiently manage all network architecture requirements. The WBAN usually contains at least two or more body sensors. Each body sensor sends packets to or receives packets from the Personal Area Network Coordinator (PANC). The PANC is responsible for scheduling its child nodes' tasks. Scheduling tasks in the WBAN requires a dynamic and an adaptive process in order to handle cases of emergency that can occur with a given patient. To improve the most important parameters of a WBAN, such as quality link, response time, throughput, the duty-cycle, and packet delivery, we propose three scheduling processes: the semi-dynamic, dynamic, and priority-based dynamic scheduling approaches.In this thesis, we propose three task scheduling techniques, Semi-Dynamic Scheduling (SDS), Efficient Dynamic Scheduling (EDS) and High Priority Scheduling (HPS) approaches. Moreover, a comprehensive study has been performed for the WBAN platforms by classifying and evaluating them. We also investigate the mobility model for the WBANs by designing an architecture that describe this model. In addition, we detail a diagnosis procedure by using classification methods in order to solve very sensitive epidemic diseases. Then, our proposals have been validated using two techniques to check out the feasibility of our proposals. These techniques are simulation scenarios using the well-known network simulator OPNET and real implementations over TelosB motes under the TinyOS system

APA, Harvard, Vancouver, ISO, and other styles

35

Scherdel, Pauline. "La surveillance de la croissance des enfants comme outil de repérage." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLS326.

Full text

Abstract:

La surveillance de la croissance des enfants est une activité quasi-universelle visant principalement à repérer des affections graves chez des enfants apparemment sains. Il existe des preuves empiriques que les performances de cette surveillance sont faibles, ce qui pourrait s’expliquer par l’absence de consensus sur trois questions clés et interdépendantes : quelles sont les affections à cibler en priorité ? comment définir une croissance anormale ? et quelles sont les courbes de croissance à utiliser ?Nous avons montré qu’il existait une grande hétérogénéité des pratiques de surveillance de la croissance en Europe et que les sept algorithmes proposés pour définir une croissance anormale avaient des performances et/ou un niveau de validation faible. Nous avons réalisé une étude de validation externe et une comparaison face-à-face de ces algorithmes et démontré que la règle de Grote avait les meilleures performances. Nous avons montré que la croissance des enfants français contemporains était plus proche des courbes de l’OMS que des courbes de référence françaises, excepté dans les six premiers mois de vie, et que l’introduction des courbes de l’OMS augmenterait la sensibilité des algorithmes au détriment de leurs spécificités. Nous avons obtenu un consensus d’experts internationaux sur la typologie des affections cibles prioritaires et un consensus national sur une liste réduite de huit affections cibles prioritaires des algorithmes de surveillance de la croissance.Ces connaissances nouvelles permettront très probablement de proposer des outils plus valides pour la surveillance de la croissance et de standardiser les pratiques pour améliorer la santé des enfants Growth monitoring in children is a worldwide health activity which aims at early detection of serious underlying disorders of apparently healthy children. Existing empirical evidence shows that growth-monitoring performance were low, this can be explained by a lack of consensus on three key and interconnected questions: which conditions should be targeted? how should abnormal growth be defined? and which growth charts should be used?We showed that there is a large heterogeneity in growth-monitoring practices in Europe and that the seven algorithms proposed for defining an abnormal growth had low performance and/or a level of validation. We performed an external validation study and head-to-head comparison of these seven algorithms and demonstrated that the Grote clinical rule had the best performance. We found that the growth of contemporary French children were closer to the WHO than French growth charts, except during the first six month of life. The introduction of WHO growth charts would increase the sensitivity at the expense of their specificity. We obtained an international consensus on the typology of priority target conditions and national consensus on a short list of eight priority target conditions of growth-monitoring algorithms.This new knowledge will most likely allow developing validated tools for growth monitoring and standardizing practices for improving child outcomes

APA, Harvard, Vancouver, ISO, and other styles

36

Abelard, Simon. "Comptage de points de courbes hyperelliptiques en grande caractéristique : algorithmes et complexité." Thesis, Université de Lorraine, 2018. http://www.theses.fr/2018LORR0104/document.

Full text

Abstract:

Le comptage de points de courbes algébriques est une primitive essentielle en théorie des nombres, avec des applications en cryptographie, en géométrie arithmétique et pour les codes correcteurs. Dans cette thèse, nous nous intéressons plus particulièrement au cas de courbes hyperelliptiques définies sur des corps finis de grande caractéristique $p$. Dans ce cas de figure, les algorithmes dérivés de ceux de Schoof et Pila sont actuellement les plus adaptés car leur complexité est polynomiale en $\log p$. En revanche, la dépendance en le genre $g$ de la courbe est exponentielle et se fait cruellement sentir même pour $g=3$. Nos contributions consistent principalement à obtenir de nouvelles bornes pour la dépendance en $g$ de l'exposant de $\log p$. Dans le cas de courbes hyperelliptiques, de précédents travaux donnaient une borne quasi-quadratique que nous avons pu ramener à linéaire, et même constante dans le cas très particuliers de familles de courbes dites à multiplication réelle (RM). En genre $3$, nous avons proposé un algorithme inspiré de ceux de Schoof et de Gaudry-Harley-Schost dont la complexité, en général prohibitive, devient très raisonnable dans le cas de courbes RM. Nous avons ainsi pu réaliser des expériences pratiques et compter les points d'une courbe hyperelliptique de genre $3$ pour un $p$ de 64 bits Counting points on algebraic curves has drawn a lot of attention due to its many applications from number theory and arithmetic geometry to cryptography and coding theory. In this thesis, we focus on counting points on hyperelliptic curves over finite fields of large characteristic $p$. In this setting, the most suitable algorithms are currently those of Schoof and Pila, because their complexities are polynomial in $\log q$. However, their dependency in the genus $g$ of the curve is exponential, and this is already painful even in genus 3. Our contributions mainly consist of establishing new complexity bounds with a smaller dependency in $g$ of the exponent of $\log p$. For hyperelliptic curves, previous work showed that it was quasi-quadratic, and we reduced it to a linear dependency. Restricting to more special families of hyperelliptic curves with explicit real multiplication (RM), we obtained a constant bound for this exponent.In genus 3, we proposed an algorithm based on those of Schoof and Gaudry-Harley-Schost whose complexity is prohibitive in general, but turns out to be reasonable when the input curves have explicit RM. In this more favorable case, we were able to count points on a hyperelliptic curve defined over a 64-bit prime field

APA, Harvard, Vancouver, ISO, and other styles

37

Mahdi, Abdel Halim. "Utilisation de métaheuristiques hybrides pour la Résolution de problèmes d'agencement d'atelier, de découpe 2D et d'ordonnancement." Vandoeuvre-les-Nancy, INPL, 2000. http://www.theses.fr/2000INPL089N.

Full text

Abstract:

Nous présentons dans cette thèse la résolution de trois problèmes d’optimisation liés aux systèmes de production : 1) Deux problèmes d’agencement physique d’un ensemble de cellules de production sur un atelier. Nous considérons dans ce cas des formes polygonales rectilinéaires rigides pour les cellules ainsi que la possibilité d’affecter trois types de moyens de manutention pour transporter les différents flux de produit. 2) Un problème de découpe à deux dimensions de formes polygonales rectilinéaires 3) Des problèmes d’ordonnancement de type « flowshop » général. La résolution de ces différents types de problème se fait par le biais d’hybridation des métaheuristiques que sont les algorithmes génétiques et le recuit simulé avec d’autres algorithmes conçus pour des besoins spécifiques à chacune des applications. Un algorithme d’Hitchcock dans le cas de l’agencement, des procédures complexes de réparation et d’exploration de l’espace libre dans le cas des problèmes de découpe et des opérateurs orientés données dans le cas des problèmes d’ordonnancement In this thesis, we present efficient methods for solving three optimization problems dealing with production systems : 1) Two physical facility layout problems. We consider rigid and polygonal rectilinear shapes for the cells and the material handling system assignment to transport the different production flows. 2) 2 dimensional cutting problem for polygonal rectilinear shapes 3) Flowshop scheduling problems. For solving each problem, we use hybrid methods combining metaheuristics such an genetic algorithms and simulated annealing with other procedures used specifically to each application. Hitchcock algorithm for layout problems, complex repairing procedures and free space exploration algorithms for the 2D cutting problems and data oriented operators for flowshop problems

APA, Harvard, Vancouver, ISO, and other styles

38

Delaunay, Christophe. "Formes modulaires et invariants de courbes elliptiques définies sur Q." Bordeaux 1, 2002. http://www.theses.fr/2002BOR12628.

Full text

Abstract:

Cette thèse est constituée de plusieurs parties indépendantes qui s'intègrent toutes dans le cadre général de l'étude des courbes elliptiques et des formes modulaires. Nous nous intéressons tout d'abord au revêtement modulaire des courbes elliptiques définies sur Q. En particulier, nous décrivons la méthode des points de Heegner pour le calcul explicite des points rationnels non triviaux lorsque le rang analytique de la courbe elliptique vaut 1. Nous étudions alors le cas des cubiques de Sylvester (x3+y3=m). Nous expliquons comment déterminer efficacement le degré modulaire en utilisant le carré symétrique de la série L de la courbe elliptique. Puis, nous proposons une étude des points critiques du revêtement. En se basant sur l'analogie qui existe entre les courbes elliptiques et les corps de nombres, nous faisons une étude sur les groupes de Tate-Shafarevitch des courbes elliptiques définies sur Q similaire à celle de Cohen et Lenstra sur les groupes de classes d'un corps de nombres. Enfin, l'utilisation du carré symétrique pour le calcul du degré modulaire, s'inscrit dans le cadre plus général des conjectures de Deligne sur les valeurs spéciales des séries L. Nous expliquons comment vérifier numériquement ces conjectures dans le cas des puissances symétriques des séries L de formes modulaires, et nous donnons un nombre conséquent d'exemples.

APA, Harvard, Vancouver, ISO, and other styles

39

Broberg, Felix, and Emelie Eriksson. "Comparing MAX-MIN and Rank-based Ant Colony Optimization Algorithms for solving the University Course Timetabling Problem." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-229790.

Full text

Abstract:

The University Course Timetabling Problem (UCTP) is a scheduling problem regarding courses, time slots and rooms, and is often accompanied by a set of feature requirements. As non-trivial instances of the UCTP are NP-hard, traditional computational methods are ineffective. A meta-heuristic alternative is the Ant Colony Optimization (ACO) algorithm, which has previously been proven to successfully solve the UCTP. This paper investigates the relative effectiveness of the MAX-MIN ACO variation to the Rank-based ACO variation on UCTP problem sets of varying difficulty. They are also compared when using a local-search help function and a path attractiveness heuristic. This study shows that the ACO variations perform similarly well for all problem difficulties when utilizing the path attractiveness heuristic. Utilizing both local search and the heuristic produces the best results across the difficulties and ACO variations. There is, however, a need for further investigation into the parameters for both ACO variations to ensure the validity of the conclusion. Det universitetsbaserade schemaläggningsproblemet (UCTP) avser schemaläggning av kurser till rum och tider där hänsyn till en mängd funktionella krav ofta måste tas. Traditionella beräkningsmetoder har visats vara ineffektiva då icke-triviala fall av problemet är NP-svåra. Myrkolonisystemsalgoritmen (ACO) är ett meta-heuristiskt alternativ som framgångsrikt har använts för att lösa UCTP. Denna rapport jämför effektiviteten mellan MAX-MIN ACO-variationen och den Rank-baserade ACO-variationen i att hitta lösningar till UCTP. Variationerna jämförs också vid använding av "local search" och en vägvalsheuristik. Rapporten visar att ACO-variationerna presterar likvärdigt vid användande av vägvalsheuristiken. Användandet av både "local search" och vägvalsheuristiken leder till bästa resultat för samtliga svårighetsgrader och ACO-variationer. Efterforskning krävs angående parametrarna för ACO-variationerna för att säkerställa giltigheten av slutsatserna.

APA, Harvard, Vancouver, ISO, and other styles

40

Luhandjula, Thierry. "Algorithme de reconnaissance visuelle d'intentions : application au pilotage automatique d'un fauteuil roulant." Phd thesis, Université Paris-Est, 2012. http://tel.archives-ouvertes.fr/tel-00794527.

Full text

Abstract:

Dans cette thèse, nous proposons une approche méthodologique et algorithmique pour la reconnaissance visuelle d'intentions, basée sur la rotation et le mouvement vertical de la tête et de la main. Le contexte dans lequel cette solution s'inscrit est celui d'une personne handicapée, dont la mobilité est assurée par un fauteuil roulant. Le système proposé constitue une alternative intéressante aux interfaces classiques de type manette, boutons pneumatiques, etc. La séquence vidéo, composée de 10 images, est traitée en utilisant différentes méthodes pour construire ce qui dans cette thèse est désigné par " courbe d'intention ". Une base de règles est également proposée pour classifier chaque courbe d'intention. Pour la reconnaissance basée sur les mouvements de la tête, une approche utilisant la symétrie du visage est proposée pour estimer la direction désirée à partir de la rotation de la tête. Une Analyse en Composantes Principales (ACP) est utilisée pour détecter l'intention de varier la vitesse de déplacement du fauteuil roulant, à partir du mouvement vertical de la tête. Pour la reconnaissance de la direction basée sur la rotation de la main, une approche utilisant à la fois la symétrie verticale de la main et un algorithme d'apprentissage (réseaux neuronaux, machines à vecteurs supports ou k-means), permet d'obtenir les courbes d'intentions exploitées par la suite pour la détection de la direction désirée. Une autre approche, s'appuyant sur l'appariement de gabarits de la région contenant les doigts, est également proposée. Pour la reconnaissance de la vitesse variable basée sur le mouvement vertical de la main, deux approches sont proposées. La première utilise également l'appariement de gabarits de la région contenant les doigts, et la deuxième se base sur un masque en forme d'ellipse, pour déterminer la position verticale de la main. Les résultats obtenus montrent de bonnes performances en termes de classification aussi bien des positions individuelles dans chaque image, que des courbes d'intentions. L'approche de reconnaissance visuelle d'intentions proposée produit dans la très grande majorité des cas un meilleur taux de reconnaissance que la plupart des méthodes proposées dans la littérature. Par ailleurs, cette étude montre également que la tête et la main en rotation et en mouvement vertical constituent des indicateurs d'intention appropriés

APA, Harvard, Vancouver, ISO, and other styles

41

Dang, Thanh-Hung. "Scalar complexity of Chudnovsky-type algorithms of multiplication in finite fields." Thesis, Aix-Marseille, 2020. http://www.theses.fr/2020AIXM0131.

Full text

Abstract:

L’algorithme de type évaluation-interpolation sur des courbes algébriques, introduit par D.V et G.V Chudnovsky en 1987, est à la base des techniques algorithmiques fournissant actuellement les meilleures bornes de la complexité bilinéaire de la multiplication dans les corps finis. En particulier, ces algorithmes sont connus pour avoir asymptotiquement une complexité bilinéaire linéaire ou quasi linéaire. Mais jusqu’à présent aucun travail ne s’était attaqué à l’analyse de leur complexité scalaire. Aussi, s’intéresse-t-on dans cette thèse à la complexité scalaire de ces algorithmes. Plus précisément, nous présentons une stratégie générique permettant d’obtenir des algorithmes de type Chudnovsky ayant une complexité scalaire optimisée. Cette complexité est directement liée à une représentation des espaces de Riemann-Roch sous-jacents visant à l’obtention de matrices creuses. Les résultats théoriques et numériques obtenus suggèrent que notre stratégie d’optimisation est indépendante du choix du diviseur permettant de construire les espaces de Riemann-Roch. En utilisant cette stratégie, nous améliorons de 27% la complexité scalaire de la construction de Baum-Shokrollahi (1992) sur le corps F256/F4. De plus, pour ce corps, notre construction est la meilleure connue en termes de complexité totale. Les sources des programmes Magma utilisés dans cette thèse sont données en appendice The evaluation-interpolation algorithm on algebraic curves, introduced by D.V. and G.V. Chudnovsky in 1987, is the basis of algorithmic techniques currently providing the best bounds of the bilinear complexity of multiplication in finite fields. In particular, these algorithms are known to have asymptotically linear or quasi-linear bilinear complexity. But until now no work has been done on the analysis of their scalar complexity. Therefore, in this thesis we are interested in the scalar complexity of these algorithms. More precisely, we present a generic strategy to obtain Chudnovsky-type algorithms with optimized scalar complexity. This complexity is directly related to a representation of the underlying Riemann-Roch spaces aimed at obtaining sparse matrices. The theoretical and numerical results obtained suggest that our optimization strategy is independent of the choice of the divisor used to construct the Riemann-Roch spaces. Using this strategy, we improve by 27% the scalar complexity of the construction of Baum-Shokrollahi (1992) on the field F256/F4. Moreover, for this field, our construction is the best known in terms of total complexity. The sources of the Magma programs used in this thesis are given in appendix

APA, Harvard, Vancouver, ISO, and other styles

42

Taktak, Raouia. "Survavibility in Multilayer Networks : models and Polyhedra." Thesis, Paris 9, 2013. http://www.theses.fr/2013PA090076/document.

Full text

Abstract:

Dans cette thèse, nous nous intéressons à un problème de fiabilité dans les réseaux multicouches IP-sur-WDM. Etant donné un ensemble de demandes pour lesquelles on connaît une topologie fiable dans la couche IP, le problème consiste à sécuriser la couche optique WDM en y cherchant une topologie fiable. Nous montrons que le problème est NP-complet même dans le cas d'une seule demande. Ensuite, nous proposons quatre formulations en termes de programmes linéaires en nombres entiers pour le problème. La première est basée sur les contraintes de coupes. Nous considérons le polyèdre associé. Nous identifions de nouvelles familles de contraintes valides et étudions leur aspect facial. Nous proposons également des algorithmes de séparation pour ces contraintes. En utilisant ces résultats, nous développons un algorithme de coupes et branchements pour le problème et présentons une étude expérimentale. La deuxième formulation utilise comme variables des chemins entre des terminaux dans le graphe sous-jacent. Un algorithme de branchements et génération de colonnes est proposé pour cette formulation. Par la suite, nous discutons d'une formulation dite naturelle utilisant uniquement les variables de design. Enfin, nous présentons une formulation étendue compacte qui, en plus des variables naturelles, utilise des variables de routage. Nous montrons que cette formulation fournit une meilleure borne inférieure This thesis deals with a problem related to survivability issues in multilayer IP-over-WDM networks. Given a set of traffic demands for which we know a survivable logical routing in the IP layer, the aim is determine the corresponding survivable topology in the WDM layer. We show that the problem is NP-hard even for a single demand. Moreover, we propose four integer linear programming formulations for the problem. The first one is based on the so-called cut inequalities. We consider the polyhedron associated with the formulation. We identify several families of valid inequalities and discuss their facial aspect. We also develop separation routines. Using this, we devise a Branch-and-Cut algorithm and present experimental results. The second formulation uses paths between terminals of the underlying graph as variables. We devise a Branch-and-Price algorithm based on that formulation. In addition, we investigate a natural formulation for the problem which uses only the design variables. Finally, we propose an extended compact formulation which, in addition to the design variables, uses routing variables. We show that this formulation provides a tighter bound for the problem

APA, Harvard, Vancouver, ISO, and other styles

43

Mameri, Djelloul. "L'indépendant faiblement connexe : études algorithmiques et polyédrales." Thesis, Clermont-Ferrand 2, 2014. http://www.theses.fr/2014CLF22513/document.

Full text

Abstract:

Dans ce travail, nous nous intéressons à une topologie pour les réseaux de capteurs sans fil. Un réseau de capteurs sans fil peut être modélisé comme un graphe non orienté G = (V,E). Chaque sommet de V représente un capteur et une arête e = {u, v} dans E indique une transmission directe possible entre deux capteurs u et v. Contrairement aux dispositifs filaires, les capteurs sans fil ne sont pas a priori agencé en réseau. Une topologie doit être créée en sélectionnant des noeuds "dominants" qui vont gérer les transmissions. Les architectures qui ont été examinées dans la littérature reposent essentiellement sur les ensembles dominants connexes et les ensembles dominants faiblement connexes. Cette étude est consacrée aux ensembles indépendants faiblement connexes. Un indépendant S ⊂ V est dit faiblement connexe si le graphe GS = (V, [S, V \S]) est connexe, où [S, V \S] est l’ensemble des arêtes e = {u, v} de E avec u ∈ S et v ∈ V \S. Une topologie basée sur les ensembles faiblement connexes permet de partitionner l’ensemble des capteurs en trois groupes, les esclaves, les maîtres et les intermédiaires. Les premiers effectuent les mesures, les seconds rassemblent les données collectées et les troisièmes assurent les communications inter-groupes. Nous donnons d’abord quelques propriétés de cette structure combinatoire lorsque le graphe non orienté G est connexe. Puis nous proposons des résultats de complexité pour le problème de la recherche de l’indépendant faiblement connexe de cardinalité minimale (MWCISP). Nous décrivons également un algorithme d’énumération exact de complexité O∗(1.4655|V |) pour le MWCISP. Des tests numériques de cette procédure exacte sont présentés. Nous formulons ensuite le MWCISP comme un programme linéaire en nombres entiers. Le polytope associé aux solutions de ce problème est complètement caractérisé lorsque G est un cycle impair. Nous étudions des opérations de composition de graphes et leurs conséquences polyédrales. Nous introduisons des inégalités valides notamment les contraintes dites de multibord. Par la suite, nous développons un algorithme de coupes et branchement sous CPLEX pour résoudre ce problème en utilisant des heuristiques pour la séparation de nos familles de contraintes. Des résultats expérimentaux de ce programme sont exposés In this work, we focus on a topology for Wireless Sensor Networks (WSN). A wireless sensor network can be modeled as an undirected graph G = (V,E). Each vertex of V represents a sensor and an edge e = {u, v} in E implies a direct transmission between the two sensors u and v. Unlike wired devices, wireless sensors are not a priori arranged in a network. Topology should be made by selecting some sensor as dominators nodes who manage transmissions. Architectures that have been studied in the literature are mainly based on connected dominating sets and weakly connected dominating sets.This study is devoted to weakly connected independent sets. An independent set S ⊂ V is said Weakly Connected if the graph GS = (V, [S, V \S]) is connected, where [S, V \S] is the set of edges with exactly one end in S. A sensor network topology based on weakly connected sets is partition into three groups, slaves, masters and bridges. The first performs the measurements, the second gathers the collected data and the later provides the inter-group communications. We first give some properties of this combinatorial structure when the undirected graph G is connected. Then we provide complexity results for the problem of finding the minimum weakly connected independent set problem (MWCISP). We also describe an exact enumeration algorithm of complexity O∗(1.4655|V |) (for the (MWCISP)). Numerical tests of this exact procedure are also presented. We then present an integer programming formulation for the minimum weakly connected independent set problem and discuss its associated polytope. Some classical graph operations are also used for defining new polyhedra from pieces. We give valid inequalities and describe heuristical separation algorithms for them. Finally, we develop a branch-and-cut algorithm and test it on two classes of graphs

APA, Harvard, Vancouver, ISO, and other styles

44

Li, Le. "Online stochastic algorithms." Thesis, Angers, 2018. http://www.theses.fr/2018ANGE0031.

Full text

Abstract:

Cette thèse travaille principalement sur trois sujets. Le premier concentre sur le clustering en ligne dans lequel nous présentons un nouvel algorithme stochastique adaptatif pour regrouper des ensembles de données en ligne. Cet algorithme repose sur l'approche quasi-bayésienne, avec une estimation dynamique (i.e., dépendant du temps) du nombre de clusters. Nous prouvons que cet algorithme atteint une borne de regret de l'ordre et que cette borne est asymptotiquement minimax sous la contrainte sur le nombre de clusters. Nous proposons aussi une implémentation par RJMCMC. Le deuxième sujet est lié à l'apprentissage séquentiel des courbes principales qui cherche à résumer une séquence des données par une courbe continue. Pour ce faire, nous présentons une procédure basée sur une approche maximum a posteriori pour le quasi-posteriori de Gibbs. Nous montrons que la borne de regret de cet algorithme et celui de sa version adaptative est sous-linéaire en l'horizon temporel T. En outre, nous proposons une implémentation par un algorithme glouton local qui intègre des éléments de sleeping experts et de bandit à plusieurs bras. Le troisième concerne les travaux qui visent à accomplir des tâches pratiques au sein d'iAdvize, l'entreprise qui soutient cette thèse. Il inclut l'analyse des sentiments pour les messages textuels et l'implémentation de chatbot dans lesquels la première est réalisé par les méthodes classiques dans la fouille de textes et les statistiques et la seconde repose sur le traitement du langage naturel et les réseaux de neurones artificiels This thesis works mainly on three subjects. The first one is online clustering in which we introduce a new and adaptive stochastic algorithm to cluster online dataset. It relies on a quasi-Bayesian approach, with a dynamic (i.e., time-dependent) estimation of the (unknown and changing) number of clusters. We prove that this algorithm has a regret bound of the order of and is asymptotically minimax under the constraint on the number of clusters. A RJMCMC-flavored implementation is also proposed. The second subject is related to the sequential learning of principal curves which seeks to represent a sequence of data by a continuous polygonal curve. To this aim, we introduce a procedure based on the MAP of Gibbs-posterior that can give polygonal lines whose number of segments can be chosen automatically. We also show that our procedure is supported by regret bounds with sublinear remainder terms. In addition, a greedy local search implementation that incorporates both sleeping experts and multi-armed bandit ingredients is presented. The third one concerns about the work which aims to fulfilling practical tasks within iAdvize, the company which supports this thesis. It includes sentiment analysis for textual messages by using methods in both text mining and statistics, and implementation of chatbot based on nature language processing and neural networks

APA, Harvard, Vancouver, ISO, and other styles

45

Bergé, Pierre. "Algorithmes pour voyager sur un graphe contenant des blocages." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.

Full text

Abstract:

Nous étudions des problèmes NP-difficiles portant sur les graphes contenant des blocages.Nous traitons les problèmes de coupes du point de vue de la complexité paramétrée. La taille p de la coupe est le paramètre. Étant donné un ensemble de sources {s1,...,sk} et une cible t, nous proposons un algorithme qui construit une coupe de taille au plus p séparant au moins r sources de t. Nous nommons ce problème NP-complet Partial One-Target Cut. Notre algorithme est FPT. Nous prouvons également que la variante de Partial One-Target Cut, où la coupe est composée de noeuds, est W[1]-difficile. Notre seconde contribution est la construction d'un algorithme qui compte les coupes minimums entre deux ensembles S et T en temps $2^{O(plog p)}n^{O(1)}$.Nous présentons ensuite plusieurs résultats sur le ratio de compétitivité des stratégies déterministes et randomisées pour le problème du voyageur canadien.Nous prouvons que les stratégies randomisées n'utilisant pas de mémoire ne peuvent pas améliorer le ratio 2k+1. Nous apportons également des éléments concernant les bornes inférieures de compétitivité de l'ensemble des stratégies randomisées. Puis, nous étudions la compétitivité en distance d'un groupe de voyageurs avec et sans communication. Enfin, nous nous penchons sur la compétitivité des stratégies déterministes pour certaines familles de graphes. Deux stratégies, avec un ratio inférieur à 2k+1 sont proposées: une pour les graphes cordaux avec poids uniformes et l'autre pour les graphes où la taille de la plus grande coupe minimale séparant s et t est au plus k We study NP-hard problems on graphs with blockages seen as models of networks which are exposed to risk of failures.We treat cut problems via the parameterized complexity framework. The cutset size p is taken as a parameter. Given a set of sources {s1,...,sk} and a target $t, we propose an algorithm which builds a small edge cut of size p separating at least r sources from t. This NP-complete problem is called Partial One-Target Cut. It belongs to the family of multiterminal cut problems. Our algorithm is fixed-parameter tractable (FPT) as its execution takes $2^{O(p^2)}n^{O(1)}$. We prove that the vertex version of this problem, which imposes cuts to contain vertices instead of edges, is W[1]-hard. Then, we design an FPT algorithm which counts the minimum vertex (S,T)-cuts of an undirected graph in time $2^{O(plog p)}n^{O(1)}$.We provide numerous results on the competitive ratio of both deterministic and randomized strategies for the Canadian Traveller Problem. The optimal ratio obtained for the deterministic strategies on general graphs is 2k+1, where k is a given upper bound on the number of blockages. We show that randomized strategies which do not use memory cannot improve the bound 2k+1. In addition, we discuss the tightness of lower bounds on the competitiveness of randomized strategies. The distance competitive ratio for a group of travellers possibly equipped with telecommunication devices is studied. Eventually, a strategy dedicated to equal-weight chordal graphs is proposed while another one is built for graphs with small maximum (s,t)-cuts. Both strategies outperform the ratio 2k+1

APA, Harvard, Vancouver, ISO, and other styles

46

Norgren, Eric, and Johan Jonasson. "Investigating a Genetic Algorithm-Simulated Annealing Hybrid Applied to University Course Timetabling Problem : A Comparative Study Between Simulated Annealing Initialized with Genetic Algorithm, Genetic Algorithm and Simulated Annealing." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-186364.

Full text

Abstract:

Every semester universities around the world have to create new schedules. This task can be very complex considering that a number of constraints has to be taken into account, e.g. there should not exist any timetable clashes for students and a room cannot be double-booked. This can be very hard and time-consuming for a human to do by hand, which is why methods to automate this problem, the University Course Timetabling Problem, has been researched for many years. This report investigates the performance of a hybrid consisting of Genetic Algorithm and Simulated Annealing when solving the University Course Timetabling Problem. An implementation by Yamazaki & Pertoft (2014) was used for the Genetic Algorithm. Simulated Annealing used the Genetic Algorithm as base for its implementation. The hybrid runs the Genetic Algorithm until some breakpoint, takes the best timetable and uses it as an initial solution for the Simulated Annealing. Our results show that our implementation of Simulated Annealing performs better than the hybrid and magnitudes better than the Genetic Algorithm. We believe one reason for this is that the dataset used was too simple, the Genetic Algorithm might scale better as the complexity of the dataset increases.

APA, Harvard, Vancouver, ISO, and other styles

47

Potemine, Igor. "Arithmétique des corps globaux de fonctions et géométrie des schémas modulaires de Drinfeld." Grenoble 1, 1997. http://www.theses.fr/1997GRE10030.

Full text

Abstract:

La these est consacree a l'arithmetique des motifs purs de type de drinfeld-anderson pour les corps globaux de fonctions, ainsi qu'a la geometrie des schemas modulaires grossiers de drinfeld et a la construction explicite des corps de classes pour les corps globaux totalement imaginaires en caracteristique positive. Dans le premier chapitre, on donne un theoreme de classification pour les motifs purs de drinfeld-anderson sur une cloture algebrique d'un corps fini et on demontre des resultats sur leur fonctions l analogues aux theoremes de deligne et au theoreme de hasse et weil pour les courbes. On prouve egalement une conjecture globale de goss pour les fonctions l des faisceaux purs de drinfeld-anderson en s'appuyant sur un theoreme de taguchi-wan. Ensuite, on decrit explicitement les schemas grossiers des modules rationnels de drinfeld et on construit les modeles minimaux terminaux de ces schemas en utilisant les resultats de danilov et reid pour les varietes toriques. Dans le troisieme chapitre, on applique cette construction a la theorie du corps de classes. Plus precisement, on developpe une theorie de multiplication complexe des modules rationnels de drinfeld de rang arbitraire et on construit l'extension abelienne maximale d'un corps global totalement imaginaire de fonctions en utilisant un systeme de j-invariants fondamentaux et un systeme de fonctions de type de weber. On considere enfin quelques applications algorithmiques entre autres, un analogue de l'algorithme des courbes elliptiques de lenstra.

APA, Harvard, Vancouver, ISO, and other styles

48

Wang, Yuqiang. "Models and Algorithms for Some Combinatorial Optimization Problems: University Course Timetabling, Facility Layout and Integrated Production-Distribution Scheduling." Diss., Virginia Tech, 2007. http://hdl.handle.net/10919/28757.

Full text

Abstract:

In this dissertation, we address three different combinatorial optimization problems (COPs), each of which has specific real-life applications. Owning to their specific nature, these problems are different from those discussed in the literature. For each of these problems, we present a mathematical programming formulation, analyze the problem to determine its useful, inherent structural properties, and develop an efficient methodology for its solution by exploiting these properties. The first problem that we address is the course timetabling problem encountered at Virginia Tech. The course timetabling problem for a university is a difficult problem and has been studied by many researchers over the years. As a result, a plethora of models and approaches have been reported in the literature. However, most of these studies have focused on applications pertaining to course scheduling for a single or at most few departments of a university. The sheer size of the university-wide timetabling problem that we address, involving thousands of courses to be scheduled in hundreds of classrooms in each semester, makes it a challenging problem. We employ an appropriate decomposition technique that relies on some inherent structural properties of the problem both during the modeling and algorithmic development phases. We show the superiority of the schedules generated by our methodology over those that are currently being used. Also, our methodology requires only a reasonable amount of computational time in solving this large-size problem. A facility layout problem involving arbitrary-shaped departments is the second problem that we investigate in this dissertation. We designate this problem as the arbitrary-shaped facility layout problem (ASFLP). The ASFLP deals with arranging a given set of departments (facilities, workstations, machines) within the confines of a given floor space, in order to optimize a desired metric, which invariably relates to the material handling cost. The topic of facility planning has been addressed rather extensively in the literature. However, a major limitation of most of the work reported in the literature is that they assume the shape of a department to be a rectangle (or even a square). The approach that relies on approximating an arbitrary-shaped department by a rectangle might result in an unattractive solution. The key research questions for the ASFLP are: (1) how to accurately model the arbitrary-shaped departments, and (2) how to effectively and efficiently determine the desired layout. We present a mixed-integer programming model that maintains the arbitrary shapes of the departments. We use a meta-heuristic to solve the large-size instances of the ASFLP in a reasonable amount of time. The third problem that we investigate is a supply chain scheduling problem. This problem involves two stages of a supply chain, specifically, a manufacturer and one or more customers. The key issue is to achieve an appropriate coordination between the production and distribution functions of the manufacturer so as to minimize the sum of the shipping and job tardiness costs. We, first, address a single customer problem, and then, extend our analysis to the case of multiple customers. For the single-customer problem, we present a polynomial-time algorithm to solve it to optimality. For the multiple-customer problem, we prove that this problem is NP-hard and solve it by appropriately decomposing it into subproblems, one of which is solvable in polynomial time. We propose a branch-and-bound-based methodology for this problem that exploits its structural properties. Results of an extensive computational experimentation are presented that show the following: (1) our algorithms are efficient to use and effective to implement; and (2) significant benefits accrue as a result of integrating the production and distribution functions. Ph. D.

APA, Harvard, Vancouver, ISO, and other styles

49

Grandjean, Arnaud. "Introduction de non linéarités et de non stationnarités dans les modèles de représentation de la demande électrique résidentielle." Phd thesis, Ecole Nationale Supérieure des Mines de Paris, 2013. http://pastel.archives-ouvertes.fr/pastel-00817969.

Full text

Abstract:

La problématique développée dans la thèse est d'estimer, dans une démarche prospective et dans un but d'anticipation, les impacts en puissance induits par les ruptures technologiques et comportementales qui ne font pas aujourd'hui l'objet de mesures dans les panels. Pour évaluer les modifications sur les appels de puissance du parc résidentiel engendrées par ces profondes transformations,un modèle paramétrique, bottom-up, techno-explicite et agrégatif est donc nécessaire. Celui-ci serait donc destiné à la reconstitution, de manière non tendancielle, de la courbe de charge électrique résidentielle. Il permettrait ainsi de conduire la simulation de différents scénarios d'évolution contrastés. L'élaboration d'un tel modèle constitue le sujet de ce doctorat.Pour répondre à cette problématique, nous proposons une méthode conceptuelle originale de reconstitution de courbe de charge. Sa mise en application centrée sur la génération de foisonnement d'origine comportementale a conduit à la modélisation d'un certain nombre de concepts. Ce travail a abouti à l'élaboration d'un algorithme stochastique destiné à représenter le déclenchement réalistedes appareils domestiques. Différents cas d'application ont pu être testés et les résultats en puissance ont été étudiés. Plus particulièrement pour analyser le foisonnement visible à un niveau agrégé, nous avons mis en place une méthodologie nouvelle basée sur une distance adaptée aux courbes de charge. Finalement, nous avons cherché à identifier des comportements réels d'usage des appareils. Pour cela, nous avons conduit différents travaux de classification de courbes de charge.

APA, Harvard, Vancouver, ISO, and other styles

50

Mathault, Jessy. "Adaptation d'un algorithme de deuxième ordre pour l'analyse haute-résolution de courbes électrochimiques." Master's thesis, Université Laval, 2018. http://hdl.handle.net/20.500.11794/30266.

Full text

Abstract:

Ce mémoire présente une nouvelle méthode d'analyse des courbes de voltampérométrie cyclique. Cette méthode utilise deux algorithmes distincts afin de permettre la caractérisation automatique et précise des pics gaussiens d'oxydoréduction qui sont liés à la concentration des molécules en solution. En premier lieu, des améliorations significatives sont apportées à un algorithme de suppression de la courbe de fond qui fonctionne par approximation polynomiale itérative. Avec les améliorations proposées, l'algorithme isole les pics d'oxydoréduction à partir des mesures de voltampérométrie cyclique automatiquement. La variation de l'amplitude des pics en fonction de la concentration est alors mieux conservée et les erreurs d'estimation sont diminuées par rapport à l'algorithme initial. Ensuite, le développement d'un algorithme qui permet de caractériser des pics gaussiens basé sur l'algorithme de deuxième ordre MUSIC est présenté. Cet algorithme est adapté de manière à caractériser avec une haute précision le nombre, la position, la largeur et l'amplitude des pics d'oxydoréduction. Finalement, les performances de cet algorithme sont comparées à celles d'autres algorithmes similaires à l'aide de courbes simulées et expérimentales. L'algorithme proposé permet une meilleure caractérisation des pics sans chevauchement ainsi que des pics déformés. Il permet aussi de diminuer la fréquence des fausses détections et d'obtenir une haute précision de la mesure de position, et ce même lorsque les signaux sont bruités. This master's thesis describes a new method for analyzing cyclic voltammetry curves for an efficient peak detection and automatic baseline substraction. This method uses two distinct algorithms for a precise characterization of Gaussian redox peaks which are correlated with molecules' concentration in a solution. First, significant improvements are made to an existing algorithm that uses iterative polynomial approximations to suppress the baseline automatically from the voltammetric curves. With these enhancements, the algorithm extracts redox peaks from cyclic voltammetry measurements automatically and allows a better representation of the variation of peak's amplitude according to concentration. In addition, the approximation errors are reduced compared to the initial algorithm. Then, the development of an algorithm for characterizing Gaussian peaks based on the MUSIC second-order algorithm is presented. This algorithm is adapted to characterize the number, position, width and amplitude of redox peaks with high accuracy. Finally, the performances of this algorithm are compared with those of other similar algorithms using simulated and experimental curves. The suggested algorithm leads to a better characterization of non-overlapping peaks as well as distorted peaks. It also reduces the frequency of false detections and allows the precise measurement of peaks' positions in noisy signals.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Algorithmes de course'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles