Методическое пособие для подготовки к государственному экзамену по информатике для студентов специальности «Прикладная математика»



жүктеу 0.67 Mb.
бет1/5
Дата01.05.2016
өлшемі0.67 Mb.
  1   2   3   4   5




Бухараев Н.Р.

Введение в процедурное программирование


Методическое пособие для подготовки к

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

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

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


Факультет вычислительной математики и кибернетики

От составителя - студенту.
Предлагаемое пособие - не конспект готовых ответов (или же, попросту - набор шпаргалок) к государственному экзамену, но призванный придать импульс к своей собственной работе связанный и замкнутый текст. Это означает, что посвященный каждому вопросу программы параграф использует понятия, введенные в предыдущих ответах, а решение задач - ссылки на решение задач из предыдущих ответов. Теоретически можно и практически нужно (в идеале, фактически же – лишь по требованию экзаменатора) уметь "разворачивать" ответ до базовых общематематических понятий из первого параграфа. Потому, не удивляйтесь - при приблизительно равном фактическом объеме (после такого развертывания), более поздние разделы выглядят компактнее более ранних.
Что оценивается на государственном экзамене? Не ваша программистская интуиция, и не знание конкретных языков или систем программирования - но ваша квалификация как программистов, закачивающих университетский курс обучения по математической специальности. По факту, это означает умение уверенно создавать пусть не идеально эффективные, но всегда понятные, «грамотные» и лишь потому правильные и надежные программы. Последнее обязательно предполагает свободное владение технологией решения достаточно сложных задач - невозможного без фундаментальной общематематической подготовки, умения формулировать вне синтаксиса конкретного языка программирования точную семантику используемых понятий в терминах классических понятий.
При том вполне очевидно, что задача экзаменатора - не в том, чтобы "завалить" вас на отдельных формулировках, но в том, чтобы оценить вашу программистскую и общематематическую культуру в целом. Потому - не старайтесь заучивать приведенные формулировки наизусть - поздно и бесполезно! Лучше задумайтесь - как бы вы сами точно и полезно сформулировали содержание используемых в вашей программистской практике понятий. Надеюсь - ваши формулировки будут близки к моим. Успеха!
Выделения в тексте имеют следующий смысл. Понятия, выделяемые жирным шрифтом необходимо раскрыть в ответе, курсивом - желательно обратить внимание, мелким шрифтом - можно опустить, без ущерба для итогового результата.

© Н. Р. Бухараев, КТК ВМК КГУ, 2002 -2005
§1. Основные понятия процедурного программирования.
Ключевые понятия: состояние, оператор, спецификация, трасса. Структурное программирование – композиция, условные и итерационные (циклические) определения операторов. Рекуррентные определения.
Умения и навыки: Преобразование неструктурных алгоритмов в структурные. Нахождение рекуррентных определений кратных числовых функций. Преобразование рекуррент в итерацию.

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


