Página 9 dos resultados de 10730 itens digitais encontrados em 0.062 segundos

On the asymptotic enumeration of accessible automata

LEBENSZTAYN, Elcio
Fonte: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE Publicador: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
555.33023%
We simplify the known formula for the asymptotic estimate of the number of deterministic and accessible automata with n states over a k-letter alphabet. The proof relies on the theory of Lagrange inversion applied in the context of generalized binomial series.; CNPq[311909/2009-4]

Control and estimation for large-scale systems having spatial symmetry

Wall, Joseph Edward
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 266 leaves; 12000117 bytes; 11999870 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
563.0107%
by Joseph Edward Wall, Jr.; Thesis. 1978. Ph.D.--Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.; MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING.; Vita.; Includes bibliographical references.

Finite-state control of uncertain systems.

Jones, Steven Norman
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 122 leaves; 5757713 bytes; 5757468 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
560.37055%
Thesis. 1978. M.S.--Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.; MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING.; Includes bibliographical references.

Degree Bounds on Polynomials and Relativization Theory

Spakowski, Holger ; Tripathi, Rahul
Fonte: University of Rochester. Computer Science Department. Publicador: University of Rochester. Computer Science Department.
Tipo: Relatório
Português
Relevância na Pesquisa
563.0107%
We demonstrate the applicability of the polynomial degree bound technique to notions such as the nonexistence of Turing-hard sets in some relativized world, (non)uniform gap-definability, and relativized separations. Our contributions are as follows.

(a) There is a relativized world where AWPP has no polynomial-time Turing hard set for UP cap coUP. This implies that classes like SPP, LWPP, WPP and AWPP do not possess Turing complete sets robustly; thus we answer an open question of [HRZ95] and extend one of the main results of [HJV93].

(b) There is a relativized world where AWPP has no polynomial-time Turing hard set for ZPP.

(c) There is a relativized world where UP cap coUP is not low for LWPP as well as for WPP. As a consequence, we show that both LWPP and WPP are not uniformly gap-definable. This settles an open question of [FFK94] and gives a relativized answer to another question of [FFK94].

(d) There is a relativized world where NP cap coNP subseteq AWPP.

(e) There is a relativized world where ZPP is not contained in WPP^{WPP}. Thus WPP differs considerably from its superclass C_{=}P, for which it is known that PH subseteq C_{=}P^{C_{=}P} in every relativized world.

(f) Finally, we demonstrate that our proof technique is applicable also to classes that are not known to be gap-definable. We construct a relativized world where MIP cap coMIP has no polynomial-time Turing hard set for ZPP. This extends one of the main results of [HJV93].

Algorithms from Complexity Theory: Polynomical-Time Operations for Complex Sets

Hemachandra, Lane A.
Fonte: University of Rochester. Computer Science Department. Publicador: University of Rochester. Computer Science Department.
Tipo: Relatório
Português
Relevância na Pesquisa
555.58508%
Typically, a set is described as complex when its membership problem has no efficient solution. Many sets of central interest for data management, design of computer chips, scheduling, fault-tolerant network design, and general optimization - such as the NP-complete sets - are thought to be complex in this sense. Though much effort has been spent accumulating evidence of the infeasibility of membership testing for these sets, less effort has been spent determining which operations can be efficiently performed on complex sets. This paper surveys recent advances in the study of the sets for which fundamental operations - data compression and hashing, approximate membership testing, and enumeration - can be performed efficiently. We will see that many sets traditionally viewed as complex nonetheless have efficient algorithms for these operations.

Language Instance Generation and Test Case Construction for NP-hard Problems

Sanchis, Laura A.
Fonte: University of Rochester. Computer Science Department. Publicador: University of Rochester. Computer Science Department.
Tipo: Relatório
Português
Relevância na Pesquisa
563.0107%
Ph.D. Thesis, Computer Science Dept., U. Rochester; Prof. Mark A. Fulk, thesis advisor; simultaneously published in the Technical Report series.; This dissertation deals with the construction and generation of language instances, and with the related problem of constructing test cases for the empirical testing of approximation algorithms for NP-hard problems. In the first part of the thesis some theoretical aspects of language instance generation are investigated, especially in relation to other areas of complexity theory. Generators and constructors are machines that output instances of a language having certain characteristics, such as length, as specified by the input. Various types of generating machines are defined and the language classes having such machines are classified. Of particular interest are the languages that have efficient (polynomial-time) generators. Although only NP languages may have polynomial-time generators, it is shown that determining whether or not all NP languages have polynomial-time generators is related to other open problems in complexity theory, and that even under the assumption that P does not equal NP, the question cannot be resolved using techniques that relativize. The need to generate or construct structures having certain properties comes up in many circumstances and applications. One of these is the construction of test cases for the empirical testing of algorithms. When testing approximation algorithms for NP-hard problems...

