Los programas While: bases para una teoría de la computabilidad

La Teoría de la Computabilidad estudia los límites teóricos de los sistemas computacionales. Uno de sus objetivos centrales consiste en clasificar los problemas en computables e incomputables, donde llamamos computable a un problema si admite solución informática. Para desarrollar estos resultados el modelo abstracto de computador más utilizado históricamente es la Máquina de Turing. Los estudiantes de Ingeniería Informática pueden percibir cierta lejanía entre el modelo teórico y los computadores reales por lo que es más adecuado utilizar un modelo más cercano a la programación como son los programas-while. Los Programas-while permiten resolver los mismos problemas que las máquinas de Turing, pero en cambio son mucho más sencillos de utilizar, sobre todo para personas que tienen una experiencia previa en la informática real, pues toman la forma de lenguaje imperativo clásico. Este texto además utiliza los Programas-while aprovechando sus ventajas y reformulándolos de manera que la computación quede definida en términos de manipulación de símbolos arbitrarios, algo que está mucho más en concordancia con la realidad informática. Además de explicar en detalle qué son los programas while y cómo se utilizan, se justifica por qué no es necesario incorporar otras instrucciones o tipos de datos.

While programak: konputagarritasun teoria oinarritzeko tresna

Konputagarritasun Teoriaren asmoa sistema konputazionalen muga teorikoak aztertzea da. Bere helburu nagusia problemak konputagarri eta konputaezinen artean bereiztea da, problema konputagarria ebazpide informatikoa onartzen duenari deitzen diogula kontuan hartuta. Emaitza horiek garatzeko konputagailu eredu abstraktu erabiliena, historikoki, Turing-en Makina izan da. Ingeniaritza Informatikoko ikasleek eredu abstraktuaren eta konputagailu errealen artean distantzia dagoela nabari dezakete, horregatik programaziotik hurbilago dagoen eredu bat erabiltzea egokiagoa da, while programak hain zuzen ere. While programekin Turingen makinekin ebazten diren problema berak ebazten dira. Aldiz, while programak erabiltzen askoz errazagoak dira, batez ere aurretik informatika errealean esperientzia duten pertsonentzat, lengoaia agintzaile klasikoen programen itxura hartzen baitute. Testu honek while programak erabiltzen ditu, behar denean hauek birformulatuz eta beraien abantailak aprobetxatuz, konputazioa sinbolo arbitrarioen manipulazioaren baitan definituta gera dadin. Horrela, errealitate informatikotik askoz hurbilagoa egongo da. While programak zer diren eta nola erabiltzen diren zehaztasunez azaltzen da, eta gainera, beste agindu edo datu-mota batzuk gehitzea zergatik ez den beharrezkoa justifikatzen da.

Algunas demostraciones de incomputabilidad usando la técnica de diagonalización

Los supuestos fundamentales de la Teoría de la Computabilidad se establecieron antes de la aparición de los primeros ordenadores (a finales de los años 40), supuestos que muchos años de vertiginoso cambio no han conseguido alterar. Alan Mathison Turing demostró ya entonces que ningún ordenador, por muy potente que lo imaginemos, podría resolver algunas cuestiones. Estos problemas para los que no existe ningún algoritmo posible, los incomputables, no son excepcionales y hay un gran número de ellos entre los problemas que se plantean en torno al comportamiento de los programas. El problema de parada, es sin duda el miembro más conocido de esta familia: no existe un algoritmo para decidir con carácter general si un programa ciclará o no al recibir unos datos de entrada concretos. Para demostrar la incomputabilidad de un problema necesitamos un argumento lógico que certifique la inexistencia de algoritmo, o lo que es lo mismo, que pruebe que ninguno de los algoritmos existentes es capaz de resolver dicho problema. Tal argumento de carácter universal no suele ser sencillo de establecer, y normalmente suele estar relacionado con una demostración por reducción al absurdo. Existen distintas técnicas para lograr este objetivo. La técnica de diagonalización es la más básica de ellas, y resulta bastante conocida al no tratarse de una herramienta específica de la Informática Teórica. En este documento no se trata de explicar la técnica en sí, que se supone conocida, sino de ilustrarla con una colección de ejemplos de diferente grado de dificultad.

