Strong isomorphism reductions in complexity theory

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees.

Shape complexity based on mutual information

Shape complexity has recently received attention from different fields, such as computer vision and psychology. In this paper, integral geometry and information theory tools are applied to quantify the shape complexity from two different perspectives: from the inside of the object, we evaluate its degree of structure or correlation between its surfaces (inner complexity), and from the outside, we compute its degree of interaction with the circumscribing sphere (outer complexity). Our shape complexity measures are based on the following two facts: uniformly distributed global lines crossing an object define a continuous information channel and the continuous mutual information of this channel is independent of the object discretisation and invariant to translations, rotations, and changes of scale. The measures introduced in this paper can be potentially used as shape descriptors for object recognition, image retrieval, object localisation, tumour analysis, and protein docking, among others

Error and complexity of random walk Monte Carlo radiosity

The author studies the error and complexity of the discrete random walk Monte Carlo technique for radiosity, using both the shooting and gathering methods. The author shows that the shooting method exhibits a lower complexity than the gathering one, and under some constraints, it has a linear complexity. This is an improvement over a previous result that pointed to an O(n log n) complexity. The author gives and compares three unbiased estimators for each method, and obtains closed forms and bounds for their variances. The author also bounds the expected value of the mean square error (MSE). Some of the results obtained are also shown

An Efficient Nominal Unification Algorithm

Nominal Unification is an extension of first-order unification where terms can contain binders and unification is performed modulo α equivalence. Here we prove that the existence of nominal unifiers can be decided in quadratic time. First, we linearly-reduce nominal unification problems to a sequence of freshness and equalities between atoms, modulo a permutation, using ideas as Paterson and Wegman for first-order unification. Second, we prove that solvability of these reduced problems may be checked in quadràtic time. Finally, we point out how using ideas of Brown and Tarjan for unbalanced merging, we could solve these reduced problems more efficiently

Remote Synchronization Reveals Network Symmetries and Functional Modules

We study a Kuramoto model in which the oscillators are associated with the nodes of a complex network and the interactions include a phase frustration, thus preventing full synchronization. The system organizes into a regime of remote synchronization where pairs of nodes with the same network symmetry are fully synchronized, despite their distance on the graph. We provide analytical arguments to explain this result, and we show how the frustration parameter affects the distribution of phases. An application to brain networks suggests that anatomical symmetry plays a role in neural synchronization by determining correlated functional modules across distant locations.

To select or to weigh: a comparative study of linear combination schemes for superparent-one-dependence estimators

We conduct a large-scale comparative study on linearly combining superparent-one-dependence estimators (SPODEs), a popular family of seminaive Bayesian classifiers. Altogether, 16 model selection and weighing schemes, 58 benchmark data sets, and various statistical tests are employed. This paper's main contributions are threefold. First, it formally presents each scheme's definition, rationale, and time complexity and hence can serve as a comprehensive reference for researchers interested in ensemble learning. Second, it offers bias-variance analysis for each scheme's classification error performance. Third, it identifies effective schemes that meet various needs in practice. This leads to accurate and fast classification algorithms which have an immediate and significant impact on real-world applications. Another important feature of our study is using a variety of statistical tests to evaluate multiple learning methods across multiple data sets.

Informational Aesthetics Measures

The Birkhoff aesthetic measure of an object is the ratio between order and complexity. Informational aesthetics describes the interpretation of this measure from an information-theoretic perspective. From these ideas, the authors define a set of ratios based on information theory and Kolmogorov complexity that can help to quantify the aesthetic experience

Informational Aesthetics Measures

The Birkhoff aesthetic measure of an object is the ratio between order and complexity. Informational aesthetics describes the interpretation of this measure from an information-theoretic perspective. From these ideas, the authors define a set of ratios based on information theory and Kolmogorov complexity that can help to quantify the aesthetic experience

Shape complexity based on mutual information

Shape complexity has recently received attention from different fields, such as computer vision and psychology. In this paper, integral geometry and information theory tools are applied to quantify the shape complexity from two different perspectives: from the inside of the object, we evaluate its degree of structure or correlation between its surfaces (inner complexity), and from the outside, we compute its degree of interaction with the circumscribing sphere (outer complexity). Our shape complexity measures are based on the following two facts: uniformly distributed global lines crossing an object define a continuous information channel and the continuous mutual information of this channel is independent of the object discretisation and invariant to translations, rotations, and changes of scale. The measures introduced in this paper can be potentially used as shape descriptors for object recognition, image retrieval, object localisation, tumour analysis, and protein docking, among others