Towards automated derivation in the theory of allegories

Glanfield, Joel.
Fonte: Brock University Publicador: Brock University
Tipo: Electronic Thesis or Dissertation
Português
Relevância na Pesquisa
561.70273%
We provide an algorithm that automatically derives many provable theorems in the equational theory of allegories. This was accomplished by noticing properties of an existing decision algorithm that could be extended to provide a derivation in addition to a decision certificate. We also suggest improvements and corrections to previous research in order to motivate further work on a complete derivation mechanism. The results presented here are significant for those interested in relational theories, since we essentially have a subtheory where automatic proof-generation is possible. This is also relevant to program verification since relations are well-suited to describe the behaviour of computer programs. It is likely that extensions of the theory of allegories are also decidable and possibly suitable for further expansions of the algorithm presented here.

Algebraic theory of minimal nondeterministic finite automata with applications

Cazalis, Daniel
Fonte: FIU Digital Commons Publicador: FIU Digital Commons
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
563.0107%
Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. ^ An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA’s behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials...

Performance Models for Electronic Structure Methods on Modern Computer Architectures

Antony, Joseph
Fonte: Universidade Nacional da Austrália Publicador: Universidade Nacional da Austrália
Tipo: Thesis (PhD); Doctor of Philosophy (PhD)
Português
Relevância na Pesquisa
562.39746%
Electronic structure codes are computationally intensive scientic applications used to probe and elucidate chemical processes at an atomic level. Maximizing the performance of these applications on any given hardware platform is vital in order to facilitate larger and more accurate computations. An important part of this endeavor is the development of protocols for measuring performance, and models to describe that performance as a function of system architecture. This thesis makes contributions in both areas, with a focus on shared memory parallel computer architectures and the Gaussian electronic structure code. Shared memory parallel computer systems are increasingly important as hardware man- ufacturers are unable to extract performance improvements by increasing clock frequencies. Instead the emphasis is on using multi-core processors to provide higher performance. These processor chips generally have complex cache hierarchies, and may be coupled together in multi-socket systems which exhibit highly non-uniform memory access (NUMA) characteristics. This work seeks to understand how cache characteristics and memory/thread placement affects the performance of electronic structure codes, and to develop performance models that can be used to describe and predict code performance by accounting for these effects. A protocol for performing memory and thread placement experiments on NUMA systems is presented and its implementation under both the Solaris and Linux operating systems is discussed. A placement distribution model is proposed and subsequently used to guide both memory/thread placement experiments and as an aid in the analysis of results obtained from experiments. In order to describe single threaded performance as a function of cache blocking a simple linear performance model is investigated for use when computing the electron repulsion integrals that lie at the heart of virtually all electronic structure methods. A parametric cache variation study is performed. This is achieved by combining parameters obtained for the linear performance model on existing hardware...

Development of intelligent computer-assisted instruction systems to facilitate reading skills of learning-disabled children

Anderson, Patricia M.
Fonte: Monterey, California. Naval Postgraduate School Publicador: Monterey, California. Naval Postgraduate School
Tipo: Tese de Doutorado Formato: 90 p.
Português
Relevância na Pesquisa
558.659%
Approved for public release; distribution is unlimited; The purpose of this thesis is to develop a high-level model to create self-adapting software which teaches learning-disabled (LD) children to read. This approach identifies and discusses the fundamental concepts of learning, motivation, learning disabilities, the Theory of Multiple Intelligences, computer games, and intelligent computer-aided learning (ICAL). These concepts are then integrated into the design of a model that manipulates these concepts to teach reading skills. The result of this effort is CAPER (Computer-Assisted Personal Education Resource). It is model of a system that will: (a) identify the individual's dominant learning styles, (b) tailor the instruction and presentation to those styles, and (C) present the lessons in an interactive game-like style will retain the child's interest and enhance the learning process.; http://archive.org/details/developmentofint00ande; Captain, United States Army

Computer science students' causal attributions for successful and unsuccessful outcomes in programming assignments

