This thesis tackles a series of problems related to the evolution of completesoftware systems both in terms of the underlying Genetic Programmingsystem and the application of that system. A new representation is presented that addresses some of the issues withother Genetic Program representations while keeping their advantages. Thiscombines the easy reproduction of the linear representation with the inheritablecharacteristics of the tree representation by using fixed-length blocks ofgenes representing single program statements. This means that each block ofgenes will always map to the same statement in the parent and child unless itis mutated, irrespective of changes to the surrounding blocks. This methodis compared to the variable length gene blocks used by other representationswith a clear improvement in the similarity between parent and child. Traditionally, fitness functions have either been created as a selection ofsample inputs with known outputs or as hand-crafted evaluation functions. Anew method of creating fitness evaluation functions is introduced that takesthe formal specification of the desired function as its basis. This approachensures that the fitness function is complete and concise. The fitness functionscreated from formal specifications are compared to simple input/outputpairs and the results show that the functions created from formal specificationsperform significantly better. A set of list evaluation and manipulation functions was evolved as anapplication of the new Genetic Program components. These functions havethe common feature that they all need to be 100% correct to be useful. Traditional Genetic Programming problems have mainly been optimizationor approximation problems. The list results are good but do highlight theproblem of scalability in that more complex functions lead to a dramaticincrease in the required evolution time. Finally, the evolution of graphical user interfaces is addressed. The representationfor the user interfaces is based on the new representation forprograms. In this case each gene block represents a component of the userinterface. The fitness of the interface is determined by comparing it to a seriesof constraints, which specify the layout, style and functionality requirements. A selection of web-based and desktop-based user interfaces were evolved. With these new approaches to Genetic Programming, the evolution ofcomplete software systems is now a realistic goal.

In this thesis, we investigate the complexity of the membership problem for pattern languages. A pattern is a string over the union of the alphabets A and X, where X := {x_1, x_2, x_3, ...} is a countable set of variables and A is a finite alphabet containing terminals (e.g., A := {a, b, c, d}). Every pattern, e.g., p := x_1 x_2 a b x_2 b x_1 c x_2, describes a pattern language, i.e., the set of all words that can be obtained by uniformly substituting the variables in the pattern by arbitrary strings over A. Hence, u := cacaaabaabcaccaa is a word of the pattern language of p, since substituting cac for x_1 and aa for x_2 yields u. On the other hand, there is no way to obtain the word u' := bbbababbacaaba by substituting the occurrences of x_1 and x_2 in p by words over A. The problem to decide for a given pattern q and a given word w whether or not w is in the pattern language of q is called the membership problem for pattern languages. Consequently, (p, u) is a positive instance and (p, u') is a negative instance of the membership problem for pattern languages. For the unrestricted case, i.e., for arbitrary patterns and words, the membership problem is NP-complete. In this thesis, we identify classes of patterns for which the membership problem can be solved efficiently. Our first main result in this regard is that the variable distance, i.e., the maximum number of different variables that separate two consecutive occurrences of the same variable, substantially contributes to the complexity of the membership problem for pattern languages. More precisely, for every class of patterns with a bounded variable distance the membership problem can be solved efficiently. The second main result is that the same holds for every class of patterns with a bounded scope coincidence degree, where the scope coincidence degree is the maximum number of intervals that cover a common position in the pattern, where each interval is given by the leftmost and rightmost occurrence of a variable in the pattern. The proof of our first main result is based on automata theory. More precisely, we introduce a new automata model that is used as an algorithmic framework in order to show that the membership problem for pattern languages can be solved in time that is exponential only in the variable distance of the corresponding pattern. We then take a closer look at this automata model and subject it to a sound theoretical analysis. The second main result is obtained in a completely different way. We encode patterns and words as relational structures and we then reduce the membership problem for pattern languages to the homomorphism problem of relational structures, which allows us to exploit the concept of the treewidth. This approach turns out be successful, and we show that it has potential to identify further classes of patterns with a polynomial time membership problem. Furthermore, we take a closer look at two aspects of pattern languages that are indirectly related to the membership problem. Firstly, we investigate the phenomenon that patterns can describe regular or context-free languages in an unexpected way, which implies that their membership problem can be solved efficiently. In this regard, we present several sufficient conditions and necessary conditions for the regularity and context-freeness of pattern languages. Secondly, we compare pattern languages with languages given by so-called extended regular expressions with backreferences (REGEX). The membership problem for REGEX languages is very important in practice and since REGEX are similar to pattern languages, it might be possible to improve algorithms for the membership problem for REGEX languages by investigating their relationship to patterns. In this regard, we investigate how patterns can be extended in order to describe large classes of REGEX languages.

