Search
Search Results
-
Some logical issues in discrete mathematics and algorithmic thinking
243-258Views:98The role of logic in mathematics education has been widely discussed from the seventies and eighties during the “modern maths period” till now, and remains still a rather controversial issue in the international community. Nevertheless, the relevance of discrete mathematics and algorithmic thinking for the development of heuristic and logical competences is both one of the main points of the program of Tamás Varga, and of some didactic teams in France. In this paper, we first present the semantic perspective in mathematics education and the role of logic in the Hungarian tradition. Then, we present insights on the role of research problems in the French tradition. Finely, we raise some didactical issues in algorithmic thinking at the interface of mathematics and computer science.
Subject Classification: 97E30
-
Learning and teaching combinatorics with Sage
389-398Views:44Learning Mathematics is not an easy task, since this subject works with especially abstract concepts and sophisticated deductions. Many students lose their interest in the subject due to lack of success. Computer algebra systems (CAS) provide new ways of learning and teaching Mathematics. Numerous teachers use them to demonstrate concepts, deductions and algorithms and to make learning process more interesting especially in higher education. It is an even more efficient way to improve the learning process, if students can use the system themselves, which helps them to practice the curriculum.
Sage is a free, open-source math software system that supports research and teaching algebra, analysis, geometry, number theory, cryptography, numerical computation, and related areas. I have been using it for several years to aid the instruction of Discrete Mathematics at Óbuda University. In this article I show some examples how representations provided by this system can help in teaching combinatorics. -
Simple Variations on The Tower of Hanoi: A Study of Recurrences and Proofs by Induction
131-158Views:127The Tower of Hanoi problem was formulated in 1883 by mathematician Edouard Lucas. For over a century, this problem has become familiar to many of us in disciplines such as computer programming, algorithms, and discrete mathematics. Several variations to Lucas' original problem exist today, and interestingly some remain unsolved and continue to ignite research questions. Nevertheless, simple variations can still lead to interesting recurrences, which in turn are associated with exemplary proofs by induction. We explore this richness of the Tower of Hanoi beyond its classical setting to compliment the study of recurrences and proofs by induction, and clarify their pitfalls. Both topics are essential components of any typical introduction to algorithms or discrete mathematics.
Subject Classification: A20, C30, D40, D50, E50, M10, N70, P20, Q30, R20
-
From iteration to one - dimensional discrete dynamical systems using CAS
271-296Views:20In our paper we present the basic didactical framework and approaches of a course on one-dimensional discrete dynamical systems made with the help of Computer Algebra Systems (CAS) for students familiar with the fundamentals of calculus. First we review some didactical principles of teaching mathematics in general and write about the advantages of the modularization for CAS in referring to the constructivistic view of learning. Then we deal with our own development, a CAS-based collection of programs for teaching Newton's method for the calculation of roots of a real function. Included is the discussion of domains of attraction and chaotic behaviour of the iterations. We summarize our teaching experiences using CAS. -
Teaching graph algorithms with Visage
35-50Views:27Combinatorial optimization is a substantial pool for teaching authentic mathematics. Studying topics in combinatorial optimization practice different mathematical skills, and because of this have been integrated into the new Berlin curriculum for secondary schools. In addition, teachers are encouraged to use adequate teaching software. The presented software package "Visage" is a visualization tool for graph algorithms. Using the intuitive user interface of an interactive geometry system (Cinderella), graphs and networks can be drawn very easily and different textbook algorithms can be visualized on the graphs. An authoring tool for interactive worksheets and the usage of the build-in programming interface offer new ways for teaching graphs and algorithms in a classroom. -
A didactic analysis of merge sort
195-210Views:22Due to technical difficulties, educators teaching merge sort often avoid the analysis of the cost in the general and average cases. Using basic discrete mathematics, elementary real analysis and mathematical induction, we propose a self-contained derivation of bounds αn log_2 n + βn + γ in all cases. Independent of any programming language or pseudo-code, supported by intuitive figures, it is suitable for informatics students interested in the analysis of algorithms. It is also a good exercise in showing that induction allows us to actually discover constants, instead of simply checking them a posteriori. -
Linear clause generation by Tableaux and DAGs
109-118Views:31Clause generation is a preliminary step in theorem proving since most of the state-of-the-art theorem proving methods act on clause sets. Several clause generating algorithms are known. Most of them rewrite a formula according to well-known logical equivalences, thus they are quite complicated and produce not very understandable information on their functioning for humans. There are other methods that can be considered as ones based on tableaux, but only in propositional logic. In this paper, we propose a new method for clause generation in first-order logic. Since it inherits rules from analytic tableaux, analytic dual tableaux, and free-variable tableaux, this method is called clause generating tableaux (CGT). All of the known clause generating algorithms are exponential, so is CGT. However, by switching to directed acyclic graphs (DAGs) from trees, we propose a linear CGT method. Another advantageous feature is the detection of valid clauses only by the closing of CGT branches. Last but not least, CGT generates a graph as output, which is visual and easy-to-understand. Thus, CGT can also be used in teaching logic and theorem proving.