Государственному экзамену по информатике

для студентов специальности «Прикладная математика».

Казанский государственный университет

Факультет вычислительной математики и кибернетики
От составителя - студенту.

Предлагаемое пособие - не конспект готовых ответов (или же, попросту - набор шпаргалок) к государственному экзамену, но призванный придать импульс к своей собственной работе связанный и замкнутый текст. Это означает, что посвященный каждому вопросу программы параграф использует понятия, введенные в предыдущих ответах, а решение задач - ссылки на решение задач из предыдущих ответов. Теоретически можно и практически нужно (в идеале, фактически же – лишь по требованию экзаменатора) уметь "разворачивать" ответ до базовых общематематических понятий из первого параграфа. Потому, не удивляйтесь - при приблизительно равном фактическом объеме (после такого развертывания), более поздние разделы выглядят компактнее более ранних.

Что оценивается на государственном экзамене? Не ваша программистская интуиция, и не знание конкретных языков или систем программирования - но ваша квалификация как программистов, закачивающих университетский курс обучения по математической специальности. По факту, это означает умение уверенно создавать пусть не идеально эффективные, но всегда понятные, «грамотные» и лишь потому правильные и надежные программы. Последнее обязательно предполагает свободное владение технологией решения достаточно сложных задач - невозможного без фундаментальной общематематической подготовки, умения формулировать вне синтаксиса конкретного языка программирования точную семантику используемых понятий в терминах классических понятий.

При том вполне очевидно, что задача экзаменатора - не в том, чтобы "завалить" вас на отдельных формулировках, но в том, чтобы оценить вашу программистскую и общематематическую культуру в целом. Потому - не старайтесь заучивать приведенные формулировки наизусть - поздно и бесполезно! Лучше задумайтесь - как бы вы сами точно и полезно сформулировали содержание используемых в вашей программистской практике понятий. Надеюсь - ваши формулировки будут близки к моим. Успеха!

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

© Н. Р. Бухараев, КТК ВМК КГУ, 2002 -2008

Основные понятия процедурного программирования.

Ключевые понятия:состояние, оператор, спецификация, трасса. Структурное программирование – композиция, условные и итерационные (циклические) определения операторов. Рекуррентные определения.

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

При моделировании реальных объектов мы выделяем описание статики (одновременности) – допустимого положения, характеристики, состояния объекта на некоторый фиксированный момент времени - и динамики - изменения объекта во времени, допустимых преобразований его состояний. Формально-математическим средством такого описания служит понятие области (модели, домена, системы, пространства) или, в программистской терминологии, (абстрактного) типа данных - пары <A,F>. Здесь A - некоторое основное множество значений, отражающее совокупность допустимых состояний объекта, а F, FÍAàA, - класс функций, описывающих совокупность его допустимых преобразований во времени. (Здесь и далее XàY - класс функций f с областью определения Dom(f)=X и областью значений Val(f)=Y, не обязательно - всюду определенных). Сам термин «тип» указывает на то, что на деле такое описание не задает конкретный, содержательно богатый объект однозначно, но описывает некоторое зависящее от цели моделирования обеднение, математическую абстракцию объекта.

Помимо формулирования цели программирования как создания компьтерных моделей, понятие типа используется и для описания языка программирования как основного средства такого моделирования. Здесь для программиста явное выделение класса функций F особенно важно, поскольку оно задает класс доступных для использования преобразований. В отличие от обычной математической практики, класс таких исходных, предопределенных функций, равно как и способы определения новых функций в программировании крайне ограничены.

Понятие типа помогает нам точнее сформулировать и задачу самого программирования как перевод, описание допустимого в терминах доступного.

В наиболее простом случае элементы множества А считаются "атомами", не имеющими, в контексте данного языка описания, внутренней структуры - возможных/допустимыхзначений некоторой единственной характеристики объекта, отождествляемой с ним самим. Такие типы называют простыми или скалярными.

Классические примеры типов, традиционно воспринимаемых нами как скалярные - арифметика целых Z, рациональных Q и вещественных D чисел, т.е. соответствующие числовые множества, рассматриваемые совместно с 4 арифметическими операциями и отношениями сравнения. Универсальность математических понятий позволяет использовать одни и те же пространства для описания содержательно различных характеристик объекта - так, вещественные числа могут пониматься как значения скорости, ускорения, веса, температуры и прочих характеристик объекта.

В отличие от классического разделения «скаляры-векторы», в программировании понятие простого и сложного относительны. Тип, считающийся скалярным в одном языке программирования, может трактоваться как структурный – в другом.

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

Т.е. некоторого множества n-ок p=<p₁,..,p_n>, p_iÎ A_i, p_i - значение i-ой характеристики (как правило, числовое). В этом случае основное множество типа – n-местное отношение, подмножество декартового произведения A₁´…´A_n (множества всех n-ок p=<p₁,..,p_n>, p_iÎ A_i, i Î [1..n]). Так, множество точек плоскости можно описать как декартово произведение D²=D´D={<x,y>, xÎ D, yÎ D}, где x,y - декартовы координаты точки, любую фигуру на плоскости - как некоторое подмножество D². Другой способ описания того же пространства - задание точек парой значений их полярных координат.

В программировании вместо позиционного принципа, требующего предварительной, часто неявной, нумерации характеристик, обычно используется принцип именования - сопоставления значений не номерам, но именам характеристик. В этом случае в качестве основного множества типа выступает подмножество именованного декартового произведения множеств A₁,…,A_n- класса всех функций значения, т.е. определенных на некотором множестве имен Name всех функций f таких, что f(k)ÎA_i(k), k Î Name.

