Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDiscrete Mathematics for Computer Science, Some Notes
109
0
0.0
(
0
)
Added by
Jean Gallier
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Authors
Jean Gallier
Ask ChatGPT about the research
No Arabic abstract
These are notes on discrete mathematics for computer scientists. The presentation is somewhat unconventional. Indeed I begin with a discussion of the basic rules of mathematical reasoning and of the notion of proof formalized in a natural deduction system ``a la Prawitz. The rest of the material is more or less traditional but I emphasize partial functions more than usual (after all, programs may not terminate for all input) and I provide a fairly complete account of the basic concepts of graph theory.
rate research
Read More
These notes were originally developed as lecture notes for a category theory course. They should be well-suited to anyone that wants to learn category theory from scratch and has a scientific mind. There is no need to know advanced mathematics, nor any of the disciplines where category theory is traditionally applied, such as algebraic geometry or theoretical computer science. The only knowledge that is assumed from the reader is linear algebra. All concepts are explained by giving concrete examples from different, non-specialized areas of mathematics (such as basic group theory, graph theory, and probability). Not every example is helpful for every reader, but hopefully every reader can find at least one helpful example per concept. The reader is encouraged to read all the examples, this way they may even learn something new about a different field. Particular emphasis is given to the Yoneda lemma and its significance, with both intuitive explanations, detailed proofs, and specific examples. Another common theme in these notes is the relationship between categories and directed multigraphs, which is treated in detail. From the applied point of view, this shows why categorical thinking can help whenever some process is taking place on a graph. From the pure math point of view, this can be seen as the 1-dimensional first step into the theory of simplicial sets. Finally, monads and comonads are treated on an equal footing, differently to most literature in which comonads are often overlooked as just the dual to monads. Theorems, interpretations and concrete examples are given for monads as well as for comonads.
In this article we consider mathematical fundamentals of one method for proving inequalities by computer, based on the Remez algorithm. Using the well-known results of undecidability of the existence of zeros of real elementary functions, we demonstrate that the considered method generally in practice becomes one heuristic for the verification of inequalities. We give some improvements of the inequalities considered in the theorems for which the existing proofs have been based on the numerical verifications of Remez algorithm.
Quasi-symmetry of a steady magnetic field means integrability of first-order guiding-centre motion. Here we derive many restrictions on the possibilities for a quasi-symmetry. We also derive an analogue of the Grad-Shafranov equation for the flux function in a quasi-symmetric magnetohydrostatic field.
Proposed initially from a practical circumstance, the traveling salesman problem caught the attention of numerous economists, computer scientists, and mathematicians. These theorists were instead intrigued by seeking a systemic way to find the optimal route. Many attempts have been made along the way and all concluded the nonexistence of a general algorithm that determines optimal solution to all traveling salesman problems alike. In this study, we present proof for the nonexistence of such an algorithm for both asymmetric (with oriented roads) and symmetric (with unoriented roads) traveling salesman problems in the setup of constructive mathematics.
This work is thought as an operative guide to discrete exterior calculus (DEC), but at the same time with a rigorous exposition. We present a version of (DEC) on cubic cell, defining it for discrete manifolds. An example of how it works, it is done on the discrete torus, where usual Gauss and Stokes theorems are recovered.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
