O problema do caixeiro viajante alugador : um estudo algorítmico

The Car Rental Salesman Problem (CaRS) is a variant of the classical Traveling Salesman Problem which was not described in the literature where a tour of visits can be decomposed into contiguous paths that may be performed in different rental cars. The aim is to determine the Hamiltonian cycle that results in a final minimum cost, considering the cost of the route added to the cost of an expected penalty paid for each exchange of vehicles on the route. This penalty is due to the return of the car dropped to the base. This paper introduces the general problem and illustrates some examples, also featuring some of its associated variants. An overview of the complexity of this combinatorial problem is also outlined, to justify their classification in the NPhard class. A database of instances for the problem is presented, describing the methodology of its constitution. The presented problem is also the subject of a study based on experimental algorithmic implementation of six metaheuristic solutions, representing adaptations of the best of state-of-the-art heuristic programming. New neighborhoods, construction procedures, search operators, evolutionary agents, cooperation by multi-pheromone are created for this problem. Furtermore, computational experiments and comparative performance tests are conducted on a sample of 60 instances of the created database, aiming to offer a algorithm with an efficient solution for this problem. These results will illustrate the best performance reached by the transgenetic algorithm in all instances of the dataset

JCML - Java Card Modeling Language: Definição e Implementação

Formal methods should be used to specify and verify on-card software in Java Card applications. Furthermore, Java Card programming style requires runtime verification of all input conditions for all on-card methods, where the main goal is to preserve the data in the card. Design by contract, and in particular, the JML language, are an option for this kind of development and verification, as runtime verification is part of the Design by contract method implemented by JML. However, JML and its currently available tools for runtime verification were not designed with Java Card limitations in mind and are not Java Card compliant. In this thesis, we analyze how much of this situation is really intrinsic of Java Card limitations and how much is just a matter of a complete re-design of JML and its tools. We propose the requirements for a new language which is Java Card compliant and indicate the lines on which a compiler for this language should be built. JCML strips from JML non-Java Card aspects such as concurrency and unsupported types. This would not be enough, however, without a great effort in optimization of the verification code generated by its compiler, as this verification code must run on the card. The JCML compiler, although being much more restricted than the one for JML, is able to generate Java Card compliant verification code for some lightweight specifications. As conclusion, we present a Java Card compliant variant of JML, JCML (Java Card Modeling Language), with a preliminary version of its compiler

Aplicação do algoritmo de otimização por colônia de formigas sobre o problema do passeio do robô seletivo