Error and complexity of random walk Monte Carlo radiosity

The author studies the error and complexity of the discrete random walk Monte Carlo technique for radiosity, using both the shooting and gathering methods. The author shows that the shooting method exhibits a lower complexity than the gathering one, and under some constraints, it has a linear complexity. This is an improvement over a previous result that pointed to an O(n log n) complexity. The author gives and compares three unbiased estimators for each method, and obtains closed forms and bounds for their variances. The author also bounds the expected value of the mean square error (MSE). Some of the results obtained are also shown

Simulació computacional d'incendis en edificis

En la propagació d’un incendi en un edifici intervenen molts processos fisicoquímics degran complexitat: moviment turbulent dels gasos, reaccions de combustió, transmissióde la calor,.... L’avenç en el coneixement científic de tots aquests processos, unit a unincrement constant de la capacitat i velocitat computacional dels ordinadors, fanpossible la resolució de problemes cada cop més complexes i la creació de models desimulació cada cop més realistes.

Sistematização do dimensionamento técnico e econômico de sistemas fotovoltaicos isolados por meio de programa computacional

One of the main referring subjects to the solar energy is how to compare it economically with other sources of energy, as much alternatives as with conventionals (like the electric grid). The purpose of this work was to develop a software which congregates the technical and economic main data to identify, through methods of microeconomic analysis, the commercial viability in the sizing of photovoltaic systems, besides considering the benefits proceeding from the proper energy generation. Considering the period of useful life of the components of the generation system of photovoltaic electricity, the costs of the energy proceeding from the conventional grid had been identified. For the comparison of the conventional sources, electric grid and diesel generation, three scenes of costs of photovoltaic panels and two for the factor of availability of diesel generation had been used. The results have shown that if the cost of the panels is low and the place of installation is more distant of the electric grid, the photovoltaic system becomes the best option.

Uma perspectiva computacional sobre catálise enzimática

Enzymes are extremely efficient catalysts. Here, part of the mechanisms proposed to explain this catalytic power will be compared to quantitative experimental results and computer simulations. Influence of the enzymatic environment over species along the reaction coordinate will be analysed. Concepts of transition state stabilisation and reactant destabilisation will be confronted. Divided site model and near-attack conformation hypotheses will also be discussed. Molecular interactions such as covalent catalysis, general acid-base catalysis, electrostatics, entropic effects, steric hindrance, quantum and dynamical effects will also be analysed as sources of catalysis. Reaction mechanisms, in particular that catalysed by protein tyrosine phosphatases, illustrate the concepts.

Propriedades dinâmicas de fluidos por simulação computacional: métodos híbridos atomístico-contínuo

Computational methods for the calculation of dynamical properties of fluids might consider the system as a continuum or as an assembly of molecules. Molecular dynamics (MD) simulation includes molecular resolution, whereas computational fluid dynamics (CFD) considers the fluid as a continuum. This work provides a review of hybrid methods MD/CFD recently proposed in the literature. Theoretical foundations, basic approaches of computational methods, and dynamical properties typically calculated by MD and CFD are first presented in order to appreciate the similarities and differences between these two methods. Then, methods for coupling MD and CFD, and applications of hybrid simulations MD/CFD, are presented.

A investigação da construção de modelos no estudo de um tópico de física utilizando um ambiente de modelagem computacional qualitativo

A integração de tecnologias de informação e comunicação no contexto educacional tem sido tema de diversos congressos e simpósios ao redor do mundo e no Brasil. Neste sentido, vários estudos têm sido realizados com o objetivo de se obter metodologias que tornem efetivo o emprego das novas tecnologias no ensino. Este artigo mostra um estudo que investigou a interação entre estudantes universitários da área de ciências exatas e um ambiente de modelagem computacional qualitativo em atividades de modelagem expressiva. Os resultados obtidos mostram que os estudantes foram capazes de criar e modificar o modelo do sistema proposto a partir de suas próprias concepções.