Thesis (PhD (Logistics))--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: Computerised sugarcane harvest scheduling decision support is an active fi eld of research which ties in closely with the broader problem of automating and streamlining the various activities in the sugar supply chain. In this dissertation, the problem of providing decision support with respect to sugarcane harvesting decisions is defined within a number of contexts, each representing a typical kind of organisation of sugarcane farmers into a cohesive decision making unit with its speci fic requirements and limitations that exist in practice. A number of variations relevant to these contexts of an overarching tactical sugarcane harvest scheduling problem (THSP) are considered and solved in this dissertation. The THSP is the problem of providing objective, responsible decision support to persons charged with the task of determining optimal harvesting dates for a set of sugarcane fields across an entire season. Sugarcane fields typically diff er in terms of the age, variety, life-cycle stage and in many other properties of the cane grown on them. The growth of sugarcane crops may also be a ffected by environmental conditions such as accidental fires, frosts or storms which have a detrimental e ffect on crop-value. Since sugarcane is a living organism, its properties change over time, an so does the potential pro t associated with it. The practicalities of farming cause further complication of the problem (for example, seasonal changes alter the conditions under which the crop is harvested and transported). The rainy season carries with it the added cost of disallowing long-range vehicles to drive into the fields, forcing the unloading and reloading of cane at so-called loading zones. Other considerations, such as the early ploughing out of fields to allow them to fallow before being replanted, compounds the THSP into a multi-faceted difficult problem requiring efficient data management, mathematical modelling expertise and efficient computational work. In the literature the THSP has been viewed from many different standpoints and within many contexts, and a variety of operations research methodologies have been employed in solving the problem in part. There is, however, no description in the literature of a solution to the THSP that takes the negative e ffects of extreme environmental conditions on the quality of a harvesting schedule into account in a scienti fically justifi able manner; most models in the literature are based on optimising sucrose yield alone under normal conditions, rendering weak schedules in practice. The scope of the modelling and solution methodologies employed in this dissertation towards solving the THSP is restricted to integer programming formulations and approximate solution methods. The parameters associated with these models were determined empirically using historical data, as well as previous work on deterioration of sugarcane following environmental and other events. The THSP is solved in this dissertation by designing a generic architecture for a conceptual decision support system (DSS) for the THSP in the various contexts referred to above, which is capable of accommodating the e ects of extra-ordinary environmental conditions, as well as the introduction of a computer-implemented version of a real DSS for the THSP conforming to the framework of this generic architecture. The DSS building blocks include prediction models for sugarcane yield, sugarcane recoverable value under normal circumstances, the costs associated with a harvesting schedule and the negative e ects on sugarcane recoverable value of extraordinary environmental conditions. The working of the DSS is based on a combinatorial optimisation model resembling the well-known asymmetric traveling salesman problem with time-dependent costs which is solved approximately by means of an attribute-based tabu search in which both local and global moves have been incorporated. The DSS is also validated by experienced sugarcane industry experts in terms of the practicality and quality of the schedules that it produces. / AFRIKAANSE OPSOMMING: Gerekenariseerde besluitsteun vir die skedulering van suikerriet-oeste is 'n aktiewe navorsingsveld wat nou verwant is aan die bre ër probleem van die outomatisering en vaartbelyning van 'n verskeidenheid aktiwiteite in die suikervoorsieningsketting. Die probleem van die daarstelling van steun rakende suikkerriet oestingsbesluite word in hierdie proefskrif in 'n aantal kontekste oorweeg, elk met betrekking tot 'n tipiese soort organisasie van suikerrietboere in 'n samehorige besluitnemingseenheid met sy spesi eke vereistes en beperkings in die praktyk. Verskeie variasies van 'n oorkoepelende taktiese suikerriet-oesskeduleringsprobleem (TSOSP) wat in hierde kontekste relevant is, naamlik die probleem om objektiewe, verantwoordbare steun aan besluitnemers te bied wat verantwoordelik is vir die bepaling van optimale oesdatums vir 'n versameling suikerrietplantasies oor die bestek van 'n hele seisoen, word in hierdie proefskrif bestudeer en opgelos. Suikerrietplantasies verskil tipies in terme van ouderdom, gewastipe, posisie in die lewensiklus, en vele ander eienskappe van die suikerriet wat daar groei. Omgewingstoestande, soos onbeplande brande, ryp of storms, het verder ook 'n negatiewe impak op die waarde van suikerriet op sulke plantasies. Omdat suikerriet 'n lewende organisme is, verander die eienskappe daarvan oor tyd, en so ook die potensi ele wins wat daarmee geassosieer word. Boerderypraktyke bemoeilik verder die skeduleringsprobleem onder beskouing (seisoenale veranderings beïnvloed byvoorbeeld die wyse waarop suikerriet ge-oes en vervoer word). Addisionele koste gaan voorts met die re ënseisoen gepaard, omdat die plantasies dan nie toeganklik is vir langafstand transportvoertuie nie en suikerriet gevolglik na spesiale laaisones gekarwei moet word voordat dit op hierdie voertuie gelaai kan word. Ander oorwegings, soos die vroe ë uitploeg van plantasies sodat die grond kan rus voordat nuwe suikerriet aangeplant word, veroorsaak dat die TSOSP 'n moeilike multi-faset probleem is, wat goeie databestuur, wiskundige modelleringsvernuf en doeltreff ende rekenaarwerk vereis. Die TSOSP word in die literatuur vanuit verskillende standpunte en in verskeie kontekste oorweeg, en 'n aantal uiteenlopende operasionele navorsingsmetodologie ë is al ingespan om hierdie probleem ten dele op te los. Daar is egter geen poging in die literatuur om 'n oplossing vir die TSOSP daar te stel waarin daar op 'n wetenskaplik-verantwoordbare wyse voorsiening gemaak word vir die negatiewe e ffekte wat uitsonderlike omgewingstoestande op die kwaliteit van oesskedules het nie; die meeste modelle in die literatuure is op slegs sukrose-opbrengs onder normale omstandighede gebaseer, wat lei na swak skedules in die praktyk. Die bestek van die wiskundige modellerings- en gepaardgaande oplossings-metodologie ë word in hierdie proefskrif vir die TSOSP beperk tot onderskeidelik heeltallige programmeringsformulerings en die bepaling van benaderde oplossings deur lokale soekprosedures. Die parameters wat met hierdie modelle en soekmetodes geassosieer word, word empiries bepaal deur gebruikmaking van historiese data asook bestaande werk oor die degradering van suikerriet as gevolg van omgewings- en ander eksterne faktore. Die TSOSP word in hierdie proefskrif opgelos deur die ontwerp van 'n generiese argitektuur vir 'n konseptuele besluitsteunstelsel (BSS) vir die TSOSP in die onderskeie kontekste waarna hierbo verwys word en wat die e ekte van uitsonderlike omgewingsfaktore in ag neem, asook die daarstelling van 'n rekenaar-ge ïmplementeerde weergawe van 'n daadwerklike BSS vir die TSOSP wat in die raamwerk van hierdie generiese argitektuur pas. Die boustene van hierdie BSS sluit modelle in vir die voorspelling van suikerrietopbrengs, die herwinbare waarde van suikerriet onder normale omstandighede, die verwagte koste geassosieer met 'n oesskedule en die negatiewe e ekte van omgewingsfaktore op die herwinbare waarde van suikerriet. Die werking van die BSS is gebaseer op 'n kombinatoriese optimeringsprobleem wat aan die welbekende asimmetriese handelreisigersprobleem met tyd-afhanklike kostes herinner, en hierdie model word benaderd opgelos deur middel van 'n eienskap-gebaseerde tabu-soektog waarin beide lokale en globale skuiwe ge ïnkorporeer is. Die BSS word ook gevalideer in terme van die haalbaarheid en kwaliteit van die skedules wat dit oplewer, soos geassesseer deur ervare kundiges in die suikerrietbedryf.