Fretting fatigue is a type of contact fatigue which causes premature failure in a number of engineering assemblies subjected to vibration or other forms of cyclic loading. It is concerned with the nucleation of cracks due to oscillatory micro slip between contacting bodies. Therefore, a detailed knowledge of the interface conditions and the means of quantifying crack nucleation are very important, and will be the ultimate goal of this thesis. The analysis of an incomplete contact (Herzian contact) is considered first followed by various complete contacts. Fretting fatigue tests employing a Hertzian contact are analysed accurately by introducing several modifications needed to the classical formulation. With the total state of stress in a strip established, the crack tip stress intensity factor for a crack growing inward from the trailing edge of the contact is determined by the distributed dislocation technique. The results are then correlated with local solutions for the contact stress field which enable an estimate of the crack nucleation life, and hence a characteristic material property quantifying initiation, to be found. The interfacial contact pressure distribution beneath a complete sliding contact between elastically similar components, in the presence of friction, has been studied in detail, with particular reference to contacts whose edge angles are 60 degree, 90 degree and 120 degree. The possible types of behaviour at the edge of contacts, namely power order singularity, power order bounded and square root bounded, are discussed. A full understanding of the behaviour requires a detailed study of a characteristic equation, and this shows the kinds of pressure distribution to be anticipated, which can vary very markedly. The transition from power order behaviour to local separation and bounded behaviour is examined, and an appropriate asymptotic form developed. The problem of trapezium shaped punches pressed into a frictional, elastically similar half-plane, and subject to sequential normal and shear loading, under partial slip, is studied. Detailed considerations have again been given to the specific cases of 60 degree, 90 degree and 120 degree punches, and maps have been developed showing the initial mix of stick, slip and separation regions, together with the steady state response when the shearing force is cycled. Conditions for full stick are established.

Effective visualization of graphs is a powerful tool to help understand the relationships among the graph's underlying objects and to interact with them. Several styles for drawing graphs have emerged over the last three decades. Polyline drawing is a widely used style for drawing graphs, where each node is mapped to a distinct point in the plane and each edge is mapped to a polygonal chain between their corresponding nodes. Some common optimization criteria for such a drawing are defined in terms of area requirement, number of bends per edge, angular resolution, number of distinct line segments, edge crossings, and number of planar layers. In this thesis we develop algorithms for drawing graphs that optimize different aesthetic qualities of the drawing. Our algorithms seek to simultaneously optimize multiple drawing aesthetics, reveal potential trade-offs among them, and improve many previous graph drawing algorithms. We start by exploring probable trade-offs in the context of planar graphs. We prove that every $n$-vertex planar triangulation $G$ with maximum degree $\Delta$ can be drawn with at most $2n+t-3$ segments and $O(8^t \cdot \Delta^{2t})$ area, where $t$ is the number of leaves in a Schnyder tree of $G$. We then show that one can improve the area by allowing the edges to have bends. Since compact drawings often suffer from bad angular resolution, we seek to compute polyline drawings with better angular resolution. We develop a polyline drawing algorithm that is simple and intuitive, yet implies significant improvement over known results. At this point we move our attention to drawing nonplanar graphs. We prove that every thickness-$t$ graph can be drawn on $t$ planar layers with $\min\{O(2^{t/2} \cdot n^{1-1/\beta}), 2.25n +O(1)\}$ bends per edge, where $\beta = 2^{\lceil (t-2)/2 \rceil }$. Previously, the bend complexity, i.e., the number of bends per edge, was not known to be sublinear for $t>2$. We then examine the case when the number of available layers is restricted. The layers may now contain edge crossings. We develop a technique to draw complete graphs on two layers, which improves previous upper bounds on the number of edge crossings in such drawings. / October 2016

