Примеры экономии времени —вычисление рекуррентным способом.
Вопрос 3
Переменные в программировании как хранилища (память). Память внутренняя (оперативная) и внешняя (файлы). Потоки данных. Операторы присваивания (кратное, простое, бинарное) и ввода/вывода. Программы как файловые процедуры.
А) Переменная-это поименованная область памяти (т.е ячейки), адрес которой можно использовать для осуществления доступа к данным.
(По Бухараеву) Переменную связывают с понятием ячейки памяти, которая подразделяется на внутреннюю (оперативную) и внешнюю (файлы).
В) Оперативная память характеризуется высокой скоростью записи и чтения, фиксированным объемом и предназначена для временного хранения информации во время работы программы.
Файлы обеспечивают хранение больших объемов данных, предназначенных (как правило) для долговременного хранения, но обеспечивают относительно низкую скорость обмена с оперативной памятью.
С) Поток данных- это абстракция, используемая для чтения или записи данных
(По Бухараеву) Поток данных – это последовательность < a1,…, ai,…,an> неопределённой длины, где ai элементы некоторого базового типа, а «i» маркер потока. Над входными потоками выполняются функция распознавания конца потока << Eof(f) >>, а также функция открытия файла <<Reset(f)>>
Оператор чтения из потока read(f,x) определяется следующим образом:
{f→<a1, …, an>, iàI, eof(f)→false}
read(f,x)
{f→<a1, …, an>, x→ai, 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