With the publication of the famous Erdős-Ko-Rado Theorem in 1961, intersection problems became a popular area of combinatorics. A family of combinatorial objects is t-intersecting if any two of its elements mutually t-intersect, where the latter concept needs to be specified separately in each instance. This thesis is split into two parts; the first is concerned with intersecting injections while the second investigates intersecting posets. We classify maximum 1-intersecting families of injections from {1, ..., k} to {1, ..., n}, a generalisation of the corresponding result on permutations from the early 2000s. Moreover, we obtain classifications in the general t>1 case for different parameter limits: if n is large in terms of k and t, then the so-called fix-families, consisting of all injections which map some fixed set of t points to the same image points, are the only t-intersecting injection families of maximal size. By way of contrast, fixing the differences k-t and n-k while increasing k leads to optimal families which are equivalent to one of the so-called saturation families, consisting of all injections fixing at least r+t of the first 2r+t points, where r=|_ (k-t)/2 _|. Furthermore we demonstrate that, among injection families with t-intersecting and left-compressed fixed point sets, for some value of r the saturation family has maximal size . The concept that two posets intersect if they share a comparison is new. We begin by classifying maximum intersecting families in several isomorphism classes of posets which are linear, or almost linear. Then we study the union of the almost linear classes, and derive a bound for an intersecting family by adapting Katona's elegant cycle method to posets. The thesis ends with an investigation of the intersection structure of poset classes whose elements are close to the antichain. The overarching theme of this thesis is fixing versus saturation: we compare the sizes and structures of intersecting families obtained from these two distinct principles in the context of various classes of combinatorial objects.