The purpose of the study was to examine the impact that hypertext and hypertext design on the cognitive process. The study used two identical computer based lessons. One set of lessons used a complete set of hypertext resources that supported all of the learning objectives throughout the lessons. The other set of lessons focused the hypertext resources by limiting them to the immediate learning objective.

In this paper we extend the study of Heffter arrays and the biembedding of graphs on orientable surfaces first discussed by Archdeacon in 2014. We begin with the definitions of Heffter systems, Heffter arrays, and their relationship to orientable biembeddings through current graphs. We then focus on two specific cases. We first prove the existence of embeddings for every K_(6n+1) with every edge on a face of size 3 and a face of size n. We next present partial results for biembedding K_(10n+1) with every edge on a face of size 5 and a face of size n. Finally, we address the more general question of ordering subsets of Z_n take away {0}. We conclude with some open conjectures and further explorations.

In the 1970's computer scientists developed the theory of computational complexity. Some problems seemed hard-to-compute, while others were easy. It turned out that many of the hard problems were equally hard in a way that could be precisely specified. They became known as the NP-complete problems. The SATISFIABILITY problem (SAT) was the first problem to be proved NP-complete in 1971. Since then numerous other hard-to-solve problems have been proved to be in NP-complete. In this paper we will examine the problem of how to find a maximum independent set of vertices for a graph. This problem is known as Maximum Independent Set (MIS) for a graph. The corresponding decision problem for MIS is the question, given an integer K, is there a independent set with at least K vertices? This decision problem is INDEPENDENT SET (IS). The intention of this paper is to show through polynomial transformation that IS is in the set of NP-complete Problems. We intend to show that 3SAT is NP-complete and then using this fact, that IS is NP-complete.