Vivian, R.; Falkner, K.; Falkner, N.
Fonte: ACM; Finland Publicador: ACM; Finland
Tipo: Conference paper
Publicado em //2013 Português
Relevância na Pesquisa
560.37055%
While some students excel in introductory programming courses, others find the course to be significantly challenging and demanding. The way that students reason about the factors that contribute to success or failure may affect their self-efficacy, motivation, future success and whether or not they persist in Computer Science (CS). What factors do students' perceive to cause successful or unsuccessful learning outcomes in first-year programming assignments? Such findings can assist us in identifying causal reasoning that may be detrimental to future success and persistence. We use Attribution Theory (AT) as a framework to explore the "causal attributions" that students apply to explain their causes for success or failure in introductory programming assignments, alluded to in their reflective essays about performance in a course. Our research demonstrates that reflective essays, integrated into learning tasks, can be one effective and efficient way to extract students' casual attributions. Our results indicate that the students raised a number of causal attributions in their essays that were specific to the CS-context and were attributed to both internal and external causes. We highlight problematic areas of casual reasoning and a need to correct misleading reasoning to ensure CS students understand their control over the success of their future programming assignments. This research offers opportunities for future research to develop activities that may encourage students to correctly identify causes of performance outcomes in programming assignments and to determine if such interventions can prevent students from leaving CS.; Rebecca Vivian...

Omnispective analysis and reasoning: an epistemic approach to scientific workflows

Chemboli, Srinivas
Fonte: Universidade Nacional da Austrália Publicador: Universidade Nacional da Austrália
Tipo: Thesis (PhD); Doctor of Philosophy (PhD)
Português
Relevância na Pesquisa
561.17918%
This thesis presents the conceptualization, formulation, development and demonstration of Omnispective Analysis and Reasoning (OAR), an epistemic framework for managing intellectual concerns in scientific workflows. Although scientific workflows are extensively used to support the management of experimental and computational research, intellectual concerns are not adequately handled in current practice owing to the focus on low-level implementation details, limited context support, issues in developing shared semantics across disciplines and lack of support for verification and validation of the underlying science of the workflow. The management of intellectual concerns in scientific workflows can be improved by developing a framework for providing a layer of abstraction to lift focus from low-level implementation details, adding context as a workflow parameter, introducing localized ontologies and abstracting and mapping intellectual concerns in the research-domain to workflow specification and execution semantics. Following an examination of typical definitions of scientific workflow offered in literature, the Scientific Method is applied to develop an enhanced definition of a scientific workflow. This definition, which extends the scope of ordered analysis and investigation to a generic problem scenario...

An introduction to geometric complexity theory

Landsberg, J. M.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 08/09/2015 Português
Relevância na Pesquisa
563.0107%
I survey methods from differential geometry, algebraic geometry and representation theory relevant for the permanent v. determinant problem from computer science, an algebraic analog of the P v. NP problem.; Comment: Draft of article to appear in the Newsletter of the European Mathematical Society. 9 pages in original, arXiv version has extra spaces due to arXiv processing

Analysis of Competence Level and the Attendance of the Lecturer in Its Effects on Students Grade Using Fuzzy Quantification Theory

Mustafidah, Hindayati; Suwarsito
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/09/2014 Português
Relevância na Pesquisa
560.37055%
It known that teachers as educators should have competence that shows its quality so that the lecture material provided can be absorbed by the student. The competencies in this term include the pedagogic, professional, personality, and social. The competence that owned by lecturer can be obtained from the results of the assessment conducted by the student through the filling of the questionnaire. This study conducted an analysis of the level of the lecturer competence of the relationship between the present of lecturer in classroom with a percentage of the value of passing students in courses using fuzzy quantification theory. Based on the results of the four competencies acquired professional competence that contributes most of 79.45% in contributed the attendance of lecturer will it affect the percentage of passing students in courses that are shown with a percentage of the graduation minimum B.; Comment: 5 pages, 1 figure, 5 tables, 4 equations, published with International Journal of Computer Science Issues (IJCSI)

The Computational Theory of Intelligence: Applications to Genetic Programming and Turing Machines

Kovach, Daniel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/12/2014 Português
Relevância na Pesquisa
560.37055%
In this paper, we continue the efforts of the Computational Theory of Intelligence (CTI) by extending concepts to include computational processes in terms of Genetic Algorithms (GA's) and Turing Machines (TM's). Active, Passive, and Hybrid Computational Intelligence processes are also introduced and discussed. We consider the ramifications of the assumptions of CTI with regard to the qualities of reproduction and virility. Applications to Biology, Computer Science and Cyber Security are also discussed.; Comment: Total of 5 figures. This paper was originally presented at RAMSA 2013 in Visakhaptnam, India in December 2013

Denial of Service Attack: Analysis of Network Traffic Anormaly using Queuing Theory

