|
Article Excerpt
Nondeterminism is an essential concept in mathematics and one of the important concepts in computer science. It is also among the most abstract ones. Thus, many students find it difficult to cope with. In this article, we describe some didactic considerations, which guided the development of a "Computational Models" course for high school students, a course in which the concept of nondeterminism is introduced. Some of these considerations are relevant to college and university students as well. We also discuss students' perceptions of nondeterminism and their achievements in this area. Our findings show that many students prefer to avoid nondeterminism, even when it can significantly simplify the solution's design process. We analyze and categorize the students' solutions, thus shedding light on their perceptions of the abstract concept of nondeterminism.
**********
Nondeterminism is an essential concept in computer science as well as in mathematics. In a typical bachelor CS program, the concept is introduced in the computational models course, and is often discussed again later in an artificial intelligence course. Sometimes it is also discussed in the context of operating systems and distributed algorithms. In a traditional high school program, the concept is rarely included. A high school student may, in a sense, be exposed to the concept when studying probability theory. In that context, nondeterminism is forced by the random nature of events.
In the CS high school curriculum described by Gal-Ezer, Beeri, Harel and Yehudai (1995; Gal-Ezer & Harel, 1999) the concept of nondeterminism is introduced in the Computational Models (CM) unit. The CM unit motivates the need for nondeterministic computational models, and encourages students to choose them, even when deterministic models are sufficient, by demonstrating their advantages.
This unit is unique, compared to other units in this curriculum, and to the best of our knowledge is also unique compared to other high school curricula in other countries. For example, the ACM high school computer science curriculum (Merritt, 1994) includes very few references to few of the topics of the CM unit, only as optional topics, and the more recent ACM K-12 computer science curriculum (Tucker, Deek, Jones, McCowan, Sthepenson, & Verno, 2003) mentions only limits of computability, in one of its five units, as one topic among 10.
In this article we describe the introduction of nondeterminism in the CM unit, and the didactic considerations that guided it, some of which can be applied on college and university levels as well. We also describe the results of a study we conducted on the perception of nondeterminism (partial information on this study was given in Armoni & Gal-Ezer, 2003). This study was part of a wider study, which examined various aspects of the teaching and learning process of the CM unit, such as students' achievements (Armoni & Gal-Ezer, 2004), teaching reductive thinking (Armoni & Gal-Ezer, 2005), and the tendency of students to choose reductive solutions (Armoni, Gal-Ezer, & Tirosh, 2005). The aspect of nondeterminism studied here focuses on the level of use of nondeterminism by students when they have freedom of choice, from which we can deduce their perceptions of this concept.
This article is organized as follows: in the second section " Computational Models in a High School CS Curriculum" we give a brief description of the CM unit; the third section "The Introduction of Nondeterminism" describes the way nondeterminism is introduced; the fourth section "The Study" describes the findings of our study regarding the perception of nondeterminism. Our conclusions and suggestions for further research are discussed in the fifth and last section.
COMPUTATIONAL MODELS IN A HIGH SCHOOL CS CURRICULUM
The CM unit is part of a high school curriculum described in detail in Gal-Ezer et al. (1995) and Gal-Ezer and Harel (1999). According to this curriculum, students who decide to take a comprehensive computer science program, study five 90 hours courses (units), taught over two or three school years. The last unit is one of the two elective units in this curriculum, and one of the alternatives offered for it is the CM unit. The CM unit is unique, compared to other units of this curriculum, since an important portion of it is dedicated to discussing properties of abstract computational models, rather than implementations within these models. It is the only unit in the curriculum, which does not have a clear aspect of solving algorithmic problems and implementing the solutions in a programming language.
CM introduces finite automata (deterministic and nondeterministic), pushdown automata, and Turing machines. We will elaborate on the choice of these models in the following subsection. The unit demonstrates and drills automata design, but it also discusses the theoretical properties of each model: computational power (in relation to previously introduced models), computational limits and closure properties.
The main educational goal of the CM unit is to expose students to theoretical thinking patterns, which are mathematical in nature, including abstraction and generalization (demonstrated by defining abstract models, inspired by simple automatic machines), abstract analysis (demonstrated by investigating the introduced computational models and their properties) and abstract conceptual flexibility (demonstrated by various changes in the definitions of models and by investigating the effect of such changes).
To preserve the uniqueness of the CM unit, compared to other units in this high school CS curriculum, it was decided to focus on theoretical issues, and to relate to automata design as a tool exploited in theoretical discussions. Therefore, this unit intentionally does not mention "real life" various applications of computational models, such as compilers, natural language processing, and so forth, nor does it integrate any simulation or visualization tools into the teaching process. We assumed that introducing such tools would only affect the perception of the technical aspects (i.e., designing automata), aspects which we found to be easier to cope with (Armoni & Gal-Ezer, 2004). Also, since such tools are usually quite attractive, and since most high school students are not fully mature, we were afraid they might invest too much time and attention in these tools, disrupting the learning process of the theoretical aspects.
The CM unit was developed by a team chaired by the first author, in consultation with the second. The teaching process is guided by a textbook and a teacher guide especially designed for the unit.
The Choice of Models
To fit into the 90 hours limit, not all classical models, traditionally introduced in a college or university computational models course, could be introduced in the CM unit. A didactic decision had to be taken, regarding the choice of models. The CM unit focuses on models, which are automata-based and does not introduce other common models, such as regular expressions or grammars. This restriction leaves us with relatively "concrete" models, as they resemble real automatic machines, and thus may be easier to cope with for high school students. In addition, these models have very similar definitions, enabling the introduction of each new model as based on the preceding one. This minimizes the conceptual adaptation that a student needs to learn a new model. For example, the Turing machine model is presented as a generalization of pushdown automata, achieved by permitting access to cells beneath the top cell of the stack. In spite of the restriction to automata-based models the chain of models we introduce is rich enough and enables meaningful theoretical discussion, through which major concepts in computer science are introduced: Some models are equivalent and some are not, some models are nondeterministic, some models differ in their closure properties and in the contribution of nondeterminism to their computational power, and one of the models is equivalent to a computer program (or an algorithm).
The CM Unit Syllabus
The CM unit consists of three parts: (a) finite automata, (b) pushdown automata, and (c) Turing machines.
The first part introduces three computational models: Deterministic Finite Automata (DFA), Noncomplete Deterministic Finite Automata (NCDFA) and Nondeterministic Finite Automata (NFA). The introduction of each new model is followed by a technical part, which focuses on designing automata within this model, and then there is a theoretical discussion. The theoretical aspects discussed in the first part include the definition of regular languages, computational limits (that is, the existence of nonregular languages), equivalence of the three models and some closure properties.
The second part of the CM unit focuses on the Pushdown Automata model (PDA). Again, the technical part is followed by a theoretical discussion in which PDA are proved to be stronger than finite automata, the computational limits of the model are discussed, and some closure properties of the family of languages accepted by this model (context-free languages) are proved.
The third and final part of the CM unit is dedicated to the Turing Machine model (TM). The technical aspects include designing simple machines that accept formal languages, and simple machines that calculate functions. The theoretical aspects include a discussion of the computational power of TM (i.e., the Church-Turing thesis) and, in particular, the equivalence of the new model to a computer; and a discussion of the new model computational limits, demonstrated by proving the noncomputability of the halting problem.
THE INTRODUCTION OF NONDETERMINISM
The concept of nondeterminism is introduced and discussed in the fourth chapter of the CM unit, which takes about 15 hours.
We chose a way somewhat different from the traditional way of introducing nondeterminism. The nondeterministic finite automaton (NFA) model is usually defined as a straightforward version of the deterministic finite automaton (DFA) (Hopcroft & Ullman, 1979). In a DFA, the transition function maps each pair of a state and an input letter to a single state, while in an NFA, the transition function maps each pair of a state and an input letter to a set of states (which may also be empty). Figure 1 shows an NFA, accepting the...
|
