Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma

Nonogram is a logical puzzle whose associated decision problem is NP-complete. It has applications in pattern recognition problems and data compression, among others. The puzzle consists in determining an assignment of colors to pixels distributed in a N  M matrix that satisfies line and column constraints. A Nonogram is encoded by a vector whose elements specify the number of pixels in each row and column of a figure without specifying their coordinates. This work presents exact and heuristic approaches to solve Nonograms. The depth first search was one of the chosen exact approaches because it is a typical example of brute search algorithm that is easy to implement. Another implemented exact approach was based on the Las Vegas algorithm, so that we intend to investigate whether the randomness introduce by the Las Vegas-based algorithm would be an advantage over the depth first search. The Nonogram is also transformed into a Constraint Satisfaction Problem. Three heuristics approaches are proposed: a Tabu Search and two memetic algorithms. A new function to calculate the objective function is proposed. The approaches are applied on 234 instances, the size of the instances ranging from 5 x 5 to 100 x 100 size, and including logical and random Nonograms

Geração de processos WS-BPEL com base em um algoritmo de reescrita de regras

Web services are computational solutions designed according to the principles of Service Oriented Computing. Web services can be built upon pre-existing services available on the Internet by using composition languages. We propose a method to generate WS-BPEL processes from abstract specifications provided with high-level control-flow information. The proposed method allows the composition designer to concentrate on high-level specifi- cations, in order to increase productivity and generate specifications that are independent of specific web services. We consider service orchestrations, that is compositions where a central process coordinates all the operations of the application. The process of generating compositions is based on a rule rewriting algorithm, which has been extended to support basic control-flow information.We created a prototype of the extended refinement method and performed experiments over simple case studies

Extensões ao Projeto LVWNet: mobilidade, interação com equipamentos reais, comunicação direta, e registro dinâmico de nós

Due to the constantly increasing use of wireless networks in domestic, business and industrial environments, new challenges have emerged. The prototyping of new protocols in these environments is typically restricted to simulation environments, where there is the need of double implementation, one in the simulation environment where an initial proof of concept is performed and the other one in a real environment. Also, if real environments are used, it is not trivial to create a testbed for high density wireless networks given the need to use various real equipment as well as attenuators and power reducers to try to reduce the physical space required to create these laboratories. In this context, LVWNet (Linux Virtual Wireless Network) project was originally designed to create completely virtual testbeds for IEEE 802.11 networks on the Linux operating system. This paper aims to extend the current project LVWNet, adding to it the features like the ability to interact with real wireless hardware, provides a initial mobility ability using the positioning of the nodes in a space coordinates environment based on meters, with loss calculations due to attenuation in free space, enables some scalability increase by creating an own protocol that allows the communication between nodes without an intermediate host and dynamic registration of nodes, allowing new nodes to be inserted into in already in operation network

Condicionamento estrutural das zonasa de cisalhamento da região de Forquilha, domínio Ceará Central: uma abordagem integrada de sensoriamento remoto e geologia estrutural

