Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

These operations define a language we call the GOTO language. A program in this language is a sequence of numbered instructions (written one per line). To run a program written in this language, we should provide the input. We will assume that the input is a string of symbols from a finite input alphabet (which is a subset of the tape alphabet), which is stored on the tape before the computation begins.

Although we do not want to place any bounds on it, allowing an infinite tape is not realistic. This problem is circumvented by allowing expandable memory. In the beginning, the tape containing the input defines its boundary. When the machine moves beyond the current boundary, a new memory cell will be attached with a special symbol B (blank) written on it. Finally, we define the result of computation as the contents of the tape when the computer reaches the STOP instruction.

Ex.1. Answer the following questions:

1. Why has the word “algorithm” become essential?

2. What are the distinguishing features of an algorithm?

3. What is the relationship between an algorithm and a computer program?

4. What were the first programs written for?

5. What is the origin of the word “algorithm”?

6. Why was the role of Al-Khowaresmi’s book so important?

7. How are algorithms used in mathematics?

8. How are algorithms used in Computer Science?

9. When did the concept of algorithm appear?

10. What role did Turing machine play in the history of science?

11. What was Turing’s notion of mechanical computation?

12. What is the GOTO language?

13. How does a program run in the GOTO language?

14. What does Church-Turing thesis state?

15. How are algorithms used in Computer Science?

Ex.2. Give the main ideas of the text in logical order.

Ex.3. Translate in writing:

Что такое алгоритм?

Слово «алгоритм» происходит от имени персидского математика Хорезми (по-арабски Аль-Хорезми) который в IX в.н.э. разработал правила четырех арифметических действий над числами в десятичной системе исчисления. Совокупность этих правил в Европе стали называть «алгоризм». Позже это слово трансформировалось в «алгоритм» и стало обозначать отдельные правила определенного вида (и не только правила арифметических действий).

В течение долгого времени его использовали не только математики для обозначения правил решения различных задач. В настоящее время словом «алгоритм» пользуются не только математики. Его стали использовать в самых различных сферах, и теперь алгоритм понимается как точно сформулированное правило, с помощью которого получают необходимый результат.

Эффективный алгоритм – это алгоритм, допускающий эффективную вычислительную реализацию. Изучение возможности существования эффективных алгоритмов вычисления конкретных величин составляет основу теории алгоритмов. За исключением простейших случаев, доказать конкретность алгоритма или даже описать результат действия алгоритма довольно трудно. На практике приходится ограничиваться проверкой правильности алгоритма. Такая проверка позволяет удостовериться, что алгоритм обеспечивает выполнение требуемых вычислений. Она включает тестирование программы в различных условиях постановки задачи для приобретения уверенности в том, что алгоритм нормально работает во всех контрольных примерах.

Ex.4. Topics for discussion.

1. The history of an algorithm.

2. The use of algorithms in computer science.

3. Turing machine.

UNIT 4

Data Structures

Key vocabulary:

1. Complicated adj.– сложный

2. Item n.– единица

3. Pointer n.–указатель,

описатель

1. String n.– строка

2. Either … or … ­– либо … либо…;

или … или …

1. Marker n.– маркер, метка

2. Array n.– массив

3. Dimension n.– размерность

4. Two-dimensional adj.– двумерный

5. Blank n.– пробел, пропуск,

пустое место

1. Stack n.– стек, пакет

2. Queue n.– очередь

3. Frequent adj.– частый

4. Intermediate adj.– промежуточный

5. Implement v.– выполнять,

осуществлять,

обеспечивать выполнение

1. Implementation n.–реализация,

внедрение

1. Artificial intelligence (AI) – искусственный интеллект

2. Research n.– исследование,

изучение, изыскание

1. Tree n.– дерево,

древовидная структура

1. Hierarchy n.– иерархия

2. Node n.– вершина, узловая

точка

1. Root n. – корень

2. Module n. – модуль, блок

3. Recursive adj. – рекурсивный

4. Integer n. – целое число

Most of the information we encounter in everyday life is structured in some way. The commonest example is the words of our language, which are linked together in phrases, sentences and other more complex structures. The rules for constructing these structures are extremely complicated, yet we apply them by intuition.

Other examples of structured information include dictionaries, telephone directories and encyclopedias. These are large stores of information which would be useless if the information were not strictly arranged according to a few simple rules. The structure of a collection of information makes it easy to locate individual items of information, and to insert new items, or delete items. The same reasoning applies to structured information stored in computers.

Pointers

A pointer is a data item which indicates the location of another data item. It may be thought of as an arrow.

Pointers are used to build data structures. They provide the links which join elements of the structure. Of particular significance are pointers to the front and back of a data structure. Occasionally it is required that a pointer does not point to anything; in this situation, the pointer is said to have a null value.

Strings

A string is a sequence of characters regarded as a single data item. Strings may be of fixed or variable length. The length of a string is indicated either by the number of characters in the string placed at the front of the string, or by a special character called an end-of-string marker at the end. The following example shows these two methods of representing the same string:

10 CAPITAL 194 CAPITAL 194#

Operations on strings are of two types: operations which join two or more strings to produce a single string, and operations which divide a string to produce two or more sub-strings.

Arrays

An array is a set of data items of identical types, stored together. The number of elements in the array is fixed when the array is created. Each element is accessed by an index, which indicates the position of the element in the array.

For example, if the array BEATLES has elements as follows:

BEATLES JOHN

PAUL

GEORGE

RINGO

Then the element with index value 3, BEATLES (3) is the name GEORGE.

Arrays can have more than one dimension. A two-dimensional array may be thought of as having rows and columns like in matrix. Two indices are required to locate an item in the array, corresponding to row and column indices in a matrix. For example, the state of a game of noughts and crosses may be represented by a two-dimensional array, GAME, with three rows and three columns:

GAME OXO

XXO
OOX

If the top left element is GAME(1,1), then the 0 in the third column of the second row is GAME(2,3) and the blank element is GAME(3,1).

Static and Dynamic Data Structures

An array is a static data structure, that is to say, it stays the same size once it has been created. Data structures which change in size once they have been created are called dynamic data structures. A string can be a static or a dynamic data structure. They generally require pointers for their implementation.

Stacks

A stack is a collection of data items which may only be accessed at one end, called the top of the stack.

Only two operations may be carried out on a stack. Adding a new item, called pushing or stacking the item, involves placing it on top of the stack. Removing an item involves popping it from the stack.

If a number of items are pushed onto a stack, and then popped from the stack, the last item added will be the first one removed. For this reason a stack is called a last-in-first-out (LIFO) stack. Other names for a stack are push-down stack and push-down list.

When a stack is stored in a computer memory, the elements do not move up and down as the stack is pushed and popped. Instead, the position of the top of the stack changes. A pointer called a stack pointer indicates the position of the top of the stack.

Another pointer is used to indicate the base of the stack. This pointer, called the stack base, keeps the same value as long as the stack is in existence.

The stack is one of the most important data structures in computing. Stacks are used in calculations, for translating from one computer language to another and for transferring control from one part of a program to another. Most modern processors include a stack pointer as an architectural feature and some regard their entire memory as a set of stacks.

In spite of the American origins of many ideas associated with computers, that great British institution, the queue, has found its way into the theory of computing. Everyone knows how a queue works: newcomers join at the rear, service is provided at the front, and no pushing-in is allowed. Exactly the same rules apply to queues of data stored in a computer memory: data items are added at the back and removed from the front. A queue is a first-in-first-out (FIFO) data structure.

Although queues are used slightly less frequently than stacks, they do have a variety of applications. These include queuing data items in transit between a processor and a peripheral device or intermediate points in a data communications network.

Lists

A list is a set of data stored in some order. Data items may be inserted or deleted at any point in the list. In this respect, a list is less restrictive than a stack or queue. The simplest way of implementing a list makes use of a pointer from each item to the one following it in the list. There is also a pointer to the start of the list, while the last item in the list has a null pointer.

A data structure of this type is also known as a linked list. A list element consists of a data item and its pointer. In many applications a list element contains a number of data items. Since elements can easily be added to the rear or removed from the front of the linked list, this structure may also be used to implement a queue. Inserting an element into a list is achieved by adjusting the pointers to include the new element.

Data items in a list are in order, in the sense that one data item is behind another in the list. Lists are, however, frequently used in cases where the data items are in numerical or alphabetical order. Such lists are called ordered lists. Lists are very useful for storing ordered sets of data, if insertions and deletions of data items are frequent.

Data items may themselves be entire lists. Lists of this nature are widely used in artificial intelligence research, and form the basis of the programming language Lisp.

A tree is a structure implying a hierarchy, with each element of the tree being linked to elements below it.

Each data item in a tree is at a node of the tree. The node at the top of the tree is called the root. Each node may be connected to one or more subtrees, which also have a tree structure. A node at the bottom of the tree, which has no subtrees, is called a terminal node, or a leaf.

A number of operations may be carried out on trees. Two binary trees may be joined to an additional node, which becomes the root of a larger binary tree, with the original trees as subtrees. A tree may be traversed in several ways. Traversing a tree is accessing its elements in a systematic way.

Trees have a number of applications in computing. The modules of many programs are linked together in a tree structure. Trees are also used to represent arithmetic expressions, and for sorting and searching. Some computers regard their entire memory as if it were partitioned into a tree structure.

The essential feature of a tree is that each node is connected to subtrees, which themselves have the structure of trees. In other words, wherever you are in a tree, the structure ‘below’ you is a tree. In this sense a tree is a recursive data structure, and can be manipulated by recursive programs. This is the property of trees which makes them so useful from a computing point of view.

A number of programming languages require that the type of each data item be declared before the data item is used in a program. A data item may be an integer, an array, or a list, to name just a few examples.

Характеристики

Список файлов книги