Konputaezintasun frogapen batzuk diagonalizazio teknika erabiliz

Konputagarritasunaren Teoriaren oinarriak lehenengo ordenadoreak azaldu aurretik (40. hamarkadaren bukaera aldera) ezarri ziren, eta ziztu biziko eta etenik gabeko eraldaketek aldatzea lortu ez duten oinarriak dira. Alan Mathison Turing-ek jadanik garai hartan frogatu zuen, ahalik eta potentzia handienekoa imajinatuta ere, inolako ordenadorek ebatzi ezingo zituen zenbait gai edo arazo bazeudela. Balizko algoritmorik ez duten problema horiek, konputaezinak deitzen ditugunak, ez dira salbuespenak eta adibide ugari aurki dezakegu. Programen portaeraren inguruan planteatzen diren problemen artean, asko konputaezinak dira. Familia horretako kide ezagunena, zalantzarik gabe, geratze problema da: sarrerako datu zehatz batzuk hartzerakoan, programa bat begizta infinituan geratuko ote den era orokorrean erabakitzeko algoritmorik ez dago. Problema baten konputaezintasuna frogatzeko, hau ebatziko duen algoritmo zehatz bat existitzen ez dela ziurtatuko duen argumentu logikoa behar dugu, edo beste era batera esanda, existitzen diren algoritmoak problema hori ebazteko gai izango ez direla egiaztatuko duen argumentua. Izaera unibertsaleko argumentu hori ezartzea ez da batere erraza izaten, eta normalean, absurduraino eramandako frogapen batekin erlazionatuta egon ohi da. Helburu hori lortzeko zenbait teknika daude. Diagonalizazioaren teknika horien artean oinarrizkoena da, eta nahiko ezaguna, ez baita Informatika Teorikoaren tresna espezifikoa. Dokumentu honen helburua ez da teknika bera azaldu edo deskribatzea, ezaguntzat hartzen baita, zailtasun maila desberdineko hainbat adibideren bitartez argitzea baizik.

Técnicas básicas de computabilidad

La Teoría de la Computabilidad es una disciplina encuadrada en la Informática Teórica que tiene como objetivo establecer los límites lógicos que presentan los sistemas informáticos a la hora de resolver problemas mediante el diseño de algoritmos. Frente a las disciplinas y técnicas que día a día amplían el campo de aplicabilidad práctica de los computadores, esta teoría establece una serie de barreras insalvables por ninguna tecnología digital de procesamiento de la información. Los métodos propios de la Teoría de la Computabilidad pueden ser extraordinariamente complejos, sin embargo, existe un núcleo de resultados fundamentales que son abordables mediante técnicas más asequibles, y que tienen la virtud de reflejar razonablemente el concepto central de indecidibilidad computacional. Este informe incluye una descripción de los conceptos y técnicas que configuran ese núcleo básico de la Teoría. Su propósito es dar cuenta de la primera batería de resultados relacionados con la incomputabilidad de algunos problemas conocidos y relevantes en Informática. Los resultados se presentan utilizando como estándar de programación los programas-while, incluyéndose una explicación detallada y sistemática de la técnica de Diagonalización, además de resultados tan importantes como la tesis de Church-Turing, la función universal o el problema de parada.

El método de reducción en Teoría de la Computabilidad

La Teoría de la Computabilidad es una disciplina encuadrada en la Informática Teórica que tiene como objetivo establecer los límites lógicos que presentan los sistemas informáticos a la hora de resolver problemas mediante el diseño de algoritmos. Estos resultados proporcionan importantes herramientas que se utilizan para demostrar tanto la computabilidad como la incomputabilidad de muchas funciones relevantes. Los primeros problemas incomputables que se encontraron lo fueron allá por la década de los años 30. El problema de parada es el primer y más conocido ejemplo de problema no resoluble mediante técnicas algorítmicas: ningún ordenador, por muy potente que sea, puede anticipar el comportamiento de los programas en ejecución, y decidir de antemano si terminarán o no. Este problema nos proporciona un soporte intuitivo para anticipar la incomputabilidad de otros problemas relacionados y un procedimiento para resolverlos: el método de diagonalización. Sin embargo para determinados problemas también incomputables hay que recurrir a otros métodos. Este texto incluye una descripción de otra técnica básica de Teoría de la Computabilidad: la Reducción. La base del método estriba en demostrar que ciertos pares de problemas están fuertemente relacionados de modo que si el segundo tiene solución algorítmica entonces el primero debe tenerla necesariamente también. Esta relación se establece por medio de funciones transformadoras computables, que permiten convertir de manera automática las instancias positivas del primer problema en instancias positivas del segundo. Esta técnica se utiliza muy a menudo porque resulta comparativamente más sencilla que la diagonalización, ya que en general requiere menos esfuerzo para demostrar la incomputabilidad de un mismo problema.