The development of recombinant proteins for therapeutic applications has revolutionized the pharmaceutical industry. In particular, monoclonal antibodies are the safest class of all therapeutic molecules and account for the majority of recombinant proteins currently undergoing clinical trials. A variety of technologies exist to engineer antibodies with a desired binding specificity and affinity, both of which are a prerequisite for therapeutic applications. This dissertation describes the implementation of a novel combinatorial library screening technology for the discovery and engineering of antibodies with unique binding properties. Combinatorial library screening technologies are used for the in vitro isolation of antibodies from large ensembles of proteins (libraries) typically produced by microorganisms using molecular biology techniques. Our lab has developed a powerful antibody discovery technology that relies on E. coli display by anchored periplasmic expression, otherwise known as APEx. First, I compared the effects of using combinatorial libraries comprising either smaller, monovalent single-chain antibody fragments (scFv), or the much larger, bifunctional full-length IgG antibodies. These technologies were used to isolate a small panel of antigen specific antibodies from the same library of antibody variable domains amplified from a mouse immunized with the Protective Antigen (PA) component from Bacillus anthracis, the causative agent of anthrax. Overall, IgG display resulted in the isolation of a broader panel of variable domain sequences. Most of these variable domains exhibited substantially reduced affinity when expressed as scFvs, which is consistent with the finding that none of these could be isolated from the equivalent scFv library. These results indicate that the antibody format used during in vitro selection affects which antibody variable domains will be discovered. Second, I developed several modifications of the APEx methodology to allow for more efficient recovery of antibodies with desired properties. Specifically, the system was reengineered to simultaneously account for antibody binding and expression levels in order to isolate the highest affinity antibodies with favorable expression characteristics. Third, the new approach, coupled with optimized fluorescence activated cell sorting (FACS) settings, was used to increase the affinity of an antibody by 35-fold resulting in a K[subscript D] of 100 pM. It was demonstrated that genetic transfer of this high affinity antibody specific for the V antigen of Yersinia pestis, the etiologic agent of the plague, conferred increased protection against intranasal challenge with a 363 LD₅₀ of Y. pestis in mice. / text

Chip-firing is a deceptively simple game played on the vertices of a graph, which was independently discovered in probability theory, poset theory, graph theory, and statistical physics. In recent years, chip-firing has been employed in the development of a theory of divisors on graphs analogous to the classical theory for Riemann surfaces. In particular, Baker and Norin were able to use this set up to prove a combinatorial Riemann-Roch formula, whose classical counterpart is one of the cornerstones of modern algebraic geometry. It is now understood that the relationship between divisor theory for graphs and algebraic curves goes beyond pure analogy, and the primary operation for making this connection precise is tropicalization, a certain type of degeneration which allows us to treat graphs as “combinatorial shadows” of curves. The development of this tropical relationship between graphs and algebraic curves has allowed for beautiful applications of chip-firing to both algebraic geometry and number theory. In this thesis we continue the combinatorial development of divisor theory for graphs. In Chapter 1 we give an overview of the history of chip-firing and its connections to algebraic geometry. In Chapter 2 we describe a reinterpretation of chip-firing in the language of partial graph orientations and apply this setup to give a new proof of the Riemann-Roch formula. We introduce and investigate transfinite chip-firing, and chip-firing with respect to open covers in Chapters 3 and 4 respectively. Chapter 5 represents joint work with Arash Asadi, where we investigate Riemann-Roch theory for directed graphs and arithmetical graphs, the latter of which are a special class of balanced vertex weighted graphs arising naturally in arithmetic geometry.

