Информатика и информационные технологии: конспект лекций
Шрифт:
Базовыми функциями и их сопутствующими алгоритмами могут выступать:
1) функция n независимых переменных, тождественно равная нулю. Тогда, если знаком функции является n, то независимо от количества аргументов значение функции следует положить равным нулю;
2) тождественная функция n независимых переменных вида ni. Тогда, если знаком функции является ni, то значением функции следует взять значение i-го аргумента, считая слева направо;
3) – функция одного независимого аргумента. Тогда, если знаком функции является , то значением функции следует взять значение, следующее
представлению алгоритма. Например, американский ученый Черч предположил, что класс вычислимых функций исчерпывается рекурсивными функциями и, как следствие, каким бы ни был алгоритм, перерабатывающий один набор целых неотрицательных чисел в другой, найдется алгоритм, сопутствующий рекурсивной функции, эквивалентный данному. Следовательно, если для решения некоторой поставленной задачи нельзя построить рекурсивную функцию, то и не существует алгоритма для ее решения. Другой ученый, Тьюринг, разработал виртуальную ЭВМ, которая перерабатывала входную последовательность символов в выходную. В связи с этим им был выдвинут тезис, что любая вычислимая функция вычислима по Тьюрингу.
ЛЕКЦИЯ № 2. Язык Pascal
1. Введение в язык Pascal
Основные символы языка – буквы, цифры и специальные символы – составляют его алфавит. Язык Pascal включает следующий набор основных символов:
1) 26 латинских строчных и 26 латинских прописных букв:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz;
2) _ (знак подчеркивания);
3) 10 цифр: 0123456789;
4) знаки операций:
+ – х / = <> < > <= >= := @;
5) ограничители:
. , ' [ ] (. .) { } (* *) .. : ;
6) спецификаторы: ^ # $;
7) служебные (зарезервированные) слова:
ABSOLUTE, ASSEMBLER, AND, ARRAY, ASM, BEGIN, CASE, CONST, CONSTRUCTOR, DESTRUCTOR, DIV, DO, DOWNTO, ELSE, END, EXPORT, EXTERNAL, FAR, FILE, FOR, FORWARD, FUNCTION, GOTO, IF, IMPLEMENTATION, IN, INDEX, INHERITED, INLINE, INTERFACE, INTERRUPT, LABEL, LIBRARY, MOD, NAME, NIL, NEAR, NOT, OBJECT, OF, OR, PACKED, PRIVATE, PROCEDURE, PROGRAM, PUBLIC, RECORD, REPEAT, RESIDENT, SET, SHL, SHR, STRING, THEN, TO, TYPE, UNIT, UNTIL, USES, VAR, VIRTUAL, WHILE, WITH, XOR.
Кроме перечисленных, в набор основных символов входит пробел. Пробелы нельзя использовать внутри сдвоенных символов и зарезервированных слов.
В математике принято классифицировать переменные в соответствии с некоторыми важными характеристиками. Производится строгое разграничение между вещественными, комплексными и логическими переменными, между переменными, представляющими отдельные значения и множество значений, и т. д. При обработке данных на ЭВМ такая классификация еще более важна. В любом алгоритмическом языке каждая константа, переменная, выражение или функция бывают определенного типа.
В языке Pascal существует правило: тип явно задается в описании переменной или функции, которое предшествует их использованию.
1) любой тип данных определяет множество значений, к которому принадлежит константа, которые может принимать переменная или выражение либо вырабатывать операция или функция;
2) тип значения, задаваемого константой, переменной или выражением, можно определить по их виду или описанию;
3) каждая операция или функция требуют аргументов фиксированного типа и выдают результат фиксированного типа.
Отсюда следует, что транслятор может использовать информацию о типах для проверки вычислимости и правильности различных конструкций.
Тип определяет:
1) возможные значения переменных, констант, функций, выражений, принадлежащих к данному типу;
2) внутреннюю форму представления данных в ЭВМ;
3) операции и функции, которые могут выполняться над величинами, принадлежащими к данному типу.
Следует заметить, что обязательное описание типа приводит к избыточности в тексте программ, но такая избыточность является важным вспомогательным средством разработки программ и рассматривается как необходимое свойство современных алгоритмических языков высокого уровня.
В языке Pascal существуют скалярные и структурированные типы данных. К скалярным типам относятся стандартные типы и типы, определяемые пользователем. Стандартные типы включают целые, действительные, символьный, логические и адресный типы.
Целые типы определяют константы, переменные и функции, значения которых реализуются множеством целых чисел, допустимых в данной ЭВМ.
Действительные типы определяет те данные, которые реализуются подмножеством действительных чисел, допустимых в данной ЭВМ.
Типы, определяемые пользователем, – перечисляемый и интервальный. Структурированные типы имеют четыре разновидности: массивы, множества, записи и файлы.
Кроме перечисленных, Pascal включает еще два типа – процедурный и объектный.
Выражение языка состоит из констант, переменных, указателей функций, знаков операций и скобок. Выражение задает правило вычисления некоторого значения. Порядок вычисления определяется старшинством (приоритетом) содержащихся в нем операций. В языке Pascal принят следующий приоритет операций:
1) вычисления в круглых скобках;
2) вычисления значений функций;
3) унарные операции;
4) операции *, /, div, mod, and;
5) операции +, —, or, xor;
6) операции отношения =, <>, <, >, <=, >=.
Выражения входят в состав многих операторов языка Pascal, – также могут быть аргументами встроенных функций.
2. Стандартные процедуры и функции