Пример. Множество точек плоскости можно описать как именованное декартово произведение - множество всех функций f на множестве имен {'X-координата', 'Y-координата'}, где f('X-координата') Î D, f('Y-координата') Î D. При задании точек полярными координатами мы, по всей видимости, выберем уже другое множество имен - например, {'радиус', 'угол'}, что помогает явно различить разные представления понятий.

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

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

Итак, в общем случае типа данных <A,F> в качестве множества состояний A выступает некоторое множество функций, а F - некоторый класс функций над А, FÍAàA. Функции "высших порядков", аргументами и значениями которых являются функции, называют операторами, а их определение на некотором формально-математическом языке называют - спецификацией. Классический способ спецификации – задание областей определения («дано») и значений («требуется найти/вычислить») оператора парой предикатов, называемых ее пред- и пост-условием.

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

Как следует из названия, процедурное программирование изначально ориентировалось на функциональное описание динамики - сложных преобразований, имеющих «вход» и «выход», начало и конец, аргументы и результаты – в операторных терминах.

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

Язык процедурного программирования - язык формального описания реальных процессов и объектов в терминах задаваемых этим языком способов определения типов данных и процедур их преобразования.

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

Это существенно отличает их от языков аксиоматической математики и рекурсивного (функционального и логического) программирования, оперирующих косвенными определениями понятий указанием их свойств, в частности – в терминах рекурсивных определений.

Базовый рекуррентный принцип ("новое" определяем через "старое") отражается в основном для таких языков общем способе обозначения операторов – операторе кратного или векторного присваивания вида s:=e(s'). Здесь s, s' - списки имен переменных, а e - выражение, задающее функциональную зависимость новых значений переменных (с именами из s) от старых значений переменных (с именами из s'). Существенно, что имена в s, s' могут совпадать.

Важные частные случаи присваивания, используемые (в отличие от кратного присваивания) в реальных языках программирования:

a) s:=s', где s, s' - произвольные списки имен переменных (такое присваивание соответствует табличному определению некоторой функции, в частном случае - перестановке значений)

b) простое присваивание вида v:=e(s), v - (единственное) имя переменной

c) бинарное присваивание вида v:=[vf]v', v,v' - имена переменных, f - имя (знак) функции двух аргументов.

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

Как отмечено выше, с абстрактной, обематематической точки зрения и значения (из А), и их преобразования (из F) - это одни и те же объекты (функции), с одними и теми же способами их определения. С другой, для программиста определение типов как пары <данные, преобразования> также отражает фундаментальное разделение хранимой и выводимой информации.

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

Классическим примером конструктивного построения языка являются языкиструктурного программирования,выделяющие в качестве основных три общематематических способа (структуры, схемы) определения новых процедур:

a) композиция – (S1;S2, в синтаксисе языка Паскаль), соответствующая описанию последовательного вычисления процедур S1 и S2 как функций на состояниях: (S1;S2)(s)=S2(S1(s))

В школьных терминах – определение «сложной функции» подстановкой (суперпозицией).

b) структуру условного оператора (в Паскале - if B then S1 else S2), соответствующую определению функции разбором случаев

ì S1(s), B(s)=true

(if B then S1 else S2)(s)= í

î S2(s), B(s)=false

В классических терминах – условное определение функции.

c) структуру оператора цикла с предусловием (в Паскале - while B do S), соответствующую итогу вычисления первого члена рекуррентно определяемой последовательности s, не обладающим заданным свойством B. Точнее:

a) если s₀=s, s_i+1=S(s_i) и k=min {i: B(s_i)=false}, то (while B do S)(s)=s_k

b) если {i: B(s_i)=false}=Æ, то значение (while B do S)(s) неопределено,

В классических терминах – итерационное определение функции.

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

Пример структурирования программ

Задача линейного поиска значения в последовательном файле. Неформальная постановка – выяснить (found), есть ли заданное значение x в заданной последовательности a. Спецификация: предусловие AÎNàT and XÎT, постусловие found:=$ iÎ Dom(A)(X=A_i):

Здесь и далее мы обозначаем значения большими буквами, чтобы явно отличить их от имен значений.

read(x); found:=false; while not eof() do begin read(a); if a=x then begin found:=true; goto 1 end; 1: »

read(x); found:=false; while not eof() and not found do begin read(a); if a=x then begin found:=true; end;

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

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

Пример трассировки для доказательства корректности программ. Задача обмена значений (вещественных) переменных, спецификация x,y:=y,x.

Программа Трасса Программа Трасса Программа Трасса

x y x y z x y

X Y X Y Æ X Y

x:=y; Y Y z:=x; X Y X x:=x+y; X+Y Y

y:=x Y Y x:=y; Y Y X y:=x-y; X+Y X

y:=z Y X X x:=x-y Y X неверно верно верно

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

Спецификация Итерационное определение Программа

m:=max (a₁,…,a_n) m₁= a₁ ì a_i, m_i<a_i read(m);

m_i+1= max(m_i,a_i)=í while not eof() do

î m_i, m_{i ³} a_i if m<a then m:=a

s:=S {a_i: iÎ [1..k]} s₀=0 s:=0; read(eps);

k=min {i: abs(a_i)<eps } read(a); go:= true;

s_i+1= s_i+a_i while not eof() and go do

begin read(a);

if abs(a)>=eps

then s:=s+a else go:=false

end

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

b:=a₀xⁿ+…+a_nx⁰ b₀= a₀ read(b);

b_i+1=b_ix+a_i while not eof() do

(схема Горнера) begin read(a); b:=b*x+a end

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