Помимо формулирования цели программирования как создания компьтерных моделей, понятие типа используется и для описания языка программирования как основного средства такого моделирования. Здесь для программиста явное выделение класса функций F особенно важно, поскольку оно задает класс доступных для использования преобразований. В отличие от обычной математической практики, класс таких исходных, предопределенных функций, равно как и способы определения новых функций в программировании крайне ограничены.
Понятие типа помогает нам точнее сформулировать и задачу самого программирования как перевод, описание допустимого в терминах доступного.
В наиболее простом случае элементы множества А считаются "атомами", не имеющими, в контексте данного языка описания, внутренней структуры - возможных/допустимых значений некоторой единственной характеристики объекта, отождествляемой с ним самим. Такие типы называют простыми или скалярными.
Классические примеры типов, традиционно воспринимаемых нами как скалярные - арифметика целых Z, рациональных Q и вещественных D чисел, т.е. соответствующие числовые множества, рассматриваемые совместно с 4 арифметическими операциями и отношениями сравнения. Универсальность математических понятий позволяет использовать одни и те же пространства для описания содержательно различных характеристик объекта - так, вещественные числа могут пониматься как значения скорости, ускорения, веса, температуры и прочих характеристик объекта.
В отличие от классического разделения «скаляры-векторы», в программировании понятие простого и сложного относительны. Тип, считающийся скалярным в одном языке программирования, может трактоваться как структурный – в другом.
В более сложных случаях для описания статики объекта требуется несколько характеристик - каждая, вообще говоря, со своим собственным множеством значений. В классической математике для описания состояния сложного объекта как совокупности значений его характеристик обычно используется понятие векторного пространства.
Т.е. некоторого множества n-ок p=
1
,..,pn>, pi Ai, pi - значение i-ой характеристики (как правило, числовое). В этом случае основное множество типа – n-местное отношение, подмножество декартового произведения A1…An (множества всех n-ок p=
1
,..,pn>, pi Ai, i  [1..n]). Так, множество точек плоскости можно описать как декартово произведение D2=DD={, x D, y D}, где x,y - декартовы координаты точки, любую фигуру на плоскости - как некоторое подмножество D2. Другой способ описания того же пространства - задание точек парой значений их полярных координат.
В программировании вместо позиционного принципа, требующего предварительной, часто неявной, нумерации характеристик, обычно используется принцип именования - сопоставления значений не номерам, но именам характеристик. В этом случае в качестве основного множества типа выступает подмножество именованного декартового произведения множеств A1,…,An - класса всех функций значения, т.е. определенных на некотором множестве имен Name всех функций f таких, что f(k)Ai(k), k  Name.
Пример. Множество точек плоскости можно описать как именованное декартово произведение - множество всех функций f на множестве имен {'X-координата', 'Y-координата'}, где f('X-координата')  D, f('Y-координата')  D. При задании точек полярными координатами мы, по всей видимости, выберем уже другое множество имен - например, {'радиус', 'угол'}, что помогает явно различить разные представления понятий.
Отметим, что хотя в качестве имен обычно используются слова (последовательности символов), наше определение позволяет понимать под именами любое множество значений - например, снова - целые числа (индексы). В случае использования таких "нетрадиционных" имен обычно предпочитают говорить не об именах, а об указателях или ссылках на значение. На практике различие между именованным и "просто" декартовым произведениями довольно условно. Как правило, мы стараемся описать объект как упорядочиваемый (по меньшей мере, одним способом) набором "координат", т.е. независимых линейных характеристик (см. "Классификация типов").
Возможность описания противоположных по содержательному смыслу понятий - статика и динамика, значения и преобразования - в рамках одного языка функций - одно из наиболее фундаментальных положений программирования.
Итак, в общем случае типа данных в качестве множества состояний A выступает некоторое множество функций, а F - некоторый класс функций над А, FAA. Функции "высших порядков", аргументами и значениями которых являются функции, называют операторами, а их определение на некотором формально-математическом языке называют - спецификацией. Классический способ спецификации – задание областей определения («дано») и значений («требуется найти/вычислить») оператора парой предикатов, называемых ее пред- и пост-условием.
Примеры см. далее. На практике мы часто подразумеваем тривиальные предусловия, не формулируя их явно.
Как следует из названия, процедурное программирование изначально ориентировалось на функциональное описание динамики - сложных преобразований, имеющих «вход» и «выход», начало и конец, аргументы и результаты – в операторных терминах.
В качестве содержательно альтернативных подходов можно упомянуть область баз данных, изначально ориентированную на описание сложно организованной статики и интерактивное программирование, ориентированное на описание сложно организованных во времени процессов. Исходя из различных теоретических источников, на практике все такие подходы тесно взаимосвязаны и все более сближаются с развитием программирования.
Язык процедурного программирования - язык формального описания реальных процессов и объектов в терминах задаваемых этим языком способов определения типов данных и процедур их преобразования.
Языки процедурного программирования - языки прямых определений, задающие способы определения (порождения, конструирования) новых операторов в терминах (уже построенных к этому времени) типов данных. Эти определения операторов мы и будем называть процедурами.
Это существенно отличает их от языков аксиоматической математики и рекурсивного (функционального и логического) программирования, оперирующих косвенными определениями понятий указанием их свойств, в частности – в терминах рекурсивных определений.
Базовый рекуррентный принцип ("новое" определяем через "старое") отражается в основном для таких языков общем способе обозначения операторов – операторе кратного или векторного присваивания вида s:=e(s'). Здесь s, s' - списки имен переменных, а e - выражение, задающее функциональную зависимость новых значений переменных (с именами из s) от старых значений переменных (с именами из s'). Существенно, что имена в s, s' могут совпадать.
Важные частные случаи присваивания, используемые (в отличие от кратного присваивания) в реальных языках программирования:

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

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

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

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


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

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

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


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

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

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

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

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




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

  1. если s0=s, si+1=S(si) и k=min {i: B(si)=false}, то (while B do S)(s)=sk

  2. если {i: B(si)=false}=, то значение (while B do S)(s) неопределено,

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


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

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

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

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


s0



si

si+1






Trace

Step

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


Пример трассировки для доказательства корректности программ. Задача обмена значений (вещественных) переменных, спецификация 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 (a1,…,an) m1= a1  ai, mii read(m);

mi+1= max(mi,ai)= while not eof() do

 mi, mi ai if ms:= {ai: i [1..k]} s0=0 s:=0; read(eps);

k=min {i: abs(ai)

si+1= si+ai while not eof() and go do

begin read(a);

if abs(a)>=eps

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

end

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



b:=a0xn+…+anx0 b0= a0 read(b);

bi+1=bix+ai while not eof() do

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

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


§2. Технология программирования.
Параметры-переменные и значения. Глобальные и локальные объекты. Семантика обращений. Побочные эффекты. Демонстрация технологии на примере.
Возможны 2 естественных порядка (стратегии, принципа) определения процедур. Принцип композиции - от данных средств реализации (т.е. языка программирования ЯП) к желаемой цели (логике, языку спецификаций) - восходящее программирование – первоначально кажется наиболее естественным, поскольку следует порядку порождения процедур в ЯП и их последующего применения к данным (порядку вычисления). Однако, в силу связанного с таким порождением быстрого роста числа рассматриваемых случаев, такой подход, скорее - локальная тактика, применимая для разработки относительно небольших и несложных программ. Стратегия нисходящего программирования - цель (логика) важнее средств (реализации) - основана на принципе декомпозиции, последовательного перехода от определения на некотором исходном языке спецификации к более детальным определениям той же процедуры на все более бедных языках спецификаций. Это - чисто семантический принцип, не зависящий по существу от конкретного языка программирования. (В реальности же, как всегда, успех обеспечивает лишь сочетание стратегии и тактики!)
Термин "технология" предполагает наличие некоторого языка фиксации, описания этапов процесса собственного мышления при разработке сложной программы. Аппарат определения пользовательских типов данных и пользовательских процедур позволяет определять нужные языки спецификации средствами самого языка программирования, реализовывая принцип упреждающего именования - возможности обращения, т.е. формального использования имен ("заголовков") функций (операторов) прежде, чем они фактически определяются как выражения языка программирования.
Определение пользовательской процедуры есть сопоставление пользовательскому имени функции (оператора) выражения ЯП, называемого телом процедуры. На уровне семантики, это разграничение определяют как различие между интерфейсом и реализацией процедуры.
Единственной - но критичной! - сложностью такого предварительного определения (объявления) имени является выделение (именование и определение типа) входных и выходных значений - (возможно, совпадающих) имен аргументов и результатов процедуры как функции а также, возможно, имен глобальных значений - т.е. его параметров как функции (в общематематическом, а не узко-программистском смысле термина). В реальности, существующая традиция предполагает выделение непересекающихся множеств имен - т.н. формальных параметров-значений - "собственно" входов, не являющихся выходами, и параметров-переменных - всех выходов, т.е. изменяемых значений. Имена глобальных объектов при этом никак не выделяются. Последующее фактическое определение тела процедуры, как правило, также требует введения вспомогательных объектов, удовлетворяющих локальным, т.е. временным определениям.
Пример порядка разработки при нисходящей стратегии (восходящая предполагает обратный порядок!).

Задача. Вычисление значения комплексного многочлена a степени Deg(a). Спецификация-постусловие (неявно, предполагает знание типа "арифметика комплексных чисел"): y(a,x):={ai*xi:i[1..Deg(a)]}, xComplex, i[1,Deg(a)](aiComplex).





  1. Решаем задачу в терминах ее постановки (спецификации). Объявляем имена нужных пользовательских типы и процедур.

type

tIndex=? ; {номера коэффициентов}

tComplex=?; {комплексные числа}

tComplexPolynom=? {комплексные многочлены}

procedure SetZero(var c:tComplex); {c:=0} ?

function Degree(p:tPolynom):tIndex; {определить степень полинома}?

function Element(p:tPolynom,i:tIndex):tComplex;{определить значение коэффициента}?

procedure Mult(a,b:tComplex;var c:tComplex); {c:=a  b} ?


procedure PolynomValue(Polynom: tComplexPolynom; var y: tComplex);

var


Coefficient:tComplex; { коэффициент полинома }

i, {его номер}

DegA:tIndex; {степень полинома}

begin


SetZero(y);{y:=0}

DegA:=Degree(Polynom);

for i:=1 to DegA do

begin


Coefficient:= Element(Polynom,i); { Coefficient := ai }

Mult(y, Coefficient,y);{y:=y*x+ai;}

end; {for}

end; {procedure PolynomValue }

Выделены операторы типа "арифметика комплексных чисел" - или, в более программистской терминологии, "подзадачи"




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

tIndex=1..100; {строго говоря - ограничиваем постановку}

tComplex=record x,y:real end;

tComplexPolynom=record Coefficient:array[tIndex] of tComplex; Degree:tIndex end;

procedure SetZero(c:tComplex); begin c.x:=0;c.y=0 end;

{function Degree(p:tPolynom):tIndex; = p.Degree }

{function Element(p:tPolynom,i:tIndex):tComplex;=p.Coefficient[i] }

procedure Mult(a,b:tComplex;c:tComplex);

begin

c.x:=a.x*b.x-a.y*b.y;

c.y:= a.x*b.y+a.y*b.x;

end;


procedure PolynomValue(Polynom: tComplexPolynom; var y: tComplex);

var


{Coefficient:tComplex; = Polynom.Coefficient[i] }

i:tIndex; {номер коэффициента}

{DegA:tIndex; = Polynom.Degree }

begin


SetZero(y);{y:=0}

for i:=1 to Polynom.Degree do Mult(y, Polynom.Coefficient[i],y);{y:=y*x+ai;}

end; {PolynomValue }

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


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


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

  2. Формальная семантика параметров-значений. Перед телом процедуры проставь операторы присваивания V:=E, V - имя формального параметра, E - соответствующее ему в обращении выражение (фактический параметр-значение)

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


Пример построения модифицированного тела процедуры.
{процедура линейного поиска значения в массиве}

{спецификация: found:=x a   i [1..LenA] (x=ai) }

procedure poisk(x:T;A:tArray;LenA:tIndex; var found:boolean);

var i:tIndex;

begin

found:=false; i:=1;



while (i<=LenA) and not found do if A[i]=x then found:=true else inc(i)

end;
Построим обращение для poisk(2*i,X,10,b)  ?



  1. (Избавление от коллизии имен)

found:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then found:=true else inc(i1)

  1. (Присваивание значений параметров-значений)

x1:=2*i; a:=x;LenA:=10; found:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then found:=true else inc(i1)

  1. (Замена имен параметров-переменных)

  2. x1:=2*i; a:=x;LenA:=10; b:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then b:=true else inc(i1)

т.е. poisk(2*i,X,10,b)  x1:=2*i; a:=x; LenA:=10; b:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then b:=true else inc(i1)
Побочный эффект - фактическое изменение значений глобальных объектов в теле процедуры, не отражаемое формально, т.е. синтаксически, при обращении к процедуре - а потому, неявное для программиста - пользователя процедуры.

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

procedure poisk(x:T;A:tArray; var found:boolean);

{found:=i[1..LenA](x=ai)}

{var i:tIndex; - сэкономили память!}

begin

found:=false; while (LenA>=0) and not found do if A[i]=x then found:=true else dec(Len)



end;
В отличие от параметров процедуры, глобальные объекты никак не участвуют в модификации тела процедуры, потому обращение вида poisk(x,a,b) не только найдет правильное значение b, но и обнулит значение глобальной переменной LenA, содержащую по смыслу фактическую длину массива а и тем самым "закроет" его элементы для дальнейшей обработки.
Потому - либо а) (правило полной локализации) вообще не используй локально (т.е. в теле процедуры) глобальные объекты, либо, как минимум б) не изменяй их значений в теле процедуры. В любом случае использования глобальных объектов помечай такое использование синтаксически (в виде комментария).

  1   2   3   4   5


©netref.ru 2016
әкімшілігінің қараңыз

    Басты бет