Changes in fire regimes since the Last Glacial Maximum: an assessment based on a global synthesis and analysis of charcoal data

Fire activity has varied globally and continuously since the last glacial maximum (LGM) in response to long-term changes in global climate and shorter-term regional changes in climate, vegetation, and human land use. We have synthesized sedimentary charcoal records of biomass burning since the LGM and present global maps showing changes in fire activity for time slices during the past 21,000 years (as differences in charcoal accumulation values compared to pre-industrial). There is strong broad-scale coherence in fire activity after the LGM, but spatial heterogeneity in the signals increases thereafter. In North America, Europe and southern South America, charcoal records indicate less-than-present fire activity during the deglacial period, from 21,000 to ∼11,000 cal yr BP. In contrast, the tropical latitudes of South America and Africa show greater-than-present fire activity from ∼19,000 to ∼17,000 cal yr BP and most sites from Indochina and Australia show greater-than-present fire activity from 16,000 to ∼13,000 cal yr BP. Many sites indicate greater-than-present or near-present activity during the Holocene with the exception of eastern North America and eastern Asia from 8,000 to ∼3,000 cal yr BP, Indonesia and Australia from 11,000 to 4,000 cal yr BP, and southern South America from 6,000 to 3,000 cal yr BP where fire activity was less than present. Regional coherence in the patterns of change in fire activity was evident throughout the post-glacial period. These complex patterns can largely be explained in terms of large-scale climate controls modulated by local changes in vegetation and fuel load

Health surveys and use of maternal and child health care services in three municipalities within the Sao Paulo metropolitan area

Objectives. To describe the changes in the use of maternal and child health care services by residents of three municipalities-Embu, Itapecerica da Serra, and Taboao da Serra-in the Sao Paulo metropolitan area, 12 years after the implementation of the Unified Health System (SUS) in Brazil, and to analyze the potential of population-based health care surveys as sources of data to evaluate these changes. Methods. Two population-based, cross-sectional surveys were carried out in 1990 and 2002 in municipalities located within the Sao Paulo metropolitan area. For children under 1 year of age, the two periods were compared in terms of outpatient services utilization and hospital admission; for the mothers, the periods were compared in terms of prenatal care and deliveries. In both surveys, stratified and multiple-stage conglomerate sampling was employed, with standardization of interview questions. Results. The most important changes observed were regarding the location of services used for prenatal care, deliveries, and hospitalization of children less than 1 year of age. There was a significant increase in the use of services in the surrounding region or hometown, and decrease in the utilization of services in the city of Sao Paulo (in 1990, 80% of deliveries and almost all admissions for children less than 1 year versus 32% and 46%, respectively, in 2002). The use of primary care units and 24-hour walk-in clinics also increased. All these changes reflect care provided by public resources. In the private sector, there was a decrease in direct payments and payments through company-paid health insurance and an increase in payments through self-paid health insurance. Conclusions. The major changes observed in the second survey occurred simultaneous to the changes that resulted from the implementation of the SUS. Population-based health surveys are adequate for analyzing and comparing the utilization of health care services at different times.

Thioxanthone Sensitized Photodegradation of Poly(alkyl methacrylate) Films