In the last decade, dynamic combinatorial mass spectrometry (DCMS) with protein targets has emerged as a promising method for the identification of enzyme-inhibitors. 2-Oxoglutarate (2OG) oxygenases are involved in important biological processes related to many diseases; several human 2OG oxygenases are targeted for pharmaceutical intervention. This thesis describes inhibition studies on three 2OG oxygenases using DCMS and structure activity relation (SAR) studies. Disulphide based DCMS was used for the identification of N-oxalyl based lead inhibitors for the 2OG oxygenase AlkB from Escherichia coli. Crystallographic analyses of AlkB with a lead inhibitor assisted in the design of a second generation of inhibitors using N-oxalyl, pyridyl and quinolinyl scaffolds. Crystallographic and kinetic data of three potent and selective AlkB inhibitors validates the DCMS approach for the development of 2OG oxygenase inhibitors. The hypoxia inducible factor hydroxylase, prolyl hydroxylase domain 2 (PHD2), was then used as the model enzyme for the development of a novel DCMS approach employing the reversible reaction of boronic acids with diols to form boronate esters. The ‘boronate’ DCMS method was used to identify pyridyl- substituted lead compounds. Further modification of the pyridine scaffold, based on structural analyses, led to the development of highly potent and selective PHD2 inhibitors. To identify inhibitors for the fat mass and obesity associated protein (FTO), another 2OG oxygenase, an inhibition assay was developed. The inhibition assay was used in conjunction with a differential scanning fluorimetry (DSF) binding assay to identify isoquinolinyl and pyridyl inhibitor scaffolds, related to those used in the DCMS studies. FTO complexed structures of these compounds, and with a natural product anthraquinone, enabled the design and synthesis of new inhibitors that are both co-substrate and substrate competitors of FTO. One such compound proved to be a potent FTO inhibitor with improved selectivity over other 2OG oxygenases. Overall, the work validates the use of DCMS methods for the development of potent and selective inhibitors for 2OG oxygenases, and by implication of other enzyme families.