The studied region, named Forquilha and localized in northwestern Central Ceará domain (northern portion of Borborema Province), presents a lithostratigraphic framework constituted by paleoproterozoic metaplutonics, metasedimentary sequences and neoproterozoic granitoids. The metasedimentary rocks of Ceará group occupy most part of the area. This group is subdivided in two distinct units: Canindé and Independência. Canindé unit is represented basically by biotite paragneisses and muscovite paragneisses, with minor metabasic rocks (amphibolite lens). Independência sequence is composed by garnetiferous paragneisses, sillimanite-garnet-quartz-muscovite schists and quartz-muscovite schists, pure or muscovite quartzites and rare marbles. At least three ductile deformation events were recognized in both units of Ceará group, named D1, D2 and D3. The former one is interpreted as related to a low angle tangential tectonics which mass transport is southward. D2 event is marked by the development of close/isoclinal folds with a N-S oriented axis. Refolding patterns generated by F1 and F2 superposition are found in several places. The latest event (D3) corresponds to a transcurrent tectonics, which led to development of mega-folds and several shear zones, under a transpressional regime. The mapped shear zones are Humberto Monte (ZCHM), Poço Cercado (ZCPC) and Forquilha (ZCF). Digital image processing of enhanced Landsat 7-ETM+ satellite images, combined with field data, demonstrate that these penetrative structures are associated with positive and negative geomorphologic patterns, distributed in linear and curvilinear arrangements with tonal banding, corresponding to the ductile fabric and to crests. Diverse color composites were tested and RGB-531 and RGB-752 provided the best results for lineament analysis of the most prominent shear zones. Spatial filtering techniques (3x3 and 5x5 filters) were also used and the application of Prewitt filters generated the best products. The integrated analysis of morphological and textural aspects from filtered images, variation of tonalities related to the distribution of geologic units in color composites and the superposition over a digital elevation model, contributed to a characterization of the structural framework of the study area. Kinematic compatibility of ZCHM, ZCPC, ZCF shear zones, as well as Sobral-Pedro II (ZCSPII) shear zone, situated to the west of the study area, was one of the goal of this work. Two of these shear zones (ZCHM, ZCPC) display sinistral movements, while the others (ZCSPII, ZCF) exhibit dextral kinematics. 40Ar/39Ar ages obtained in this thesis for ZCSPII and ZCPC, associated with other 40Ar/39Ar data of adjacent areas, indicate that all these shear zones are related to Brasiliano orogeny. The trend of the structures, the opposite shear senses and the similar metamorphic conditions are fitted in a model based on the development of conjugate shear zones in an unconfined transpression area. A WNW-ESE bulk shortening direction is infered. The geometry and kinematic of the studied structures suggest that shortening was largely accommodated by lateral extrusion, with only minor amounts of vertical stretch

Estudo do fluxo de neutrino solar com o código evolutivo de Toulouse - Geneva

The study of solar neutrinos is very important to a better comprehension of the set of nuclear reactions that occurs inside the Sun and in solar type stars. The ux of neutrinos provides a better comprehension of the stellar structure as a whole. In this dissertation we study the ux of neutrinos in a solar model, addressing the neutrino oscillation, analyzing with the intention of determining and verify the distribution from a statistical point of view, since this ux depends on the particles intrinsic velocity distributions in stellar plasma. The main tool for this analysis was the Toulouse-Geneva Stellar Evolution Code, or TGEC, which allow us to obtain the neutrino ux values per reaction and per layer inside the Sun, allowing us to compare the observational results for the neutrino ux detected on experiments based on Cl37 (Homestake), Ga71 (SAGE, Gallex/GNO) and water (SNO). Our results show the nal distribution for neutrino ux as a function of the depth using the coordinates of mass and radius. The dissertation also shows that the equations for this ux are present in TGEC.

Monitoramento geoambiental do estuário do Rio Paraíba do Norte - PB por meio da cartografia temática digital e de produtos de sensoriamento remoto

