Примеры экономии памяти — обработка массивов « на лету».

Примеры экономии времени —вычисление рекуррентным способом.

Вопрос 3

Переменные в программировании как хранилища (память). Память внутренняя (оперативная) и внешняя (файлы). Потоки данных. Операторы присваивания (кратное, простое, бинарное) и ввода/вывода. Программы как файловые процедуры.

А) Переменная-это поименованная область памяти (т.е ячейки), адрес которой можно использовать для осуществления доступа к данным.

(По Бухараеву) Переменную связывают с понятием ячейки памяти, которая подразделяется на внутреннюю (оперативную) и внешнюю ( файлы).

В) Оперативная память характеризуется высокой скоростью записи и чтения, фиксированным объемом и предназначена для временного хранения информации во время работы программы.

Файлы обеспечивают хранение больших объемов данных, предназначенных (как правило) для долговременного хранения, но обеспечивают относительно низкую скорость обмена с оперативной памятью.

С) Поток данных- это абстракция, используемая для чтения или записи данных

(По Бухараеву) Поток данных – это последовательность < a_1,…, a_i,…,a_n> неопределённой длины, где a_i элементы некоторого базового типа, а «i» маркер потока. Над входными потоками выполняются функция распознавания конца потока << Eof(f) >> , а также функция открытия файла <<Reset(f)>>

Оператор чтения из потока read(f,x) определяется следующим образом:

{f→<a₁, …, a_n>, iàI, eof(f)→false}

read(f,x)

{f→<a₁, …, a_n>, x→a_i, iàI+1}

При eof(f)=true выполнение оператор read не определено.

D) Присвоение – это механизм, позволяющий изменять значения переменных.

Бинарное присваивание- это объединение соответствующего бинарного оператора (+,-,*,/) , с оператором «=».

Унарное присваивание – это арифметическая операция одного аргумента для увеличения или уменьшения на единицу, т.е «++»- инкремент, или «--»- декремент.

Операторы ввода/вывода- это интерфейс, отвечающий за взаимодействие программы с внешней средой.

В Паскале встречаются операторы Write( Writeln) и Read (Readln).

Оператор Writeln Выводит на экран сообщение или записывает данные в какой нибудь файл, а оператор Write имеет тот же самый принцип, но после записи не переводит курсор на новую строку, как Writeln.

Оператор Readln- позволяет пользователю вводит данные в компьютер и переводит курсор в новую строку, как не делает это оператор Read.

Е) В программирование иногда несколько раз используются одни и те же данные и счисления. Для того, чтобы облегчить работы программы, нужно использовать процедуры и файлы. В настоящее время многие программы обладают этим свойством, поэтому в настоящее время программу называют файловыми процедурами.

Вопрос 4

Каждый язык программирования – язык определения процедур. В наиболее традиционном случае такой язык определяется:

1. классом базовых операторов (в частности допустимых присваиваний);

2. классом операторных конструкций, порождающих из базовых операторов все более сложные, путем кратного применения.

Такие языки прямых определений, называются процедурными языками программирования.

Предикат в программировании — функция, принимающая один или более аргументов и возвращающая значения булева типа. Иначе говоря, предикат – функция на состояние, имеющая всего лишь два значения, которые в программе обычно обозначаются true и false. В языках блок-схем предикаты записываются в виде ромбиков.

Блок-схема — распространенный тип схем (графических моделей), описывающих алгоритмы или процессы, в которых отдельные шаги изображаются в виде блоков различной формы, соединенных между собой линиями, указывающими направление последовательности.

Транслятор – это программа, предназначенная для автоматического перевода…

Если язык программирования ориентирован на конкретный тип процессора и учитывает его возможности, то он называется языком программирования низкого уровня.

Низкий уровень языка программирования не означает плохой уровень.
Имеется ввиду, что операторы языка близки к машинному коду и ориентированы на конкретные команды процессора. (ассемблер имеет самый низкий уровень)

Инструмент, который переводит программу, написанную на языке высокого уровня в машинный код, называют компилятором.

Языки программирования высокого уровня значительно ближе и понятнее человеку. Особенности конкретных компьютерных архитектур в них не учитываются, поэтому создаваемые программы на уровне исходных текстов легко переносятся на другие платформы, для которых создан транслятор этого языка. Разрабатывать программы на языках высокого уровня значительно проще, а ошибок при этом допускается гораздо меньше.

Функциональная эквивалентность – разная реализация одной спецификации с точностью до входа\выхода.

Ветка – конкретный путь в блок-схеме соответствующий конкретному входимому значению

Трасс – последовательность промежуточных состояний вычисления (пошаговая проверка)

Понятие трассы используется для проверки работы алгоритмов путем выписывания трассы для данного входного состояния (трассировка алгоритма).

x,y:=y,x

x:=X y:=Y

x:=x•y y:=x/y x:=x/y

z:=x x:=y y:=z

x:=x+y y:=x-y x:=x-y

Не обязательно выписывать трассу после каждого выполняемого оператора, а лишь в некоторых контрольных точках.

Вопрос 5

Самые простые для понимания алгоритмы – это линейные алгоритмы, представляющие собой последовательность или композицию операторных блоков, это вычисления с единственной трассой.

В общем случае произвольных блок-схем, множество всех трасс очень богато, его крайне трудно описать, такие блок-схемы с многообразными и запутанными трассами называют спагетти (блок-схем).

Идея упростить язык блок-схем с помощью выделения небольшого числа операторных конструкций соответствующих удобным и знакомым схемам определения функций.

Структурный подход к программированию выделяет три операторных конструкции (структуры):

1. Композиция

Если S1и S2– допустимые блок-схемы, то S1→ S2также допустима.

2. Структура полного условного оператора. Соответствует определению функций разбором случаев.

Частный случай – структура укороченного условного оператора:

3. Структура цикла с предусловием

Множество трасс такой структуры описывается просто:

где i0– наименьший номер такой, что условие B называют условием продолжения цикла, а оператор S – телом цикла.

Эквивалентность структурных и всех б/с на примере "побочный выход из цикла".

Побочный выход из цикла.

Вопрос 6