Johnsongrass mosaic virus (JGMV) é uma espécie do gênero Potyvirus. A sua distribuição geográfica, até o início da década de 1990, estava limitada à Austrália e aos Estados Unidos, onde causa doença em sorgo, milho e várias gramíneas. Em 2001, o JGMV foi detectado pela primeira vez no Brasil em amostras de híbridos e variedades de milho provenientes da região de Ribeirão Preto, SP mediante análise sorológica (DAS-ELISA), e em 2013 foi detectado mediante RT-PCR em amostras de Pennisetum purpureum provenientes do Estado da Bahia. Em Fevereiro de 2012 a Clínica Fitopatológica da ESALQ/USP recebeu amostras de Panicum maximum cv. Mombaça, com sintomas de mosaico, de São Luiz do Paraitinga, SP. Exames preliminares de contrastação negativa em microscópio eletrônico de transmissão indicaram a presença de partículas virais características de potyvirus. Diante disso, o principal objetivo deste trabalho foi caracterizar o agente etiológico associado às plantas doentes de capim Mombaça mediante testes biológicos, sorológicos e moleculares. Extratos foliares de plantas sintomáticas de capim Mombaça foram inoculados mecanicamente em 69 genótipos da família Poaceae. As avaliações foram feitas com base nos sintomas e por PTA-ELISA usando antissoro policlonal contra a proteína capsidial do potyvirus produzido nesse trabalho, após purificação do isolado viral. As espécies susceptíveis foram Brachiaria brizantha, B. decumbens, B. plantaginea, Cenchrus echinatus, Echinochloa colona, E. crus-galli, E. cruspavonis, Melinis minutiflora, Panicum maximum cv. Colonião, Pennisetum setosum, Rhynchelytrum repens, Rottboellia exaltata, Sorghum bicolor BRS 332, S. bicolor BRS 509, S. bicolor x S. sudanense BRS 802 e S. verticilliflorum. Espécies cultivadas como arroz, aveia, cana-de-açúcar, centeio, milho e trigo não foram infectadas com esse isolado. O peso molecular da proteína capsidial deste potyvirus foi estimado em cerca de 33 kDa por meio de Western blot. Sequência de nucleotídeos do genoma completo (9.885 nt) obtida neste estudo revelou identidade de 82,03% com a única sequência completa do genoma de um isolado do JGMV da Austrália, depositada no GenBank. A partir dessa sequência foram obtidos oligonucleotídeos iniciadores específicos para a detecção do isolado de SP do JGMV mediante RT-PCR. / Johnsongrass mosaic virus (JGMV) is a species of the genus Potyvirus. The geographical distribution, until the early 1990s, was limited to Australia and the United States, where it causes disease in sorghum, corn and various grasses. In 2001, JGMV was first detected in Brazil in samples of hybrids and varieties of corn from the region of Ribeirão Preto, São Paulo State by serological analysis (DASELISA), and in 2013 it was detected by RT-PCR in samples of Pennisetum purpureum from the State of Bahia. In February 2012, the Disease Diagnostic Clinic ESALQ/USP received samples of Panicum maximum cv. Mombaça, exhibiting mosaic symptoms, from the region of São Luiz do Paraitinga, SP. Preliminary examination of negatively stained sap in a transmission electron microscope indicated the presence of potyvirus-like particles. Therefore, the main objective of this study was to characterize the etiologic agent associated with P. maximum cv. Mombaça diseased plants by biological, serological and molecular tests. Leaf extract from Mombaça infected plants was mechanically inoculated in 69 genotypes of the Poaceae family. Evaluations were done based on symptoms expression and PTAELISA using polyclonal antiserum against the capsid protein of the potyvirus produced in the preset work virus purification. Susceptible species were Brachiaria brizantha, B. decumbens, B. plantaginea, Cenchrus echinatus, Echinochloa colona, E. crus-galli, E. crus-pavonis, Melinis minutiflora, Panicum maximum cv. Colonião, Pennisetum setosum, Rhynchelytrum repens, Rottboellia exaltata, Sorghum bicolor BRS 332, S. bicolor BRS 509, S. bicolor x S. sudanense BRS 802 and S. verticilliflorum. Cultivated species such as rice, oats, sugarcane, rye, corn and wheat were not infected with this isolate. The molecular weight of the coat protein of this potyvirus was estimated at about 33 kDa by Western blot. The nucleotide sequence of the complete genome (9885 nt) obtained in this study showed 82.03% identity with an unique sequence for the complete genome of an isolate of JGMV from Australia, deposited in GenBank. From this nucleotide sequence, specific pair of primers was designed for the detection of the São Paulo isolate of JGMV by RT-PCR.