The thioxanthone-sensitized photodegradation of poly(alkyl methacrylate) films [alkyl = methyl, ethyl, butyl, and hexyl] was studied using near UV-vis light. The photooxidation process continued even after the total consumption of the sensitizer, possibly due to the excitation of the ketyl groups formed during the first stages of the process. The rate of oxidation, as well as the formation of hydroxy, peroxy, and ketyl groups was faster for polymers with larger ester groups. The decrease of the molecular weight of the degradated polymers was also larger for the hexyl substituted polymer. The side-chain size effect was attributed to the larger amount of secondary hydrogens available for abstraction by the triplet state of thioxanthone, present in the larger ester groups. The lower glass transition temperature of the hexyl substituted polymer allows a better diffusion of oxygen to the deeper layers of the films that also contributes to the faster photodegradation rate. (C) 2009 Wiley Periodicals, Inc. J Appl Polym Sci 115: 1283-1288, 2010

Transparent Fault Tolerance for Web Services based Architectures

Service-based architectures enable the development of new classes of Grid and distributed applications. One of the main capabilities provided by such systems is the dynamic and flexible integration of services, according to which services are allowed to be a part of more than one distributed system and simultaneously serve different applications. This increased flexibility in system composition makes it difficult to address classical distributed system issues such as fault-tolerance. While it is relatively easy to make an individual service fault-tolerant, improving fault-tolerance of services collaborating in multiple application scenarios is a challenging task. In this paper, we look at the issue of developing fault-tolerant service-based distributed systems, and propose an infrastructure to implement fault tolerance capabilities transparent to services.

Automated Negotiation for Grid Notification Services

Notification Services mediate between information publishers and consumers that wish to subscribe to periodic updates. In many cases, however, there is a mismatch between the dissemination of these updates and the delivery preferences of the consumer, often in terms of frequency of delivery, quality, etc. In this paper, we present an automated negotiation engine that identifies mutually acceptable terms; we study its performance, and discuss its application to a Grid Notification Service. We also demonstrate how the negotiation engine enables users to control the Quality of Service levels they require.

Gestão de pessoas para melhoria do serviço público: o caso das centrais de atendimento do Banco Central

O objetivo deste estudo é verificar em que medida a Central de Atendimento ao Público do Banco do Brasil, em Brasília provê a adequada alocação de seus servidores a capacitação desses, e as condições organizacionais necessárias para a automotivação. Considera-se que esses fatores são de suma importância para prestação de um serviço público. Buscou -se ainda verificar se as condições sócio-econômicas e de trabalho não são impeditivas da boa prestação do serviço. Foram aplicados formulários e questionários aos servidores a fim de verificar em que medida estão presentes esses fatores. A conclusão aponta que, apesar de a alocação ser feita de maneira empírica, da necessidade de criação de um sistema de treinamento mais alinhado com os objetivos da instituição, e da baixa cultura de comunicação intraorganizacional ,a gestão de pessoas no Banco Central do Brasil, caminha para um pensamento de melhoria contínua e apresenta soluções para grande parte dos problemas identificados.

Insuficiência cardíaca com fração de ejeção normal

A insuficiência cardíaca com fração de ejeção normal (ICFEN) é uma síndrome complexa que vem sendo largamente estudada, desde a última década. É causada por disfunção ventricular diastólica evidenciada por métodos complementares, como estudo hemodinâmico ou ecocardiograma, na presença de fração de ejeção preservada. Acomete preferencialmente indivíduos mais idosos e com comorbidades, como hipertensão arterial sistêmica, insuficiência coronariana e obesidade. Os mecanismos fisiopatológicos são complexos e multifatoriais, envolvendo a rigidez passiva do miocárdio, a geometria ventricular, a força de contenção do pericárdio e a interação entre os ventrículos. Os objetivos principais do tratamento são reduzir a congestão venosa pulmonar, a frequência cardíaca e controlar as comorbidades. Ainda não há evidências fortes de que o uso de medicações específicas, como inibidores de enzima de conversão ou betabloqueadores, interfiram na mortalidade. Os fatores de pior prognóstico incluem a idade avançada, presença de disfunção renal, diabete, classe funcional III e IV (NYHA) e estágio avançado de disfunção diastólica, com padrão restritivo ao enchimento ventricular. Outro aspecto que vem ganhando espaço na literatura é o questionamento do papel da disfunção sistólica nos quadros de ICFEN. Todos esses aspectos são abordados detalhadamente na presente revisão.