Spelling suggestions: "subject:"ist A"" "subject:"list A""
341 |
Dinaminės duomenų struktūros ir kai kurių jų algoritmų realizavimas rodyklėmis / Dynamic Data Structures And The Realisation Of Some Algorithms By PointersSuchaževskaja, Tatjana 08 June 2005 (has links)
The present research paper deals with the comparison of static and dynamic data structures: static array, dynamic array, pointers array - class TList (Delphi) and dynamic doubly linked list, created with the help of recursive record.To compare the above mentioned structures, sorting (Bubble) and convex hull creation algorithms (Graham, Endrew) are realized, with the time of their implementation analysed. The algorithm of sorting (Bubble) is realized by four ways: static array, dynamic array, pointers array (class TList) and a dynamic doubly linked list, created with the help of recursive record.The algorithms of convex hull creation (Graham, Endrew) is realized by three ways: static array, dynamic array and pointers array (TList).The research paper also describes the pointers array class TList (Delphi), its properties and methods. The sorting method Sort of this class is compared with the sorting method of a “Bubble”. Using class templates, a universal class MList (C++) was created for work with dynamic linear linked lists.
|
342 |
L’évaluation de la loi du 1er février 2012 concernant l’acquisition du plein exercice pour les médecins à diplôme hors Union européenne / The exercise authorization procedure : the evaluation of the law of 1 February 2012 on the acquisition of the full exercise for doctors with a diploma outside the European UnionChen, Xin 02 October 2017 (has links)
La Procédure d'Autorisation d'Exercice est un dispositif qui concerne l'ensemble des praticiens à diplôme hors Union Européenne. Elle a été instaurée en 2007 par la loi CMU du 27 juillet 1999, complétée par la Loi de Financement de la Sécurité Sociale du 21 décembre 2008, modifiée par la loi 2012-157 du 1er février 2012. La dernière loi concernée, la loi n°2016-1888 du 28 décembre 2016 de modernisation, de développement et de protection des territoires de montagne, met fin à la régularisation de ces praticiens. Depuis l'exécution de la loi 2012-157 du 1er février 2012 jusqu'à la fin de l'année 2016, la Procédure d'Autorisation d'Exercice compte 26562 inscriptions et 14647 présentations dont 4866 reçus aux Epreuves de Vérification des Connaissances à la Procédure d'Autorisation d'Exercice. Nous avons étudié les résultats des Epreuves de Vérification des Connaissances avec des analyses approfondies. Entre 2012 et 2016, la liste A a reçu le plus grand nombre de candidats aux Epreuves de Vérification des Connaissances, soit 21123 inscriptions, 10007 présentations. Le taux de réussite de la liste A varie entre 15% et 19%, sachant que la liste A est une liste qui recueille tous les nouveaux arrivants, les Epreuves de Vérification des Connaissances pour cette liste est un concours. La liste B a reçu 562 inscriptions, dont 413 présentations entre 2012 et 2016 avec un taux de réussite de 24% à 41%. Les épreuves pour cette liste sont sous forme d'examen. La liste C a reçu 4877 inscriptions, dont 4227 présentations entre 2012 et 2016 et le taux de réussite est de 56% à 80%. La liste C est aussi un examen qui recueille tous les praticiens à diplôme hors Union Européenne qui sont déjà installés en France. Nous avons observé que la disparition de la liste C est en partie due au dispositif de la Procédure d'Autorisation d'Exercice qui permet la régularisation des praticiens à diplôme hors Union Européenne. La loi 2012-157 du 1er février 2012 qui modifie les conditions et le périmètre de participation des candidats aux Epreuves de Vérification des Connaissances est une des causes de transfert des candidats de la Liste A à la Liste C. Enfin, les praticiens inscrits au tableau de l'Ordre des médecins, et provenant de la Procédure d'Autorisation d'Exercice, occupent une proportion qui est d'environ 10% dans certains départements en France. Ce chiffre montre le nombre de ces praticiens est quasiment aussi important qu'avant et que leur présence est demandée dans la France entière. Dans certains départements, nous avons pu constater que la présence de praticiens à diplôme hors Union Européenne augmente la densité médicale territoriale en France, démontrant l'importance de leur présence au niveau local, ainsi que dans les zones rurales et de montagnes. Le seul contrôle de l'entrée des praticiens à diplôme hors Union Européenne n'est pas suffisant ; la formation continue de ces praticiens devrait être envisagée afin d'améliorer leur niveau médical d'exercice, et la réorientation territoriale d'installation pourrait être une solution qui augmenterait l'offre de soins au niveau local. / The "Authorization Exercise Procedure" is a device that concerns all doctors with diplomas outside the European Union. It was introduced in 2007 by law "CMU of 27 July 1999", supplemented by "Law of Social Security Financing" of 21 December 2008, amended by the Law "2012-157 of 1 February 2012", The last law concerned, was No. 2016-1888 of 28 December 2016 on the modernization, development and protection of mountain territories, put an end to the regularization of these doctors. Since the implementation of Law 2012-157 from 1 February 2012 to the end of 2016, the Fiscal Authorization Procedure has 26,562 registrations and 14,647 presentations, of which 4866 were received in the Knowledge Verification Exercise Authorization Procedure. We examined the results of the Knowledge Verification tests with in-depth analyzes. Between 2012 and 2016, List A received the highest number of candidates for the Knowledge Test, 21123 registrations, 10007 presentations. The success rate of List A varies between 15% and 19%, knowing that List A is a list that collects all newcomers, the Knowledge Testing tests for this list is a competition. List B received 562 entries, including 413 entries between 2012 and 2016 with a pass rate of 24% to 41%. The tests for this list are in the form of an examination. List C received 4877 entries, of which 4,227 entries between 2012 and 2016 and the success rate is 56% to 80%. List C is also an examination that gathers all the doctors with diplomas outside the European Union who are already established in France. We have observed that the disappearance of the list C is partly due to the device of the Exercise Authorization Procedure which allows the regularization of the doctors with diploma outside the European Union. Law 2012-157 of February 1, 2012, which modifies the conditions and the perimeter of participation of the candidates in the tests of verification of the Knowledge is one of the causes of transfer of the candidates from List A to List C. Finally, the doctors registered on the board of the French Medical Association, and coming from The Exercise Authorization Procedure, occupy a proportion which is about 10% in certain departments in France. This figure shows the number of these doctors is almost as important as before and that their presence is demanded in the whole of France. In some départements, we have seen that the presence of doctors with diplomas outside the European Union increases the territorial medical density in France, demonstrating the importance of their presence at the local level, as well as in rural and mountain areas. The only control of the entry of doctors with diplomas outside the European Union is not sufficient; The continuing training of these doctors should be considered in order to improve their medical level of practice and the territorial reorientation of the facility could be a solution that would increase the supply of care at the local level.
|
343 |
Event-Driven Motion Compensation in Positron Emission Tomography: Development of a Clinically Applicable MethodLangner, Jens 28 July 2009 (has links)
Positron emission tomography (PET) is a well-established functional imaging method used in nuclear medicine. It allows for retrieving information about biochemical and physiological processes in vivo. The currently possible spatial resolution of PET is about 5 mm for brain acquisitions and about 8 mm for whole-body acquisitions, while recent improvements in image reconstruction point to a resolution of 2 mm in the near future. Typical acquisition times range from minutes to hours due to the low signal-to-noise ratio of the measuring principle, as well as due to the monitoring of the metabolism of the patient over a certain time. Therefore, patient motion increasingly limits the possible spatial resolution of PET. In addition, patient immobilisations are only of limited benefit in this context. Thus, patient motion leads to a relevant resolution degradation and incorrect quantification of metabolic parameters.
The present work describes the utilisation of a novel motion compensation method for clinical brain PET acquisitions. By using an external motion tracking system, information about the head motion of a patient is continuously acquired during a PET acquisition. Based on the motion information, a newly developed event-based motion compensation algorithm performs spatial transformations of all registered coincidence events, thus utilising the raw data of a PET system - the so-called `list-mode´ data. For routine acquisition of this raw data, methods have been developed which allow for the first time to acquire list-mode data from an ECAT Exact HR+ PET scanner within an acceptable time frame. Furthermore, methods for acquiring the patient motion in clinical routine and methods for an automatic analysis of the registered motion have been developed. For the clinical integration of the aforementioned motion compensation approach, the development of additional methods (e.g. graphical user interfaces) was also part of this work.
After development, optimisation and integration of the event-based motion compensation in clinical use, analyses with example data sets have been performed. Noticeable changes could be demonstrated by analysis of the qualitative and quantitative effects after the motion compensation. From a qualitative point of view, image artefacts have been eliminated, while quantitatively, the results of a tracer kinetics analysis of a FDOPA acquisition showed relevant changes in the R0k3 rates of an irreversible reference tissue two compartment model. Thus, it could be shown that an integration of a motion compensation method which is based on the utilisation of the raw data of a PET scanner, as well as the use of an external motion tracking system, is not only reasonable and possible for clinical use, but also shows relevant qualitative and quantitative improvement in PET imaging. / Die Positronen-Emissions-Tomographie (PET) ist ein in der Nuklearmedizin etabliertes funktionelles Schnittbildverfahren, das es erlaubt Informationen über biochemische und physiologische Prozesse in vivo zu erhalten. Die derzeit erreichbare räumliche Auflösung des Verfahrens beträgt etwa 5 mm für Hirnaufnahmen und etwa 8 mm für Ganzkörperaufnahmen, wobei erste verbesserte Bildrekonstruktionsverfahren eine Machbarkeit von 2 mm Auflösung in Zukunft möglich erscheinen lassen. Durch das geringe Signal/Rausch-Verhältnis des Messverfahrens, aber auch durch die Tatsache, dass der Stoffwechsel des Patienten über einen längeren Zeitraum betrachtet wird, betragen typische PET-Aufnahmezeiten mehrere Minuten bis Stunden. Dies hat zur Folge, dass Patientenbewegungen zunehmend die erreichbare räumliche Auflösung dieses Schnittbildverfahrens limitieren. Eine Immobilisierung des Patienten zur Reduzierung dieser Effekte ist hierbei nur bedingt hilfreich. Es kommt daher zu einer relevanten Auflösungsverschlechterung sowie zu einer Verfälschung der quantifizierten Stoffwechselparameter.
Die vorliegende Arbeit beschreibt die Nutzbarmachung eines neuartigen Bewegungskorrekturverfahrens für klinische PET-Hirnaufnahmen. Mittels eines externen Bewegungsverfolgungssystems wird während einer PET-Untersuchung kontinuierlich die Kopfbewegung des Patienten registriert. Anhand dieser Bewegungsdaten führt ein neu entwickelter event-basierter Bewegungskorrekturalgorithmus eine räumliche Korrektur aller registrierten Koinzidenzereignisse aus und nutzt somit die als "List-Mode" bekannten Rohdaten eines PET Systems. Für die Akquisition dieser Daten wurden eigens Methoden entwickelt, die es erstmals erlauben, diese Rohdaten von einem ECAT Exact HR+ PET Scanner innerhalb eines akzeptablen Zeitraumes zu erhalten. Des Weiteren wurden Methoden für die klinische Akquisition der Bewegungsdaten sowie für die automatische Auswertung dieser Daten entwickelt. Ebenfalls Teil der Arbeit waren die Entwicklung von Methoden zur Integration in die klinische Routine (z.B. graphische Nutzeroberflächen).
Nach der Entwicklung, Optimierung und Integration der event-basierten Bewegungskorrektur für die klinische Nutzung wurden Analysen anhand von Beispieldatensätzen vorgenommen. Es zeigten sich bei der Auswertung sowohl der qualitativen als auch der quantitativen Effekte deutliche Änderungen. In qualitativer Hinsicht wurden Bildartefakte eliminiert; bei der quantitativen Auswertung einer FDOPA Messung zeigte sich eine revelante Änderung der R0k3 Einstromraten eines irreversiblen Zweikompartment-Modells mit Referenzgewebe. Es konnte somit gezeigt werden, dass eine Integration einer Bewegungskorrektur unter Zuhilfenahme der Rohdaten eines PET Systems sowie unter Nutzung eines externen Verfolgungssystems nicht nur sinnvoll und in der klinischen Routine machbar ist, sondern auch zu maßgeblichen qualitativen und quantitativen Verbesserungen in der PET-Bildgebung beitragen kann.
|
344 |
Cognitive bias modification : the effect of mental imagery on reaction rate to emotionally valenced stimuliKunstler, Erika C. S. 08 1900 (has links)
A normative experimental study was undertaken to establish whether engaging in positive, negative,
and neutral mental imagery affected the reaction rate of participants to positive, negative, and
neutral word stimuli. The sample consisted of computer literate, English speaking participants with
no history of clinical disorders. A total of 80 participants took part in the study, with 40
participants from either gender. The results of a factorial ANOVA indicated that the type of mental
imagery engaged in had a significant effect on the rate at which participants responded to stimuli
(p=.00023, F=8.4057), whilst the emotional valence of the stimuli did not have a significant
effect (p=.30503, F=1.1877). However, the interaction between the type of mental imagery and
the emotional valence of the stimuli was highly significant (p=.00794, F=3.4576), thereby
indicating that engaging in positive or negative mental imagery did bias participants towards a
faster reaction rate to positive or negative stimuli respectively. / M.A. (Psychology) / Psychology
|
345 |
ISO 9001 Registration for the Electronic Hardware Fabrication Process at the Jet Propulsion LaboratoryBonner, J. K. “Kirk”, de Silveira, Carl 10 1900 (has links)
International Telemetering Conference Proceedings / October 26-29, 1998 / Town & Country Resort Hotel and Convention Center, San Diego, California / More and more companies and organizations are recognizing the benefits to be gained by achieving ISO 9000 registration. An effort is underway at JPL to become ISO 9001 registered. To facilitate this activity, the entire laboratory has been divided into processes, each one having a designated process owner. This paper concentrates more specifically on one of these processes, namely, the Packaging and Fabrication of Electronic Hardware (PAFEH), and the effort being undertaken to ensure that this process will successfully pass registration. A comprehensive approach is being utilized by the Electronic Packaging and Fabrication Section to bring this about.
|
346 |
Experiences of chronic patients about long waiting time at a community health care centre in the Western CapeTana, Vuyiswa Veronica 03 1900 (has links)
Thesis (MCurr)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: The objectives of this study were to explore patients’ experiences about long waiting time at the Vanguard Community Health Care Centre in the Western Cape and to explore possible solutions for this problem from the patients’ perspective. A qualitative research approach was applied. A sample size of (n=12) was drawn from a total population of 2829 (N=2829) using a non-random convenient sampling technique. A semi-structured interview guide was designed based on the objectives of the study and validated by experts in the field before data collection took place. Approval for the study was obtained from the Ethics Committee at the faculty of Health Sciences, Stellenbosch University and from the facility manager of health centre where the study was to be undertaken.
The presentation of the results was categorised into themes and sub-themes that emerged from the data analysis. According to the findings in chapter 4 the themes that emerged were:
Causes of long waiting time
Areas of concern where waiting occurs most
Emotions experienced when waiting long for service
Possible solutions to waiting long for service
The findings support the conceptual framework developed for the purpose of this study which includes the Patient’s Bill of Rights, the Principles of Batho Pele, Quality Care, Patients’ Representation and Patient satisfaction. The results of the study suggests that the conceptual framework needs to be implemented as a guideline to address the problems of long waiting time with the input from the participants’ opinions about possible solutions to be incorporated to the problem of long waiting time at the community health centre. / AFRIKAANSE OPSOMMING: Die doelwitte van die studie was om pasiente se gevoelens oor lang wagtye by Vanguard Gemeenskapsgesondheidsentrum in die Wes-Kaap te ondersoek en om moontlike oplossings vir hierdie probleem vanaf die pasient se perspektief te bepaal ‘n Kwalitatiewe navorsingsbenadering is gebruik. ‘n Steekproefgrootte van (n=12) is verkry vanaf ‘n totale bevolking van 2829 (N= 2829) deur die gebruik van ‘n nie-ewekansige gerieflike steekproefneming tegniek. ‘n Semi-gestruktureerde onderhoudgids is ontwerp gebaseer op die doelwitte van die studie. Die onderhoudgids is geldig bevind deur spesialiste in die gebied voor data insameling plaasgevind het. Goedkeuring vir die studie is verkry van die Etiese Komitee by die Fakulteit Gesondheidswetenskappe, Stellenbosch Universiteit en van die bestuurder van die gesondheidsentrum waar die studie uitgevoer sou word.
Resultate is rangskik in temas en subtemas wat afgelei is van die data analise. Die volgende temas is bepaal vanuit Hoofstuk 4 se bevindinge:
Redes vir lang wagtye
Areas waar lang wagtye voorkom
Emosies ondervind wanneer lank gewag moet word vir diens
Moontlike oplossings vir lang wagtye
Die bevindinge ondersteun die konseptuele raamwerk ontwikkel vir die doel van die studie wat die Handves van Regte vir pasiente, die beginsels van Batho Pele, Kwaliteitsorg, Pasient verteenwoordiging en Pasienttevredenheid insluit. Die bevindinge van die studie dui aan dat die konseptuele raamwerk geimplementeer moet word as riglyn om die probleme wat ervaar word met lang wagtye aan te spreek. Die deelnemers se menings oor moontlike oplossings moet deel moet wees van die aanspreek van die probleem van lang wagtye in die gemeenskapsgesondheidsentrum.
|
347 |
Reproductive biology and ex situ conservation of the genus Restrepia (Orchidaeae)Millner, Helen Jean January 2013 (has links)
The genus Restrepia is well known to orchid enthusiasts but its micromorphology has not been described, and its pollination and breeding systems have not been investigated. The aim of this investigation was, therefore, to add to existing knowledge so that the resultant data could be used to facilitate ex situ conservation initiatives. A detailed electron microscopy study (SEM) of the floral organs was performed. This confirmed the structure of the dorsal sepal and lateral petal osmophores, their secretory nature together with that of the synsepal and the labellum. It was postulated how, by manipulating different labellar surface textures, the flower might use these ‘tactile guides’ to steer the insect (fly) through the flower. The cirrhi were postulated to help by destabilising the pollinator in flight, trapping it and bringing about pollination. The papillate structure of the calli was established and their optical properties investigated. Media comparison investigations established that Western medium supported the highest germination rates and, with the addition of banana supplement, the highest rates for seedling growth and development. This represented the first protocol for axenic germination of Restrepia in the literature (Millner et al., 2008) and provided a tested methodology for investigating breeding systems and producing Restrepia plant material for both scientific and horticultural purposes. Self-pollinations were found to produce fewer embryos compared to cross-pollinations. The operation of self-incompatibility (SI) was confirmed by the study of pollen tube growth which further confirmed the time interval between pollination and fertilisation. A time line from pollination/fertilisation to flowering was established. The type of SI in operation was best explained by gametophytic incompatibility. This demonstrated that it was possible to raise Restrepia hybrids and species from seed, by performing intraspecific crosses so helping to preserve them for posterity and relieve pressure on wild populations. Narrow endemic Restrepia species face combined threats from habitat loss, habitat degradation and problems of viable seed production due to the effects of SI and inbreeding depression (ID). Recently developed online resources, such as GeoCAT, were used to perform a Red List assessment in order to identify the degree of threat individual species faced, both globally and nationally. All species were classified as facing substantial levels of threat; although this was lessened for populations in protected habitats. Conservation is needed for cultivated collections as well as these wild populations by keeping alive existing knowledge and expertise in growing these species.
|
348 |
Hur uppfattar farmaceuter tillgänglig information om patienters aktuella läkemedel och hur ser de på övergången till en gemensam nationell läkemedelslista?Grahn, Karin January 2017 (has links)
Läkare, sjuksköterskor, farmaceuter, patienter och patienters anhöriga är alla delar av den kedja som ska se till så att läkemedelsanvändning sker på ett säkert sätt. Så många inblandade och i så många olika sammanhang gör att läkemedelsanvändning kan vara svårt att hantera. 2014 skrevs det ut 102 913 130 recept i Sverige (1). Fram till 2014 hade ca 850 000 felaktiga recept korrigerats av farmaceuter varje år (2). Att korrigera recept är en nödvändig del som ingår i farmaceutens skyldighet och ansvar vilket regleras i svensk lagstiftning (3). Farmaceuten är en del av vårdkedjan som skall tillse att patienten har en korrekt och säker behandling med läkemedel (4). Tillgång till en nationell gemensam läkemedelslista för alla berörda parter, förskrivare, farmaceut, patient och övrig vårdpersonal skulle kanske kunna komma tillrätta med felaktigheter i förskrivningar och därmed öka patientsäkerheten (4). Tidigare studier har genomförts som behandlar läkarens syn på en gemensam lista och även patientens syn på eHälsoarbete vilket till viss del belyser en gemensam lista (5)(6) men inga studier har hittats om hur en gemensam lista kommer att påverka farmaceuternas vardag vilket ett av syftena med detta arbete har varit. För att uppnå syftet genomfördes en enkätundersökning med farmaceuter verksamma på ett antal apotek där de fick delge sina tankar både kring den information om patienters aktuella läkemedel som finns tillgänglig idag, bland annat genom receptdepån och sina tankar kring en nationell gemensam läkemedelslista. Resultat av undersökning gör gällande att det förekommer fel i receptdepån både med avseende på saknad information, felaktigheter i recept och att recept förekommer mer än en gång och att de finns med trots att patienten inte skall använda dem mer. Majoriteten av farmaceuterna var eniga om att en nationell gemensam läkemedelslista skulle hjälpa dem i deras arbete för att öka patientsäkerheten men huruvida den kommer att lösa alla problem som förekommer i receptdepån får framtiden utvisa. / Doctors, nurses, pharmacists, patients and next of kin are all parts of the chain that is needed to make sure that the use of medication is safe and appropriate for the patient. That many people involved and in many different settings can make the use of medication difficult to manage. In the year 2014 there were 102 913 130 prescriptions made out to patients in Sweden. Up to the year 2014 850 000 corrections had been made to prescriptions with faults in them by pharmacists each year. To correct prescriptions is an essential part of the pharmacist’s obligations and responsibility, a responsibility that is regulated in Swedish law. The pharmacist is the last part of the chain that has the possibility to adjust anything that is wrong with medications and the use of it before it is in the patient’s own hands. The access to a nationally shared medication list for all involved parties might solve some of the problems that faces the responsible parties when it comes to dealing with patients and their new and ongoing medications and in that way be able to increase the safety around mediation for the patient in need. Although the survey conducted as part of this paper focuses on pharmacists the background tries to explain in what way the different professions come in contact with medicines and how they would perhaps benefit from a shared list. The paper also tries to give a little insight to what kind of problems there could be related to prescriptions. In Sweden we have come a rather long way in the use of computers and the use of internet in the field of eHealth compared to other countries. The paper tries to show how the problem surrounding prescription of medicine is handled in the other countries of Scandinavia. Earlier studies have been conducted that looks at shared lists from the doctors view and also studies have been conducted that looks upon eHealth for patients partly in view of shared medication lists. No studies have been found that looks specifically at how pharmacists feel about it and how such a list would benefit them in their work to secure patient safety, hence this paper. In order to reach the papers purpose a survey was performed with pharmacists employed at different pharmacies in the southern part of Sweden. The result of the survey showed that there are indeed problems with prescriptions in the prescription repository and the majority of the pharmacists agreed that a shared medication list could help them in their work to secure patient safety when releasing prescribed medication. Although the pharmacist agreed for the most part in the benefits of such a list they did not know if it would solve all problems, which is for the future to decide.
|
349 |
Turordningsreglerna : En bestämmelse för att skydda den svagare arbetstagaren eller ett exempel på strukturell diskriminering? / The regulations in § 22 of the law regarding employment protection : a decision making process to protect the vulnerable employee, or a clear example of a structural discrimination?Mattsson, Tora January 2017 (has links)
Abstract When an employer need to fire employees because of redundancy it has been found out that foreign-born workers are more negative affected than workers who is born in Sweden. The employer can apply several of provisions of 22 § LAS to create the case list. The regulations have in some cases been criticized to contribute to a structural discrimination on the Swedish labour market. The purpose of this study is to examine how the employer in different ways can affect the case list and examine whether the rules can be an example of structural discrimination, and how this in turn may affect the foreign-born workers. A legal dogmatic method has been applied to investigate the legal situation. And addition have also been made from a legal sociological method to create a picture to see how the situation for foreign-born employees looks on the Swedish labour market. The results of the study showed that the employer has great potential to influence the case list and that the employers right to lead the work is a strong principle. The biggest restriction in the employers right to lead the work is in the regulation that says that decision cannot be discriminatory. If the employer would make a decision that is disadvantage for some groups, there must be a factual statement for the decision. Furthermore, the study also concluded that there is a form of structural discrimination from the regulation of 22 § LAS. The structural discrimination is especially showed in how the law is constructed, and in norms and values that was held by employers and institutions.
|
350 |
Complexité des homomorphismes de graphes avec listesLemaître, Adrien 04 1900 (has links)
Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme.
Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées.
Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2. / Constraint satisfaction problems, consisting in assigning values to variables while respecting a set of constraints, form a large class of natural problems. In order to study the complexity of these problems, it is convenient to see them as homomorphism problems on relational structures. One current research topic is to characterise complexity classes where the homomorphism problem belongs. The ultimate goal is to confirm conjectures that bind together algebraic properties of the relationnal structure and complexity of the homomorphism problem.
At first, the thesis characterizes digraphs which generate FO list-homomorphism problems. It is shown that in the particular case of telescopic digraphs, conjectures binding together algebra and complexity are confirmed.
Subsequently, we characterize graphs which generate arc-consistency solvable list-homomorphism problems. We introduce the notion of monochromatic polymorphism and we propose a simple algorithm which solves the list-homomorphism problem if the target graph admits a monochromatic TSI polymorphism of arity k for every k ≥ 2.
|
Page generated in 0.0575 seconds