Objetivo: avaliar por meio de fotografias de perfil e um questionário específico, a estética facial de indivíduos com fissura transforame incisivo bilateral (FTB), operados segundo o protocolo do HRAC-USP. Modelo: Estudo transversal, com análise das fotografias, atribuindo escores aos pacientes e comparando-os estatisticamente. Local de Execução: HRAC-USP. Participantes: Amostra: 30 pacientes, 24 do gênero masculino e 6 do gênero feminino, com idades entre 5 anos e 8 meses a 10 anos e 4 meses, leucodermas, com FTB . Examinadores: 5 Ortodontistas do HRAC-USP (OHRAC), 5 ortodontistas não relacionados à área de fissura (ONF), 5 Cirurgiões Plásticos do HRAC-USP (CPHRAC), 5 Cirurgiões Plásticos não relacionados à área de fissura (CPNF), 5 leigos (L) com formação superior. Variáveis: classificação da agradabilidade facial, em escala de 1 a 9, estruturas reconhecidas como responsáveis pela pior classificação. Resultados: O grupo OHRAC atribuiu mediana de 7 (aparência esteticamente agradável), o grupo CPHRAC atribuiu 5 (esteticamente aceitável). O grupo L atribuiu 4 (esteticamente aceitável). Os grupos ONF e CPNF, designaram 3 (esteticamente desagradável). Existiu diferença significante entre todas as categorias, exceto para os ONF e CPNF. Foram associadas à classificação esteticamente desagradável o nariz, o terço médio da face e o lábio superior. Conclusões: A estética facial da amostra foi classificada em agradável (grupo OHRAC), aceitável (grupos CPHRAC e L) e desagradável (grupos ONF e CPNF). Houve diferença significante entre os grupos, exceto para os ONF e CPNF. As estruturas associadas aos piores escores foram o nariz, o terço médio da face e o lábio superior. / Objective: to evaluate, by means of photographs of profile and a specific questionnaire, the facial esthetics of individuals with complete bilateral cleft lip and palate (CBCLP) operated according to the protocol of HRAC-USP. Design: cross-sectional study with analysis of the photographs, by assignment of scores to the patients and statistical comparison. Setting: HRAC-USP. Participants: sample: 30 white patients with CBCLP, being 24 males and 6 females, aged 5 years 8 months to 10 years 4 months. Examines: 5 orthodontists of HRAC-USP (OHRAC), 5 orthodontists not treating patients with clefts (ONC), 5 plastic surgeons of HRAC-USP (PSHRAC), 5 plastic surgeons not treating patients with clefts (PSNC), and 5 lay graduated examiners (L). Variables: classification of facial pleasantness in a scale from 1 to 9, structures recognized as responsible for the worst classification. Results: the OHRAC group assigned a median of 7 (esthetically pleasant appearance) and the PSHRAC assigned 5 (esthetically acceptable). Group L assigned 4 (esthetically acceptable). Groups ONC and PSNC assigned 3 (esthetically unpleasant). There was a significant difference between all categories, except for ONC and PSNC. The structures associated to the esthetically unpleasant classification were the nose, middle third of the face and upper lip. Conclusions: the facial esthetics of the sample was classified as pleasant (OHRAC group), acceptable (PSHRAC and L groups) and unpleasant (ONC and PSNC groups). here was a significant difference between groups, except for the ONC and PSNC. The structures associated to the worst scores were the nose, middle third of the face and upper lip.