The North Paraíba River Estuary, located in the eastern portion of the Paraíba State, Northeast Brazil, on coordinates 34º50 00 -34º57 30 S and 6º55 00 -7º7 30 W, constitutes a fluvio-marine plain formed by the North Paraíba River and its tributaries Sanhauá, Paroeira, Mandacaru, Tiriri, Tambiá, Ribeira and Guia. This estuary comprises an area of about 260 km2. Increasing human demands on the estuary area and inadequate environment managing have generated conflicts. The present work main purpose is to evaluate the geodynamic evolution of the North Paraíba River Estuary in the period from 1969 to 2001, using digital image processing techniques, thematic digital cartography and multitemporal data integration, combined to geological-geophysical field surveys. The SUDENE cartographic database, converted to digital format were, used to obtain occupation and topographic maps from 1969 and to generate a Digital Elevation Model (DEM). Digital Landsat 7 ETM+ and Spot HRVIR-PAN satellite images interpretation allowed the environmental characterization of the estuary. The most important digital processing results were achieved color composites RGB 5-4-3, 5-3-1, 5-2-NDWI and band ratio 7/4-5/3-4/2, 5/7-3/1-5/4). In addition the fusion image technique RGBI was used by the inclusion of the Spot HRVRI and Landsat 7 ETM+ panchromatic band on I layer with RGB triplets 5-4-3, 5-3-1 and 5/7-3/1-5/4. The DEM and digital images integration allowed the identification of seven geomorphological units: coastal tableland, flowing tray, tide plain, fluvial terrace, submerged dune, beach plain and beach). Both Side Scan Sonar and Echosound were used to analyse underwater surface and bedforms of the estuarine channel, sand predominance (fine to very fine) and 2D dune features 5 m wide and 0.5 m height. This investigation characterized the estuary as an environment dominated by regimen of average flow. The channel depth varies between 1 m and 11 m, being this last quota reached in the area of Porto de Cabedelo. The chanel estuary is relatively shallow, with erosion evidences mainly on its superior portion, attested by sand banks exposed during the low tide. Multitemporal digital maps from 1969 and 2001 integration were obtained through geoprocessing techniques, resulting the geodynamic evolution of the estuary based on landuse, DEM geomorphology and bathymetric maps

Desenvolvimento de dobras e falhas em ambiente distensional: Aplicação da modelagem física

The geological modeling allows, at laboratory scaling, the simulation of the geometric and kinematic evolution of geological structures. The importance of the knowledge of these structures grows when we consider their role in the creation of traps or conduits to oil and water. In the present work we simulated the formation of folds and faults in extensional environment, through physical and numerical modeling, using a sandbox apparatus and MOVE2010 software. The physical modeling of structures developed in the hangingwall of a listric fault, showed the formation of active and inactive axial zones. In consonance with the literature, we verified the formation of a rollover between these two axial zones. The crestal collapse of the anticline formed grabens, limited by secondary faults, perpendicular to the extension, with a curvilinear aspect. Adjacent to these faults we registered the formation of transversal folds, parallel to the extension, characterized by a syncline in the fault hangingwall. We also observed drag folds near the faults surfaces, these faults are parallel to the fault surface and presented an anticline in the footwall and a syncline hangingwall. To observe the influence of geometrical variations (dip and width) in the flat of a flat-ramp fault, we made two experimental series, being the first with the flat varying in dip and width and the second maintaining the flat variation in width but horizontal. These experiments developed secondary faults, perpendicular to the extension, that were grouped in three sets: i) antithetic faults with a curvilinear geometry and synthetic faults, with a more rectilinear geometry, both nucleated in the base of sedimentary pile. The normal antithetic faults can rotate, during the extension, presenting a pseudo-inverse kinematics. ii) Faults nucleated at the top of the sedimentary pile. The propagation of these faults is made through coalescence of segments, originating, sometimes, the formation of relay ramps. iii) Reverse faults, are nucleated in the flat-ramp interface. Comparing the two models we verified that the dip of the flat favors a differentiated nucleation of the faults at the two extremities of the mater fault. V These two flat-ramp models also generated an anticline-syncline pair, drag and transversal folds. The anticline was formed above the flat being sub-parallel to the master fault plane, while the syncline was formed in more distal areas of the fault. Due the geometrical variation of these two folds we can define three structural domains. Using the physical experiments as a template, we also made numerical modeling experiments, with flat-ramp faults presenting variation in the flat. Secondary antithetic, synthetic and reverse faults were generated in both models. The numerical modeling formed two folds, and anticline above the flat and a syncline further away of the master fault. The geometric variation of these two folds allowed the definition of three structural domains parallel to the extension. These data reinforce the physical models. The comparisons between natural data of a flat-ramp fault in the Potiguar basin with the data of physical and numerical simulations, showed that, in both cases, the variation of the geometry of the flat produces, variation in the hangingwall geometry