1,720,965 research outputs found
Complejidad computacional en distintas formulaciones de ajedrez para un jugador
No full textEl objetivo de esta tesis es estudiar la complejidad computacional correspondiente al problema del ajedrez solitario, en que dada una posición el jugador sólo puede hacer jugadas de captura con el objetivo de dejar una sola pieza en el tablero. Demostramos que este problema pertenece a la clase de complejidad de los problemas NP-Completos. Mediante problemas de ciclos hamiltonianos en grafos no dirigidos, se investiga la NP-Completitud del juego restringiendo el conjunto de piezas a diferentes posibilidades utilizando peones, alfiles y torres. Para esto se presentan cuatro formas de generar las posiciones con diferentes propiedades como las piezas usadas o las maneras de representar las aristas del grafo. Se compara un método con otro para analizar ventajas de cada uno, tales como tamaño del tablero y cantidad de piezas necesarias. También se estudia la NP-Completitud de distintas variantes en que se modifican algunas reglas, así como los efectos de utilizar piezas del ajedrez antiguo. Se investiga asimismo la frontera P de este problema cuando se usa esencialmente un solo tipo de pieza.The purpose of this thesis is to study the computational complexity of the solitaire chess problem, in which given a chess position the player can only make capturing moves with the goal of leaving a single piece on the board, where captures are the only legal moves. We prove that solitaire chess belongs to the class of NP-Complete problems. By using hamiltonian cycle problems on undirected graphs, the NP-Completeness of the game is investigated by restricting the set of pieces to different possibilities using pawns, bishops and rooks. For this purpose, four methods are presented to generate the positions with different properties such as the pieces employed or the ways of mapping each edge of the graph. The methods are compared to illustrate their virtues such as board size and number of pieces required. We also study the NP-Completeness of different variants of the problem in which some rules are modified, as well as the effects of using old chess pieces. The P-frontier of this problem is also investigated when using essentially a single type of piece.Fil: Salvia, Daniel Matías. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina
Sistemas de tipos para λ-cálculo y Lógica Combinatoria
No full textEl λ-cálculo puede verse como un lenguaje de programación universal en el que las funciones son “ciudadanos de primera clase”. Este lenguaje puede representar todas las funciones computables. Resulta de especial interés el estudio de los sistemas tipados. Los tipos permiten una clasificación o “estratificación” del universo de valores y expresiones, en la cual se basan los lenguajes de programación modernos para la rápida detección del uso inapropiado de funciones, métodos, etc. Como una formulación alternativa del λ-cálculo surge la Lógica Combinatoria, que es un sistema de reescritura en cierto sentido más simple pero sin embargo igualmente expresivo. Y del mismo modo que para el λ-cálculo, existen formulaciones de Lógica Combinatoria tipada. En esta tesis se dan pruebas de consistencia para distintas versiones del λ-cálculo tipado. Para esto se plantean métodos de demostración puramente sintácticos, basados en la noción de variable positiva. Estas pruebas son comparadas con otras existentes en la literatura para algunos de los sistemas de tipos analizados. Se estudian las ventajas y limitaciones del método propuesto, identificando sistemas para los cuales éste no resulta aplicable, y sobre algunos de ellos se da una demostración adecuada. Al mismo tiempo, se estudia la Lógica Combinatoria y sus variantes tipadas con el fin de definir un sistema de tipos de segundo orden. Se consideran diferentes opciones para extender el sistema de tipos simples de Curry. El sistema obtenido reshttps://catalogo-intra.exactas.uba.ar/cgi-bin/koha/cataloguing/addbiblio.pl?biblionumber=101824#tab6XXulta equivalente al sistema de tipos polimórficos Fη del λ-cálculo, presentado por Mitchell.Fil: Viso, Andrés Ezequiel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina
Traducciones entre lambda-cálculos con patrones
No full textNuestro trabajo estudia relaciones entre distintos λ-cálculos con patrones a través de la definición de traducciones entre ellos, a nivel sintáctico. Presentamos la traducción de un gran fragmento del cálculo lambda con patrones múltiples (λC) al cálculo lambda con constructores (λB_c). Esto tiene como fin la posibilidad de compilación de un lenguaje de características y operaciones complejas que están “internalizadas", como el primero, en un lenguaje con un sistema de patrones minimales dados por el análisis por casos sobre constantes básicas, como el segundo, que incluye a cambio un conjunto de reglas de propagación de este constructor de análisis por casos. Tenemos también interés en codificar con combinadores ciertos cálculos con patrones. Para esto, presentamos una formulación de un cálculo de combinadores para λB_c. Si bien los combinadores S y K clásicos de la lógica combinatoria son funcionalmente completos (en el sentido de que permiten expresar todos los términos del cálculo lambda), proponemos una extensión de esta lógica a través de otros combinadores posibles para la propagación del constructor del análisis de casos, con el fin de obtener un sistema funcionalmente completo y minimal de combinadores para λB_c. Así, se provee un mecanismo de implementación del pattern matching del mismo modo que la lógica combinatoria clásica provee una implementación del cálculo lambda. Para este nuevo sistema probamos su capacidad de abstracción y la confluencia (la cual garantiza la unicidad de formas normales).Our work studies relations between different λ-calculi with patterns by means of translations between them, to the syntactical level. We present the translation of a big fragment of the λ-calculus with multiple patterns (λC) to the λ-calculus with constructors (λB_c). This has as goal to make it possible to compile a language of complex characteristics and operations which are internalized, like the former, into another with a minimal pattern system given by the case construct over basic constants, like the latter, which in turn includes a set of rules for propagating this case construct. We are also interested in coding with combinators certain pattern calculi. For this task we present a formulation of a combinator calculus for λB_c. Although the classical combinators S and K of combinatory logic are functionally complete (in the sense that they can represent all the λ-calculus terms), we propose an extension of this logic by means of other possible combinators for handling the propagation of the case construct, the goal being to obtain a minimal functionally complete system of combinators for λB_c. Therefore, a mechanism for implementing pattern matching is given, much in the same way as classical combinatory logic provides an implementation of λ-calculus. For this new system we prove its capability of abstraction and its con uence (which guarantees the uniqueness of normal forms).Fil:Santi, Lucio. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
: Explicit substitution systems and subsystems
Get PDFEsta tesis trata acerca de alguinos problemas en la teoría de reescritura y cálculos con sustituciónes explícitas. El tema principal es el estudio de sub cálculos de algunos sistemas de reescritura. Luego de una introducción sesgada a la reescritura, el cálculo lamba y las sustituciónes explícitas, hacemos un estudio comparativo de los principales formalismos de la reescritura, identificando una jerarquía entre éstos. Como primer aproximación a nuevos cálculos, estudiamos el cálculo lambda con nombres de Revesz, que utiliza cuatro reglas de reescriotura, con la particularidad de que no cuenta con sustirución alguna. Se prueba la correctitud relativa y la confluencia. También se proponen y se estudian dos versiones que usan índices de de Bruijn, y se prueba que estas dos propiedades se preservan. Luego pasamos a la perpetualidad en el cálculo de sustituciónes explícitas lambda v y estudiamos estrategias de reducción perpertias, i.e. aquellas que preservan la posibilidad de derivaciónes infinitas. Se da como una aplicación un conjunto de reglas de inferencia determinísticas que caracterizan inductivamente el sub sistema de los términos fuertemente normalizantes, y presentamos una estrategia de reducción perpetia efectiva para lambda v. A continuación se estudian distintas extensiones del cálculo lambda v, con reglas al estilo de las de composición. Se prueba la confluencia débil sobre términos abiertos. Como aplicación de lo anterior, se puede dar un cálculo simplificado, derivado de lambda v, que usa un solo índice de de Bruijn, el cual es un sub cálculo del anterior y con las mismas propiedades. Se demuestra luego la normalización débil del cálculo lambda Se simplemente tipado sobre términos abiertos, en donde las abstracciones se decoran con tipos, y las meta variables, índices de de Bruijn y operadores de actualización se decoran con contextos. La prueba se basa en el cálculo Lambda omega e, que sobre términos semi-abiertos (i.e. aquellos que admiten variables de término pero no de sustitución) es isomorfo a Lambda Se sobre términos abiertos. Esta prueba está fuertemente influenciada por otra previa de normalización débil para el cálculo lambda sigma simplemente tipado pero con diferencias substanciales que indican que los dos estilos requieren distinto tratamiento. Además, introducimos el cálculo lambda omega e, sub cálculo de lambda omega e, el cual usa sólo un índice de de Bruijn, con lo que es más cercano a lambda sigma que lambda omega e. Para lambda omega'e tipado probamos también la normalización débil sobre términos tipados semi-abiertos. Presentamos una extensión del cálculo lambda (nu) que incluye un constructor de casos primitivo que se propaga a través de las abstracciónes como una sustitución lineal de cabeza antes de actuar sobre los constructores, y probamos que este modo de descomposición del apareamiento de patrones permite recuperar la expresividad del estilo de los patrones de ML. Se demuestra que este sistema satisfase confluencia, usando una técnica de "dividir y conquistar" semi automática por al cual se determinan todo los pares de sub sistemas de este cálculo que conmutan (considerando todas las combinaciones de las nueve reglas de reducción). Finalmente, se prueba un teorema de separación (débil) para todo el formalismo, usando una técnica de separación inspirada en la técnica Böhm-out. Por último, como otra faceta de exploración de sub cálculos, analizamos los términos que se satisfacen la propiedad de expandir a términos puros, para lambda v y lambda S. Probamos que estos conjuntos de términos con propios yu no recursivos. Como aplicación, se prueba la imposibilidad de mapeos adecuados entre ciertos pares de cálculos.This thesis is about some problems on rewriting theory and explicit substitution calculi. The main topic is the study of sub-calculi for several rewriting systems. After a biased introduction to rewriting, lambda-calculus and explicit substitution, we make a compatative study of the mail rewriting formalisms, identifying a hierarchy between them. As a first approach to new calculi, we address Revesz'lambda-calculus with names, involving four rewriting rules, with the particularity that it does not have any substitution at all. We show the relative soundness and the confluence. We also propose and study two versions using de Bruijn indices, proving that all these properties are preserved. We then move to perpetuality in the lambda v explicit substitution calculus, and study perpetual rewrite strategies, i.e. those strategies that preserve the possibility of infinite derivarions. We give as an application a set of deterministic inference rules wich characterize inductively the subsystem of strongly normalizing terms, and we present an effective perpetual reduction strategy for lambda v. Then we study different extensions of lambda v-calculus, with the addition of composition-like rules. Weak confluence on open terms is proved. As an application, a derived simplification of lambda v with a unique de Bruijn index can be given, which is a sub-calculus of the former and has the same properties. We show the weak normalization of the simply-typed lambda Se-calculus with open terms where abstractions are decorated with types, and meta-variables, de Bruijn indices and updating operators are decorated whit environments. The proof is based on the lambda omega e-calculus, a calculus wich over semi-open terms (i.e. those wich allow term variables but not substitution variables) is isomorphic to lambda Se, over open terms. This proof is strongly influenced by a previous proof of weak normalization for the simply-typed lambad sigma-calculus but with subtle differences which show that the two styles require different attention. Ferthermore, we give a new calculus, lambda omega'e, sub-calculus of lambda omega e, which handles a unique de Bruijn index, which is then closer to lambda sigma than lambda omega e. For lambda omega'e we also prove the weak normalization for typed semi-open terms. We present an extension of the lambda nu-calculus with a primitive case construct that propagares through abstractions like a head linear substitution before doing constructor substitution, and show that this way of decomposing pattern matching allows to recover the expressiveness of ML-style pattern matching. Then we prove that this system enjoys confluence using a semi-automatic "divide and conquer" technique by wich we determine all the pairs of commuting subsystens of the fornalism (considering all the possible combinations of the nine reduction rules). Finally, we prove a (weak) separation theorem for the whole formalism, using a separation technique inspired by the Bóhm-out technique. And, as another facet of sub-calculi exploration, we inverstigate the terms wich satisfy the property of expansion to pure terms, for lambda v and lambad S. We prove that these sets of terms are proper and non-recursive. As an application, we prove the impossibility id adequate mapping between certain pairs of calculi.Fil:Arbiser, Ariel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Valor mixto en distintas formas de la paradoja del examen sorpresa
Get PDFSe formula y estudia la paradoja del examen sorpresa para n días como juego de suma cero entre dos jugadores, el docente y el alumno, considerando los costos de estudio por día y el costo que representa el ser examinado en forma imprevista, permitiendo que el docente pueda tomar el examen cualquiera de los n días o incluso ninguno de ellos, y que el alumno pueda elegir para estudio cualquier subconjunto de esos n días (desde ninguno hasta todos). Calculamos el valor mixto de este juego en función del número de días y del costo de la posible sorpresa, y analizamos el rol de esta sorpresa como determinante para la eliminación de estrategias.Sociedad Argentina de Informática e Investigación Operativ
El costo de eliminación de equilibrios en juegos de suma cero
Get PDFEstudiamos el problema de la eliminación de equilibrios de Nash en juegos de suma cero para dos jugadores usando mínimos cambios. Damos algoritmos lineales que, dado un juego, calculan otro sin equilibrios a distancia óptima o sub óptima, de acuerdo a distintas métricas, preservando los dominios de valores así como otras propiedades del juego. Exhibimos para esto distintos sistemas de reglas que, en base a patrones dados por formas ordinales, guían en el proceso de cambio sobre la matriz de pagos.Sociedad Argentina de Informática e Investigación Operativ
- …
