- •Звіт з практики
- •Завдання на практику
- •Завдання на навчальну практику
- •Анотація
- •Календарний план
- •Календарний план
- •Українські пошукові системи
- •Основні пошукові машини і каталоги Internet- ресурсів
- •Англомовні пошукові системи
- •Російські пошукові системи
- •Англомовні навчальні матеріали для набору та редагування
- •Підбір матеріалів на задану тематику
- •Перелік використаних джерел та літератури. Додатки
Перелік використаних джерел та літератури. Додатки
TRANSLATION ALGORITHMS
Algorithms have existed since ancient times. The execution of a sum of 2 numbers with many digits follows an algorithm; the well known "Euclid Algorithm" for the calculation of a maximal common divisor, if its author may be assumed to be its discoverer, dates to the 3rd century BC.
Today, the notion and domain of algorithms has become absolutely essential, because every "working" computer program, that is, producing the expected results, is probably a description of an algorithm. (If the reader finds the "probably" a bit strange, he or she probably needs to better understand what algorithms are and what programs are...) Furthermore, if one wishes to develop a program for a computer, the correct way of doing it would be to initially look for the most adequate method for the solution to a problem, specifying this solution as an algorithm and, afterwards, expressing it in some computer language for its insertion into the computer, followed by its (automatic) interpretation or translation into machine language, and its execution.
From an educational point of view, it seems to us essential that one teaches that "programming a computer" does not mean giving the machine some commands expressed in the syntax of some programming language, modifying and then rearranging them until the expected result is obtained, as happens with an electronic (video) game. The essence of programming and computing, the subject that should really attract students’ interest to that area, is the development and analysis of algorithms.
This paper presents a teaching activity based upon the notion of algorithms and their complexity analysis. According to our experience, we consider it to be adequate to the senior high school classes. Its duration is approximately 3 hours. It does not require previous computing experience from students. It employs some physical pedagogical material, presenting a problem with numbers in the form of a competitive manual game. The students solve the problem in groups, having a reasonable space for exercising their creativity.
Afterwards they compare the different solutions obtained by different groups. In the sequel, the instructor makes an abstraction of the concepts involved in the solution of the proposed problem, and presents a more complex and efficient solution. Then he or she introduces advanced concepts such as algorithm correctness and complexity, the notion of an optimal algorithm and the intractability of certain problems. All this is done without any connection to a computer, so the availability of such machines is not necessary for introducing conceptual notions of computing and programming. On the other hand, if computers are available, our method may serve for the introduction of practical programming.
This notion of the optimal algorithm is quite useful to illustrate the importance of Computing Theory, in particular Algorithmic Analysis. Most professionals, if not all of them, become satisfied when they find an algorithm which solves a problem, without questioning if there is a better algorithm and its "distance" from the theoretical optimum. Unfortunately, computers have become very cheap and fast, so if an algorithm is badly chosen and designed, and the machine is taking to long to give the expected solutions, one just buys a more powerful, faster one.
If the instructor’s manager had asked for a linear sorting algorithm using comparisons, knowledge of the theory would permit the instructor to dismiss his task without having lost his job for not accomplishing it.
The problem of optimal sort has been solved, but there exist other open problems, which are the subject of research in the area of algorithmic analysis. Research is done both in order to obtain better algorithms, as well as to demonstrate optimal complexities, that is, of the non-existence of better algorithms if the optimal has already been reached.
The travelling salesman problem for example, namely finding the path that a person has to take to visit cities with a minimal cost for the trip, is still open as far as finding an algorithm with polynomial complexity: every currently known algorithm has exponential complexity.
The proof of the correctness of an algorithm consists in demonstrating that it correctly executes the desired process, that is, that it reaches the desired solution. There are formal methods for proving correctness using Mathematical Logic. In this area there are two classes of problems: proof of correct execution; and proof that execution terminates for any input. This last question is called the halting problem.
Another technique consists of mathematically specifying a problem, then transforming this specification using formal rules (which should have previously been demonstrated to be correct), until one reaches an algorithm which may be formulated in a programming language.
This area is called Program Development by (Formal) Transformations. Instead of proving that the program is correct, it is deduced in a correct way (one of the big problems with proving a program correct is that when it is not correct, in most of the cases nothing can be concluded).
Through the described activities, an introduction is made to a wide area of fundamental concepts of the Theory of Computation. As it has been shown, this introduction begins with a physical manipulation by the participants, thus avoiding an excessively abstract teaching method that has no connection to the students’ reality.
A computer screen cannot replace students’ physical activity, because the latter may deal with real, and not abstract, objects. Furthermore, our proposal involves a social aspect through the formation of groups, who may not only discuss in the realm of ideas, but also may "do with their hands". A purely abstract level is reached later, but is related to the physical experience. In this sense we have here an example of "bottom-up" learning, which seems to us much more adequate. The concrete example precedes abstraction; when the latter is reached, students will not consider it as something absolutely strange, outside of their experience.
Our experience has shown that physical activities stimulate creativity. In fact, participants have been stating that they would never have found the sort of algorithms they did if they had not manipulated the card strips. During the practical activities students encounter some previously studied mathematical concepts: summation of number progressions, logarithms and their properties, combinatorics.
In two of the assessments written by participants just after the class, the following phrases were found:
"This activity is valid mainly for those who have no idea why they are learning Mathematics at school. Through the given concrete examples, it is possible to understand why there is so much theory."
"I could better understand the fact that we are really going to use the Mathematics learned at school."
The pedagogical material and the game rules were designed so that the solutions found by participants could be expressed through algorithms and be close to a computer program. We believe it is essential that the idea students have of computers and computing be changed. The idea they currently have is a false one due to the use of electronic games, sophisticated text and graphic editors, etc., and the emotions associated with them. Students on our introductory Computer Science course invariably become frustrated with its conceptual form: they had other expectations. Thus the fact that the activities described here do not use a computer go in the direction of changing that false idea. One of the participants wrote: "The class showed me that taking a course in Computer Science does not mean using the computer the whole day."
No generally accepted formal definition of "algorithm" exists yet. We can, however, derive clues to the issues involved and an informal meaning of the word from the following quotation from Boolos and Jeffrey.
"No human being can write fast enough, or long enough, or small enough to list all members of an enumerably infinite set by writing out their names, one after another, in some notation. But humans can do something equally useful, in the case of certain enumerably infinite sets: They can give explicit instructions for determining the nth member of the set, for arbitrary finite n. Such instructions are to be given quite explicitly, in a form in which they could be followed by a computing machine, or by a human who is capable of carrying out only very elementary operations on symbols".