In this thesis, the structural, optical, and electrical properties of wurtzite MgxZn1-xO:Al and MgxZn1-xO:Ga thin films have been investigated in dependence on Mg and dopant concentration. Among the transparent conductive oxides (TCOs), ZnO based compounds have gained renewed interest as a transparent electrode for large scale applications such as defroster windows, at panel displays, touch screens, and thin film solar cells due to low material and processing cost, non-toxicity, and suitable physical properties. In general, these applications require transparent electrodes with lowest possible resistivity of rho < 10^-3 Ohmcm and lower [1]. Recently, it has been reported that Ga and Al doped ZnO thin films can be deposited with respective resistivity of 5x10^-5 Ohmcm [2] and 3 x10^-5 Ohmcm [3] which are similar to the data obtained for other practical TCOs, i.e. the resistivity of about 4x 10^-5 Ohmcm for Sn doped In2O3 (ITO) thin films [4]. Moreover, the bandgap of ZnO can be increased by alloying with Mg offering band alignment between transparent electrode and active (or buffer) layer of the device, e.g. Cu(In,Ga)Se2 solar cells [5]. The tunable bandgap of these transparent electrodes can further increase the efficiency of the devices by avoiding energy losses in the interface region of the layers. From this point of view, this work has been aimed to investigate the doping efficiency and limits in transparent conductive (Mg,Zn)O alloys. For this purpose, the samples investigated in this work have been grown by pulsed-laser deposition (PLD) using a novel, continuous composition spread method (CCS). In general, this method allows to grow thin films with lateral composition gradient(s) [6, 7]. All MgxZn1-xO:Al and MgxZn1-xO:Ga thin films have been deposited on 2-inch in diameter glass, c- or r-plane sapphire substrates using threefold segmented PLD targets in order to grow thin films with two perpendicular, lateral composition gradients, i.e. the Mg composition is varied in one direction whereas the Al/Ga concentration is varied in a perpendicular direction [7, 8]. In order to investigate the influence of the temperature, samples grown at different substrate temperatures in the range of 25 to 600 C were investigated. The optical and electrical measurements have been carried out on (5x 5)mm^2 samples that were cut from the CCS wafers along the respective composition gradients, i.e. Mg and Al/Ga contents. Subsequently, physical properties of thin films have been analyzed for a large range of Al/Ga content between 0.5 and 7 at.%, which corresponds to doping concentrations between 2x 10^20 and 3x 10^21 cm^-3, for different Mg contents x(Mg) ranging from 0.01 to 0.1. It has been found that practically the limiting the dopant concentrations is about 2 x10^21 cm^-3. Further, the electrical data suggests, that the compensating intrinsic defect is doubly chargeable hinting to the zinc vacancy (V_Zn) as microscopic origin. Increasing the dopant concentration above 2 x10^21 cm^-3 leads to a degradation of electrical and structural properties [8]. Further, the influence of growth and annealing temperatures on structural, electrical and optical properties of the films has been studied. For that purpose, Al and Ga doped (2.5 at.% = 1x10^21 cm^-3) Mg0.05Zn0.95O thin films have been chosen from CCS samples grown at T_g = (25 - 600) C . For both doping series, the samples grown at higher temperatures exhibit better crystalline quality compared to the samples grown at lower growth temperatures. As a result, samples grown at higher temperatures reveal higher Hall mobility. For the Al-doping series, the highest free charge carrier density of n = 8.2x 10^20 cm^-3 was obtained for an Mg0.05Zn0.95O:Al thin film grown at 200 C, with corresponding Hall mobility of mu = 13.3 cm^2/Vs, a resistivity of rho = 5.7x10^-4 Ohmcm, and optical bandgap of E_g = 3.8 eV. Interestingly, the free charge carrier density of n = (5 - 8) x 10^20 cm^-3 for samples grown with T_g > 300 C is clearly higher than the value of n = 1.25 x 10^20 cm^-3 that was obtained for the high temperature grown sample, i.e. at T_g = 600 C. Furthermore, for all T_g, Al-doped films have a higher doping efficiency than the Ga-doped counterparts. In order to look deeper into the microscopic origin of this behavior, the samples were post-annealed in vacuum at 400 C. Experimental results showed that the free charge carrier density of Al-doped samples first decreased and saturated afterward with increasing annealing time. On the other hand, the free charge carrier density of the Ga-doped samples first slightly increased and saturated with increasing annealing time. For both doping series, the saturation value of n ~ 1 x 10^20 cm^-3 was very close to the data that has been observed for (i) high temperature grown samples and (ii) the solubility limit of Al in ZnO of 0.3 at.% = 1.2x 10^20 cm^-3, that has been determined by Shirouzu et al. for high temperature grown (T_g > 600 C) Al-doped ZnO [9]. Correspondingly, the optical bandgap also changed, i.e. increased (decreased) for Al- (Ga-) doping series, and approached a constant value of 3.5 0 +- 0.1 eV which is explained by generation of acceptor-like compensating defects, and the solubility limit of the dopants. From XRD data, no secondary phases were found for as-grown and post-annealed films. However, the slight improvement of crystalline quality has been observed on post-annealed samples. Further, it has been shown that the growth and annealing temperatures are important as they strongly affect the metastable state of the solid solution that samples grown at low temperature represent. The low solubility limit of the dopants, i.e. 0.3 at.% for Al in ZnO under equilibrium condition, can be increased by preparing samples by non-equilibrium growth techniques [10]. This is also consistent with experimental results of this work that Al- as well as Ga-doped metastable ZnO and (Mg,Zn)O thin films can be prepared with highest possible doping efficiency for the dopant concentration up to 2.5 at.% when growth or annealing temperatures below 400 C are used.