O objetivo deste estudo foi avaliar a alteração de cor de resinas acrílicas termopolimerizáveis (convencional e de microondas) após imersões em soluções químicas higienizadoras de próteses totais em diferentes períodos de tempo. Foram obtidos padrões em cera (15mm de diâmetro e 4mm de espessura), a partir de uma matriz de teflon, que foram incluídos em muflas convencionais e para microondas. Após a eliminação da cera, as resinas foram manipuladas, prensadas e polimerizadas segundo as instruções dos fabricantes. Foram confeccionados 200 corpos-de-prova, 100 de cada marca comercial das resinas Lucitone 550 (L) e Onda Cryl (OC), os quais foram imersos nas soluções: A)Água destilada-3 min.; B)Bony Plus -3 min.; C)Água destilada-5 min.; D)Corega Tabs-5 min.; E)Água destilada-20 min.; F)Hipoclorito de sódio a 0,5%-20 min.; G)Hipoclorito de sódio a 1%-20 min.; H)Água destilada-8 horas; I)Hipoclorito de sódio a 0,5%-8 horas; J)Hipoclorito de sódio a 1%-8 horas. A alteração de cor foi avaliada empregando-se um espectrocolorímetro (Color Guide 45/0 BYK-Gardner) antes e após a simulação de 180 dias de imersão. Os resultados foram comparados por meio da análise de variância (ANOVA) para dois fatores, seguida pelo teste de Student-Newman Keuls, com nível de significância de 0,05. Para correlacionar as diferenças de cor para o ambiente clínico, os dados foram calculados de acordo com as unidades da National Bureau of Standards (NBS). Os resultados mostraram que a resina Lucitone 550 (ΔE = 0,47±0,18) apresentou-se mais estável que a Onda-Cryl (ΔE = 0,53±0,31). Para ambas as resinas, as pastilhas, os hipocloritos por 20 minutos (0,5% e 1%) e por 08 horas (0,5%) não provocaram alterações maiores que seus respectivos controles (L-A: 0,27 ±0,10; L-B: 0,44±0,21; L-C: 0,48±0,21; L-D: 0,46±0,13; L-E: 0,29±0,07; L-F: 0,37±0,08; L-G: 0,47±0,10; L-H: 0,61±0,11; L-I: 0,55±0,10; OC-A: 0,22±0,08; OC-B: 0,43±0,32; OC-C: 0,65±0,35; OC-D: 0,41±0,11; OC-E: 0,31±0,11; OC-F: 0,29±0,07; OC-G: 0,37 ±0,11; OC-H: 0,78±0,10; OC-I: 0,79±0,08). As soluções de hipoclorito a 1% (L-J: 0,74±0,09; OC-J: 1,06 ±0,13) causaram maiores alterações que seus respectivos controles. As soluções empregadas por 08 horas (água e Hipocloritos a 0,5% e 1%) provocaram alterações classificadas como leves, segundo o sistema NBS. Os achados deste estudo revelaram que as pastilhas efervescentes, quando usadas de acordo com as instruções dos fabricantes, e o hipoclorito de sódio (0,5% e 1%) por 20 minutos apresentaram menores valores de alteração de cor nas resinas acrílicas após um período de uso simulado de 180 dias. Médias mais elevadas foram obtidas quando um regime de 8 horas foi simulado. / The aim of this study was to evaluate color alteration of heat-polymerized acrylic resins (conventional and microwave-polymerized), after immersion in chemicals solutions of denture cleansers for different periods of time. Wax patterns were obtained (15 mm in diameter and 4 mm thickness) from a teflon matrix and were invested in metallic or microwavable flasks. The wax had been eliminated and the resins were mixed, packed and polymerized according to the manufacturers instructions. Two hundred specimens were made, 100 specimens of each commercial resin Lucitone 550 (L) e Onda Cryl (OC), which were immersed in the solutions: A)Distilled water-3 min.; B)Bony Plus-3 min.; C)Distilled water-5 min.; D)Corega Tabs-5 min.; E) Distilled water -20 min.; F) 0,5% Sodium Hypochlorite-20 min.; G) 1% Sodium Hypochlorite-20 min.; H)Distilled water-8 hours; I)0,5% Sodium Hypochlorite-8 hours; J)1% Sodium Hypochlorite -8 hours. Color alteration was assessed by a spectrocolorimeter (Color Guide 45/0 (BYKGardner) before and after 180 days simulation. The results were analyzed statistically by a two-way analysis of variance (ANOVA), and Student Newman-Keuls test, with significance level of 0.05. To relate the color differences to a clinical environment, the data were quantified by National Bureau of Standards (NBS) units. The results showed that the resin Lucitone 550 (ΔE=0,47±0,18) was more stable than the resin Onda-Cryl (ΔE=0,53±0,31). For both resins, the tablets, the hypochlorite by 20 minutes (0,5% e 1%) and by 8 hours (0,5%) did not produce higher alterations than the respective controls (L-A: 0,27 ±0,10; L-B: 0,44±0,21; L-C: 0,48±0,21; L-D: 0,46±0,13; L-E: 0,29±0,07; L-F: 0,37±0,08; L-G: 0,47±0,10; L-H: 0,61±0,11; L-I: 0,55±0,10; OC-A: 0,22±0,08; OC-B: 0,43±0,32; OC-C: 0,65±0,35; OC-D: 0,41±0,11; OC-E: 0,31±0,11; OC-F: 0,29±0,07; OC-G: 0,37 ±0,11; OC-H: 0,78±0,10; OC-I: 0,79±0,08). The 1% hypochlorite solutions (L-J: 0,74±0,09; OC-J: 1,06 ±0,13) produced higher alterations than the respective controls. The solutions employed by 8 hours (water and 0,5% and 1% hipochlorite) produced alterations classified as slight, according to the NBS system. The findings of this study showed that the effervescent tablets, used according to the manufacturer´s instructions, and the sodium hypochlorite (0,5% and 1%) used by 20 minutes presented lower values of color alterations in acrylic resins after a period of 180 days simulation. Higher mean averages were obtained when a period of 8 hours was simulated.