Singh, Neetu; Ghrera, S. P.; Chaudhuri, Pranay
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/06/2010 Português
Relevância na Pesquisa
563.0107%
Denial-of-service (DOS) attacks increasingly gained reputation over the past few years. As the Internet becomes more ubiquitous, the threat of the denial-of-service attacks becomes more realistic and important for individuals, businesses, governmental organizations, and even countries. There is intensive need to detect an attack in progress as soon as possible. The efficiency of diagnosing the DOS attack using concepts of queuing theory and performance parameter of the system has been investigated in the present work, as the servers definitely have some mechanisms to store and process the requests. Utilizing this concept of queuing theory, the collection of data patterns were generated. With the performance parameter of the system, the analysis of the data pattern had been made to diagnose the network anomaly. Performance analysis and results show the accuracy of the proposed scheme in detecting anomalies.; Comment: Submitted to Journal of Computer Science and Engineering, see http://sites.google.com/site/jcseuk/volume-1-issue-1-may-2010

Theory and practice

Knuth, Donald E.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 31/10/1991 Português
Relevância na Pesquisa
560.37055%
The author argues to Silicon Valley that the most important and powerful part of computer science is work that is simultaneously theoretical and practical. He particularly considers the intersection of the theory of algorithms and practical software development. He combines examples from the development of the TeX typesetting system with clever jokes, criticisms, and encouragements.; Comment: Abstract added by Greg Kuperberg

Geometric Complexity Theory: Introduction

Mulmuley, Ketan D.; Sohoni, Milind
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 05/09/2007 Português
Relevância na Pesquisa
564.63543%
These are lectures notes for the introductory graduate courses on geometric complexity theory (GCT) in the computer science department, the university of Chicago. Part I consists of the lecture notes for the course given by the first author in the spring quarter, 2007. It gives introduction to the basic structure of GCT. Part II consists of the lecture notes for the course given by the second author in the spring quarter, 2003. It gives introduction to invariant theory with a view towards GCT. No background in algebraic geometry or representation theory is assumed. These lecture notes in conjunction with the article \cite{GCTflip1}, which describes in detail the basic plan of GCT based on the principle called the flip, should provide a high level picture of GCT assuming familiarity with only basic notions of algebra, such as groups, rings, fields etc.; Comment: 161 pages

All programs are not created equal - but, do students know that?

Etlinger, Henry
Fonte: ACM : Proceedings of the sixteenth SIGCSE technical symposium on Computer science education Publicador: ACM : Proceedings of the sixteenth SIGCSE technical symposium on Computer science education
Tipo: Proceedings
Português
Relevância na Pesquisa
561.31445%
Students in programming courses must deal with multiple aspects of the programming process. They need to learn the syntax and semantics of a given programming language, to explore how to use the language to implement different algorithms, and how to construct programs properly and display them in an acceptable manner. Sometimes, for example in the case of sorting, students see many different algorithms and programs. In this paper, we argue that students can also benefit from seeing multiple program representations of the same algorithm. Students learn that programs can be different and that some programs are easier to understand than others.; © ACM, 1985. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the sixteenth SIGCSE technical symposium on Computer science education. "All Programs Are Not Created Equal - But, Do Students Know That?" Proceedings of the sixteenth SIGCSE technical symposium on Computer science education. Held in New Orleans, Louisiana, United States: 14-15 March 1985.

Digital morphogenesis via Schelling segregation

Barmpalias, George; Elwes, Richard; Lewis-Pye, Andy
Fonte: London School of Economics and Political Science Research Publicador: London School of Economics and Political Science Research
Tipo: Article; PeerReviewed Formato: application/pdf
Publicado em //2014 Português
Relevância na Pesquisa
557.8369%
Schelling's model of segregation looks to explain the way in which particles or agents of two types may come to arrange themselves spatially into configurations consisting of large homogeneous clusters, i.e. connected regions consisting of only one type. As one of the earliest agent based models studied by economists and perhaps the most famous model of self-organising behaviour, it also has direct links to areas at the interface between computer science and statistical mechanics, such as the Ising model and the study of contagion and cascading phenomena in networks. While the model has been extensively studied it has largely resisted rigorous analysis, prior results from the literature generally pertaining to variants of the model which are tweaked so as to be amenable to standard techniques from statistical mechanics or stochastic evolutionary game theory. In \cite{BK}, Brandt, Immorlica, Kamath and Kleinberg provided the first rigorous analysis of the unperturbed model, for a specific set of input parameters. Here we provide a rigorous analysis of the model's behaviour much more generally and establish some surprising forms of threshold behaviour, notably the existence of situations where an \emph{increased} level of intolerance for neighbouring agents of opposite type leads almost certainly to \emph{decreased} segregation.