This work seeks to propose and evaluate a change to the Ant Colony Optimization based on the results of experiments performed on the problem of Selective Ride Robot (PRS, a new problem, also proposed in this paper. Four metaheuristics are implemented, GRASP, VNS and two versions of Ant Colony Optimization, and their results are analyzed by running the algorithms over 32 instances created during this work. The metaheuristics also have their results compared to an exact approach. The results show that the algorithm implemented using the GRASP metaheuristic show good results. The version of the multicolony ant colony algorithm, proposed and evaluated in this work, shows the best results

Uma máquina de redução de grafos para serviços web

Web services are software accessible via the Internet that provide functionality to be used by applications. Today, it is natural to reuse third-party services to compose new services. This process of composition can occur in two styles, called orchestration and choreography. A choreography represents a collaboration between services which know their partners in the composition, to achieve the service s desired functionality. On the other hand, an orchestration have a central process (the orchestrator) that coordinates all application operations. Our work is placed in this latter context, by proposing an abstract model for running service orchestrations. For this purpose, a graph reduction machine will be defined for the implementation of service orchestrations specified in a variant of the PEWS composition language. Moreover, a prototype of this machine (in Java) is built as a proof of concept

Algoritmos científicos

The Scientific Algorithms are a new metaheuristics inspired in the scientific research process. The new method introduces the idea of theme to search the solution space of hard problems. The inspiration for this class of algorithms comes from the act of researching that comprises thinking, knowledge sharing and disclosing new ideas. The ideas of the new method are illustrated in the Traveling Salesman Problem. A computational experiment applies the proposed approach to a new variant of the Traveling Salesman Problem named Car Renter Salesman Problem. The results are compared to state-of-the-art algorithms for the latter problem

Novos métodos determinísticos para gerar centros iniciais dos grupos no algoritmo fuzzy C-Means e variantes

Data clustering is applied to various fields such as data mining, image processing and pattern recognition technique. Clustering algorithms splits a data set into clusters such that elements within the same cluster have a high degree of similarity, while elements belonging to different clusters have a high degree of dissimilarity. The Fuzzy C-Means Algorithm (FCM) is a fuzzy clustering algorithm most used and discussed in the literature. The performance of the FCM is strongly affected by the selection of the initial centers of the clusters. Therefore, the choice of a good set of initial cluster centers is very important for the performance of the algorithm. However, in FCM, the choice of initial centers is made randomly, making it difficult to find a good set. This paper proposes three new methods to obtain initial cluster centers, deterministically, the FCM algorithm, and can also be used in variants of the FCM. In this work these initialization methods were applied in variant ckMeans.With the proposed methods, we intend to obtain a set of initial centers which are close to the real cluster centers. With these new approaches startup if you want to reduce the number of iterations to converge these algorithms and processing time without affecting the quality of the cluster or even improve the quality in some cases. Accordingly, cluster validation indices were used to measure the quality of the clusters obtained by the modified FCM and ckMeans algorithms with the proposed initialization methods when applied to various data sets

Algoritmo treansgenético na solução do problema do Caixeiro Viajante

The Traveling Purchaser Problem is a variant of the Traveling Salesman Problem, where there is a set of markets and a set of products. Each product is available on a subset of markets and its unit cost depends on the market where it is available. The objective is to buy all the products, departing and returning to a domicile, at the least possible cost defined as the summation of the weights of the edges in the tour and the cost paid to acquire the products. A Transgenetic Algorithm, an evolutionary algorithm with basis on endosymbiosis, is applied to the Capacited and Uncapacited versions of this problem. Evolution in Transgenetic Algorithms is simulated with the interaction and information sharing between populations of individuals from distinct species. The computational results show that this is a very effective approach for the TPP regarding solution quality and runtime. Seventeen and nine new best results are presented for instances of the capacited and uncapacited versions, respectively

Determinação de haplótipos do gene βs em portadores de anemia falcifome

Haplotypes linked to the βS gene represent patterns of DNA polymorphisms along chromosome 11 of individuals bearing the βS gene. Analysis of haplotypes, in addition to serving as an important source for anthropological studies about the ethnic origin of a population, contributes to a better understanding of the variations in clinical severity of sickle cell anemia. The aim of the present study was to determine βS gene haplotypes in a group of patients with sickle cell anemia treated at the Dalton Barbosa Cunha Hematology Center (Hemonorte) in Natal, Brazil and the Oncology and Hematology Center in Mossoró, Brazil. Blood samples were obtained from 53 non-related patients (27 males and 26 females), aged between 3 months and 61 years (mean age: 16.9 ± 12.1 years). Laboratory analyses consisted of the following: erythrogram, reticulocyte count, hemoglobin electrophoresis at alkaline pH, measurement of hemoglobin A2 and Fetal hemoglobin, solubility test and molecular analysis to determine βS gene haplotypes. DNA samples were extracted by illustra blood genomicPrep Mini Spin kit and βS gene haplotypes were determined by PCR-RFLP, using Xmn I, Hind III, Hinc II and Hinf I restriction enzymes for analysis of six polymorphic restriction sites in the beta cluster. Of 106 βS chromosomes studied, 75.5% were Central African Republic (CAR) haplotype, 11.3% Benin (BEN) and 6.6% Cameroon (CAM). The atypical haplotypes had a frequency of 6.6%. More than half the patients (58.5%) were identified as CAR/CAR genotype carriers, 16.9% heterozygous CAR/BEN, 13.2% CAR/CAM and 1.9% BEN/BEN. Patients with atypical haplotype in one or two chromosomes accounted for 9.5% (CAR/Atp, BEN/Atp and Atp/Atp). The genotype groups showed no statistically significant difference (p < 0.05) in their laboratory parameters. This is the first study related to βS haplotypes conducted in state of Rio Grande do Norte and the higher frequency of Cameroon halotype found, compared to other Brazilian states, suggests the existence of a peculiarity of African origin

Prevalência de talassemia alfa+ (deleção -3.7) na população adulta do estado do Rio Grande do Norte

Alpha thalassemia, the most common monogenic disorder in the world, is characterized by deletions of one (+-thalassemia) or both alpha genes (0-thalassemia) located on human chromosome 16 (16p13.3). The most common case of +-thalassemia is a deletion of 3.7 kb of DNA (-3.7 deletion). It is most prevalent in African and Middle East regions. In the few studies carried out in Brazilian population -3.7 deletion was the most common deletion, mainly in African descendants. This study was conducted to determine the prevalence of +- thalassemia (deletion 3.7kb) in adult population from Rio Grande do Norte. We obtained blood samples from 713 unrelated individuals of both genders, aged between 18 and 59 years old. All individuals were born in Rio Grande do Norte. The hematological indices were obtained in an automatic cell counter (Micros 60, ABX Diagnostics). The hemoglobin measurement (A2 and Fetal hemoglobin) and the profile confirmation were carried out by high performance liquid chromatography (HPLC) methodology. Genomic DNA was obtained from peripheral blood leukocytes using Illustra Blood GenomicPrep Mini Spin kit and -3.7 deletion was investigated by PCR. Among the 713 individuals studied, 80 (11,2%) presented +- thalassemia: 79 (11,1%) were heterozygous and 1 (0,1%) homozygous for the -3.7 deletion. Considering the ethnic group, negroes showed the greatest prevalence of +-thalassemia (12,5%), followed by mulattoes (12,3%) and caucasian (9,6%). Statistical comparison of hematological parameters between normal individuals and heterozygous to +-thalassemia showed significant differences in RBC (p<0,001), MCV (p<0,001), MCH (p<0,001), Hb A2 (p=0,007) as well as female hemoglobin concentration (p=0,003). This is one of the first studies to research +-thalassemia in general population of Rio Grande do Norte state and these results attest the importance of investigation of this condition to define the etiology of microcytosis and hypochromia.

Transporte eletrônico e propriedades termodinâmicas de nanobiomoléculas

We use a tight-binding formulation to investigate the transmissivity and the currentvoltage (I_V) characteristics of sequences of double-strand DNA molecules. In order to reveal the relevance of the underlying correlations in the nucleotides distribution, we compare theresults for the genomic DNA sequence with those of arti_cial sequences (the long-range correlated Fibonacci and RudinShapiro one) and a random sequence, which is a kind of prototype of a short-range correlated system. The random sequence is presented here with the same _rst neighbors pair correlations of the human DNA sequence. We found that the long-range character of the correlations is important to the transmissivity spectra, although the I_V curves seem to be mostly inuenced by the short-range correlations. We also analyze in this work the electronic and thermal properties along an _-helix sequence obtained from an _3 peptide which has the uni-dimensional sequence (Leu-Glu-Thr- Leu-Ala-Lys-Ala)3. An ab initio quantum chemical calculation procedure is used to obtain the highest occupied molecular orbital (HOMO) as well as their charge transfer integrals, when the _-helix sequence forms two di_erent variants with (the so-called 5Q variant) and without (the 7Q variant) _brous assemblies that can be observed by transmission electron microscopy. The di_erence between the two structures is that the 5Q (7Q) structure have Ala ! Gln substitution at the 5th (7th) position, respectively. We estimate theoretically the density of states as well as the electronic transmission spectra for the peptides using a tight-binding Hamiltonian model together with the Dyson's equation. Besides, we solve the time dependent Schrodinger equation to compute the spread of an initially localized wave-packet. We also compute the localization length in the _nite _-helix segment and the quantum especi_c heat. Keeping in mind that _brous protein can be associated with diseases, the important di_erences observed in the present vi electronic transport studies encourage us to suggest this method as a molecular diagnostic tool

O problema do caixeiro alugador com coleta de bonus: um estudo algoritmico

This paper introduces a new variant of the Traveling Car Renter Problem, named Prizecollecting Traveling Car Renter Problem. In this problem, a set of vertices, each associated with a bonus, and a set of vehicles are given. The objective is to determine a cycle that visits some vertices collecting, at least, a pre-defined bonus, and minimizing the cost of the tour that can be traveled with different vehicles. A mathematical formulation is presented and implemented in a solver to produce results for sixty-two instances. The proposed problem is also subject of an experimental study based on the algorithmic application of four metaheuristics representing the best adaptations of the state of the art of the heuristic programming.We also provide new local search operators which exploit the neighborhoods of the problem, construction procedures and adjustments, created specifically for the addressed problem. Comparative computational experiments and performance tests are performed on a sample of 80 instances, aiming to offer a competitive algorithm to the problem. We conclude that memetic algorithms, computational transgenetic and a hybrid evolutive algorithm are competitive in tests performed

As estratégias de negação variantes no inglês falado: uma comparação com o português

The general aim of this work is to verify the occurence of variant forms of negation in spoken English with the purpose of making a comparative study between the English and the Portuguese languages. As for Portuguese, we used as a matter of reference a study already made on negation. As for English, we analized a corpus of the North American English variant organized by a university in the United States. This study is based on the North American Functional Linguistics theoretical perspective, which considers relevant the study of language used in real situations of communicative interaction. The data analisys proved that there is at least one form of negative variant in spoken English which is not allowed by prescriptive grammar. This phenomenon turns out to be similar to Portuguese, which includes three variant strategies. According to the data obtained, it was possible to verify that the variant strategy used in English, from a contrastive point of view, corresponds to a negative strategy ruled by Portuguese prescriptive grammar. Finally, we discussed about the different conceptions of language, grammar and teaching, giving suggestions to colaborate to a productive and reflexive teaching of first or second language