The human central nervous system (CNS) contains a daunting number of cells and tremendous cellular diversity. A fundamental challenge of developmental neurobiology is to address the questions of how so many different types of neurons and glia can be generated at the precise time and place, making precisely the right connections. Resolving this issue involves dissecting the elaborate genetic networks that act within neurons and glia, as well as in the neural progenitor cells that generates them, to specify their identities. My PhD project has involved addressing a number of unresolved issues pertaining to how neural progenitor cells are specified to generate different types of neurons and glial cells in different temporal and spatial domains, and also how these early temporal and spatial cues are integrated to activate late cell fate determinants, which act in post-mitotic neural cells to activate distinct batteries of terminal differentiation genes. Analyzing the development of a specific Drosophila melanogaster (Drosophila) CNS stem cell – the neuroblast 5-6 (NB5-6) – we have identified several novel mechanisms of cell fate specification in the Drosophila CNS. We find that, within this lineage, the differential specification of a group of sequentially generated neurons – the Ap cluster neurons – is critically dependent upon the simultaneous triggering of two opposing feed-forward loops (FFLs) within the neuroblast. The first FFL involves cell fate determinants and progresses within the post-mitotic neurons to establish a highly specific combinatorial code of regulators, which activates a distinct battery of terminal differentiation genes. The second loop, which progresses in the neuroblast, involves temporal and sub-temporal genes that together oppose the progression of the first FFL. This leads to the establishment of an alternative code of regulators in late-born Ap cluster neurons, whereby alternative cell fates are specified. Furthermore, we find that the generation and specification of the Ap cluster neurons is modulated along the neuraxis by two different mechanisms. In abdominal segments, Hox genes of the Bithorax cluster integrates with Pbx/Meis factors to instruct NB5-6 to leave the cell cycle before the Ap cluster neurons are generated. In brain segments, Ap cluster neuron equivalents are generated, but improperly specified due to the absence of the proper Hox and temporal code. Additionally, in thoracic segments we find that the specification of the Ap cluster neurons is critically dependent upon the integration of the Hox, Pbx/Meis, and the temporal genes, in the activation of the critical cell fate determinant FFL. We speculate that the developmental principles of (i) feed-forward combinatorial coding; (ii) simultaneously triggered yet opposing feed-forward loops; and (iii) integration of different Hox, Pbx/Meis, and temporal factors, at different axial levels to control inter-segmental differences in lineage progression and specification; might be used widely throughout the animal kingdom to generate cell type diversity in the CNS.

The implementation of a low carbon electricity system within the GB requires a significant change to the generation mix with an increasing role for renewable generation. Much of this generation will be intermittent. To date system balancing has largely relied on predicting demand and ensuring provision. With substantial intermittency, continuation of this paradigm necessitates significant investment in peaking plant and/or storage. However, some of this investment can be avoided by harnessing the flexibility inherent in many electrical loads. Despite the attractiveness of such services, we do not see their large-scale implementation. The aim of this thesis is to consider why. A historical analysis reveals that both nationalisation and subsequent privatisation provide precedents for significant structural change as the integration of large-scale flexible demand might require. The need for political will is identified as a crucial enabling factor. Without an ideological driver, however, a perception of economic and/or technological risk can preclude the implementation of supportive policy. This perception is addressed through demonstration. An effective demonstration must show the ability to aggregate many small loads in a coordinated manner. A genetic algorithm that provides this core dispatch and optimisation capability is presented. This algorithm is shown to be effective in aggregating many small loads to provide a net effect that can be used as a balancing service and to do so in an optimal way considering both cost and reliability. Having demonstrated feasibility appropriate incentives must be created. An initial outline for a framework based on SysML is presented that can be used to identify where structural barriers to implementation are present to aid the design of appropriate policy incentives.

The diploma thesis deals with ways of teaching combinatorics at a secondary school. Specifically, I analyzed selected mathematics textbooks for secondary schools in terms of introducing concepts and operations of combinatorics and in terms of types of tasks used. I carried out interviews with six secondary school mathematics teachers and observations of their lessons in order to describe their method of teaching combinatorics. Using results of tests written by these teachers' pupils, I examined whether and how their solving strategies and errors might be influenced by their teachers' approach to teaching combinatorics. Finally, I compared my results with the existing results of mathematics education research on pupils' combinatorial reasoning. The work is divided into four chapters; the first three are theoretical (curricular documents for selected schools, analysis of textbooks on combinatorics in terms of the implementation of combinatorial concepts and operations, selected research about pupils' solving strategies and errors for combinatorial problems, methods of checking the correctness of their solutions. and the impact of ways of teaching combinatorics on pupils' performance). Chapter 4 focuses on my own research which consists of interviews with teachers, observations of lessons on combinatorics, the...

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte. / We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality.