План Разбор описания Алгоритма "точное предписание о порядке выполнения действий, из заданного фиксированного множества, для решения всех задач, заданного типа". Вводятся понятия: исходные данные, результат, действия, исполнитель
| Вид материала | Лекции |
- «бесконечность», 189.92kb.
- Понятие, свойства и способы описания алгоритма, 81.96kb.
- Ю. А. Самарский 10 июня 2011 г. Программа, 140.09kb.
- Понятие алгоритма, 18.42kb.
- Программа по дисциплине: информатика (алгоритмы и алгоритмические языки). Продвинутый, 140.13kb.
- Программа по дисциплине информатика (алгоритмы и алгоритмические языки). Основной курс, 103.21kb.
- План урока Организационный момент(1 мин) Проверка материала прошлого урока(10 мин.), 53.54kb.
- Для заданного полупроводникового диода, 92.07kb.
- Сценарий занятия по теме «Инсценировка произведения С. Маршака «Сказки о глупом мышонке», 37.09kb.
- Методические рекомендации: Взадачах такого типа используются понятия: объем видеопамяти, 338.92kb.
^ Лекция 11-12.
Комбинированный и множественные типы данных.
Здесь продолжается изучение производных типов данных.
Производные типы
Регулярный Комбинированный Множественный
^ Комбинрованный тип данных
Элементы этого множества есть наборы фиксированного числа поименованных компонентов разного типа. Зачение этого типа называются записью. Компоненты записи называются полями. Каждое поле имеет имя, уникальное на своем уровне внутри записи. На разных уровнях внутри записи могут быть однаковые имена. Эти имена "видимы" только внутри записи. На тип поля ограничений нет.
комбинированный тип::=record <список полей> end
список полей::= <секция записи>{;<секция записи>}
секция записи::=<имя поля>{,<имя поля>:<тип>}
Доступ к значению поля осуществляется через частичную переменную записи. Каждая заптсь имеет столько частичных переменных, сколько полей в записи. Имя частичной переменной строится как перечисление вершин в дереве записи, от крня до вершины представляющей нужное поле.
Курс
Админчст Группы
Нач.крс Испктр Стрст Стрст Студент
имя фмлия пол г/р адрс
грд улца д кв
В этом примере, значение поля грд храниться в частичной переменной с именем курс.группы.студент.адрес.грд.
- При определении кимбинированного типа порядок перечисления полей не важен.
- Имя поля вычислить нельзя (в отличии от регулярного типа), его всегда надо указывать явно.
- нельзя использоватть имени поля без имени полной переменной.
Для полных переменных в Pascal определен только оператор присваивания.
^ Оператор присоединения.
Этот оператор позволяет сократить длину имени частичной переменной там где эта переменная интенсивно используется.
with <список переменных комбинированного типа> do <любой оператор Pascal>
При использовании этого оператора могут возникать два вида коллизий имен:
1.У переменных, перечисленных в списке комбинированного типа, есть поля с одинаковыми именами;
2.В программе есть переменная с тем же именем как и имя поля переменной из списка переменных комбинированного типа.
Первая коллизия разрешается так: это имя поля трактуется как имя поля той полной переменной, которая перечислена в списке переменных комбинированного типа позже.
Вторая коллизия разрешается в пользу имени поля, т.е. при совпадении имен переменной и поля, это имя трактуется как имя поля, а не имя переменной.
^ Множественный тип.
Множественный тип - это не упрядоченный набор конечного числа однотипных элементов, среди которых нет повторяющихся. Тип элемента - базовый тип множества. Базовым типом может быть любой скалярный тип, кроме real. Значение мноежественного типа задается через коструктор множества:
[{список значений базового типа через запятую}]
Значения в списке могут быт заданы явно, в виде имени переменной или выражения, надлежащего типа. Таким образом [] - можно расматривать как операцию образования значения множественного типа.
В качестве элемента списка значения может выступать диапазон значений надлежацего типа: <значение>..<значение>. Значения в описании диапазона могут быть заданы явно либо в виде имен переменных, либо в виде выражений.
^ Операции над значениями множественного типа.
Рассматриваются операции объединения (+), пересечения (*), вычитания (-) множеств. Результат этих операций - значение множественного типа, даже если мощность результирующего множетва - единица.
Рассматриваются операции отношения на значениях множественного типа: включение (in), сравнения (<,>,=).
Рассматривается пример программы, реализующий решето Эратосфена, для выбора из множества натуральных чисел от 2 до 201 всех простых чисел.
(Замечение. В книге Абрамова, Трифонов, Трифонова в этом примере опечатка! Переменная k не может иметь тип 2..N, т.к. в этом случае вложенный repeat работать не будет (условие k>N - не будет выполнено никогда)). никогда)).
Лекция 13.
П р о ц е д у р ы .
Процедуры вводятся как механизм реализации концепции построения алгоритмов из алгоритмов. (Эта концепция была подробно рассмотрена в первой части лекций.) В языках программирования эта концепция реализуется в разной форме. Аппарат процедур - лишь одна из них, но чрезвычайно важная, в силу эффективности.
С другой стороны процедура рассматривается как поименованная последовательность действий. Благодаря наличию имени эту последовательность можно неоднократно использовать и инициировать.
Аппарат процедур позволяет:
- упростить реализацию, за счет компактности записи программы;
- упростить процесс отладки программы, за счет ясности текста программы;
- упростить процесс разработки программы за счет срутктуризации программы;
- ускорить разработку программы за счет многократного использования заготовок.
^ Описание процедуры вводит и именует последоательность действий. Оператор процедуры инициирует выполенение ранее описанной оследовательность действий.
описание П ::= заголовок П ; блок заголовок::= procedure имя П (список форм.парм.) оператор П ::= имя П | имя П ( список факт.парм.)
Параметры - средство, позволяющее отмечать те данные, которые поодлежат изменению при вызове процедуры. ^ Фактические параметры - те конкретные объекты, с которыми будет происходить выполнение действий в теле процедуры.
Сначала рассматриваются примеры процедуры без параметров. Разъясняется их семантика. Показывается ограниченность их возможностей.
^ Процедуры с параметрами.
Параметры значения. Вводится понятие параметра-значения. Разъясняется его синтаксис и семантика. Обсуждается область его действия и время жизни. Подчеркивается что параметры значения существуют только в период выполенения процедуры. Значения фактическиз параметров-значений вычисляются в момент вызова и затем до конца выполнения процедуры не перевычисляются. В качестве фактического значения может быть любое выражение соответсвующего типа. (Проблеме соотвествия типов уделяется особое внимание. Хорошо бы получше отработать на семинарах.)
Параметры-переменные
Параметр-переменная вводится как объект тела процедуры, между которым устанавливается связь с фактическим параметром (переменной программы), такая что изменения значения параметра-переменной при выполнении тела процедуры обязятельно вызывает соответсвующие изменения надлежащего фактического параметра в теле программы.
Разъясняется синтаксис и семантика передачи параметров по ссылке.
^ Параметры-значения прозводных типов.
На примерах показывается что если значение производного типа передается как значение, то происходит копированние этого значения в теле процедуры. Это может привести к значительным накладным расходам.
В то же время на следующем примере показывается опасность передачи объектов производных типов по ссылке. В этом случае надо быть очень аккуратным. В случае наличия взаимосвязи между ними возможны неприятности.
Type
procedure Mult (var x,y,z: matrix);
var i,j,k,s: integer;{i,j,k - параметры циклов;
s - для промежуточных сумм}
begin
for i :=1 to N do
for j :=1 to N do
begin s:=0;for k :=1 to N do
s:=s+x[i,k]*y[k,j];
z[i,j]:=s
end
end{procedure}
A =... B =...
Если рассмотреть результаты обращений Mult(A,B,C), Mult(A,B,A),Mult(A,B,B), то получим следующие результаты: ...
Причина этого в том что параметры-переменные связаны между собой в теле процедуры.
^ Синтаксис списка формальных параметров.
Здесь рассматриваются правила спецификации формальных параметров, объединения их в секции и т.д. Разъясняется важность порядка перечисления параметров в списке. Отмечается что здесь при спецификации формального параметра может быть только имя типа, но не его описание. Это приводит, в частности, к тому, что нельзя написать процедуру для обработки массивов переменной длины.
^ Область действия имен. (Принцип локализации имени.)
Здесь разъясняются понятия локального, глобального объектов и объектов-параметров. Объясняется как их различать. Как разрешаются коллизия имен между ними.
^ Оператор процедуры.
Рассматривается синтаксис оператора процедуры.
1.Если у процедуры нет параметров, то оператор состоит только из имени.
2.Число фактических параметров должно в точности совпадать с числом формальных параметов.
3.Тип фактического параметра должен соотвествовать типу формального.
4.Надо четко отслеживать, что представляет формальный параметор - значение или переменную. Так, например, если он - значение, то при передачи переменной с индексами, значение индексного выражения как бы фиксировано на все время выполнения процедуры.
В заключение отмечается что в разных языках прогаммирования механизм процедур выглядит по-разному. Так, в частности, для передачи парамеров в процедуру могут встретиться четыре способа (их больше, но эти широко распространены): по значению, по имени, по ссылке, по ссылке - результату. Различия между первыми тремя демонстрируются на слудеющем примере:
var i:integer;
a:array [1..2]of integer;
procedure P(x:integer);
begin i:=i+1; x:=x+2 end
begin a[1]:=10; a[2]:=20; i:=1; P(a[i])end
по значению x:=10; a[1]:=10; a[2]:=20;
по ссылке x=a[1];a[1]:=10; a[2]:=20;
по имени x=a[i];a[1]:=10; a[2]:=22;
Лекция 14.
Ф у н к ц и и
Когда мы рассматривали выражения, мы отмечали три вида операндов - значения, переменные и вычисляемые. Под вычисляемыми операндами имелись ввиду поименнованные фрагменты вычислений значений, которые выполнялись только при обращении к ним. Такой механизм, подобно процедурам, предполагает предопределение правил вычислений значений, сопоставление каждому правилу своего имени, а затем, всякий раз там где нам надо вычислить значение по одному из этих правил, достаточно лишь указать его имя. Этот механиз в Pascal реализуется посредством функций.
В отличии от процедур, функции - определяют правила вычисления значений. В отличие от процедур функция не определяет, что надо делать с полученным значением. Отсюда, например, так как над производными типами практически нет операций, то значения, получаемые через функции, могут быть только простых типов.
^ Описание процедуры-функции.
Для определения правила вычисления значения используется понятие <описание фукции>. Это описание размещается в разделе роцелур и функций того блока, где они используются.
<описание фукции>::=<заголовок функции>;<блок>
<заголовок функции>::=function<имя функции> :<имя типа>
<список формальных параметров>
Подобно процедурам функции могут быть без параметров, могут иметь параметры-значения и параметры-переменные. Имя типа в заголовке функции необходимо по двум причинам:
- для определения типа выражения, надо знать типы операндов;
- для контроля правиольности использования функции в программе.
Подобно поцедуре тело функции - блок. Как же определить какой из результатов, получаемых в теле функции - значение функции? Для этого в теле функции обязятельно должен быть хотя бы один выполняемый оператор присваивания вида <имя функции>::=<выражение>.
Итак, основные отличия описания процедуры от описания функции:
- служебное слово function в заголоаке;
- имя типа значений функции в заголоаке;
- в теле должен быть оператор присваивания с именем функции в правой части.
^ Вызов функции.
Для инициации выполнения тела функции служит оператор вызова функции, который часто мы и будем называть функцией. За исключением того, что вызов функции может использоваться только в выражениях, кроме уже перечисленных дугих отличий функции от процедуры нет. Т.о., функцию всегда можно описать как процедуру и наоборот. Что и когда надо использовать?
Дело втом, что функция должна иметь один результат - значение. Процедура - несколько. Поэтому, если именуемая последоватедьность действий создается ради неоднократного вычисления значения с разными данными, то это - функция, если кроме этого предполагается изменение значений нескольких объектов в программе - процедура.
^ Побочный эффект.
Функция имеет единственный эффект - вычисление значения. Вообще говоря, не должно быть в программе других эффектов от вызова функции. Pascal однако, допускает функции, в теле которых может изменяться значения глобальных объектов. Подобные действия называются побочным эффектом.
Побочный эффект опасен уже тем, что из текста программы не возможно усмотреть, что кроме выработки значения функция меняет значения каких-то объектов программы.
(Рассматриваются примеры побочных эффектов.)
^ Параметры-функции, параметры-процедуры.
Рассмативается реализация на Pascal алгоритма нахождения нулей функции методом деления отрезка пополам. Ясно, что если этот алгоритм надо применять к разным функциям в программе, то разумно было бы оформить его как функцию. Для этого надо уметь передавать функцию, для которой надо вычислить нули, как параметр.
Pascal допускает использование процедур и функций в качестве параметров. Единственное ограничение на функции и процедуры, передаваемые как параметр - они не должны иметь параметров-переменных.
program Fork (input, output);
const eps = 1E-14;{точность вычислений}
var x,y:real;
function zero (function f(x:real):real; a,b:real):real;
var x,y:real; s:boolean;
begin
s:=f(a)<0;{a - левая граница отрезка}
repeat
ищем нули}
if (z<0)=s then a:=x else b:=x {b - правая граница oтрезка}
until abs(a-b)
end
Также обращается внимание, что в случае параметров функций и процедур их значения передаются по имени.
Рекурсия
Рекурсия вводится, опираясь на опыт синтаксических определений, для которых при их построениях, она отмечалась всякий раз особо. Приводятся примеры рекурсивных определений факториала, чисел Фиббоначи, нечетных чисел.
Процедура ( везде далее подразумевается также и функция ) называется рекурсивной, если в процессе своего выполнения процедуры она обращается к самой себе прямо или косвенно. Обращение назывется косвенным (неявным), елси в теле процедуры есть обращение к другой процедуре, в которой ( возможно через цепочку вызово) есть обращение к исходной процедуре.
Каждое обращение к процедуре вызывает независимую активацию. Совокупность данных, используемых при одной активации, назовем фреймом активации. Фрейм активации содержит значения всех локальных переменных и формальных параметров. Если процедура несколько раз обращалась к себе и ни одно обращение не завершилось, то сществует несколько фреймов.
Рассматривается пример процедуры, распечатывающей строку символов в обратном порядке.
procedure Backprint;
var символ:char;
begin read (символ);
if символ=EOL then writeln{перед началом вывода}
else begin Backprint; write (символ) end
end.
^ Итерация и рекурсия.
На примерах программ вычисления факториала, наибольшего общего делителя (все они уже встречались), строятся иерационный и рекурсивный их варианты. Затем на ниже следующем примере сведения цикла while к рекурсии ставится вопрос о взаимоотношении итерации и рекурсии.
while УловиеЦикла do | procedure РекурЦикл
Телоцикла | begin
end | then
| begin ТелоЦикла;
| РекурсЦикл
| end
| end
1. Каждая итерация может быть заменена рекурсией.
2. Рекурсия не всегда может быть заменена итерацией.
Примером последнего утверждения может служить функция Аккермана:
A(m, n) = n+1 если m=0,
A(m-1, 1) если n=0,
A(m-1, A(m, n-1)) в противном случае.
Лекция 15.
Применеие рекурсии в алгоритмах с возвратом.
Файловый тип. Ввод/вывод.
Есть широкий спектр алгоритмов когда вычисления идут не по фиксированным правилам, а методом проб и ошибок. Примером таких алгоритмов могут служить алгоритм игры чет-нечет; алгоритм поиска пути в лабиринте в задаче об Ариадне и Тезее. Теперь рассмотрим применение рекурсии для решения таких задач.
Применение рекурсии рассматривается на примере задачи обхода шахматной доски ходом коня. Наряду с демонстрацией применения рекурсии еще раз демонтрируется пошагавая, структурная разработка пограммы.
procedure попытка следующего хода;
begin
repeat
if ход преемлем? then
begin
if доска не заполнена? then
begin
if неудача? then стирание предыдущего хода;
end
end
until (ход был удачным?) or (нет других возможных ходов)
end.
В итоге выписывается полный текст программы на Pascal.
^ Файловый тип. Ввод/вывод.
Все рассмотренные ранее типы данных обладали одним общим свойством - число их компонентов конечно и заранее фиксировано. Однако, существует достаточно широкий класс задач, когда количество компонент данных заранее не известно. Пример - задача кодирования текста поступающего на вход в реальном времени, ввод текста, длина которого заранее не известна и т.п.
В Pascal существует тип данных, множество элементов которого есть последовательности однотипных элементов, длина этих последовательностей не фиксируется заранее. Важной характеристикой этого типа, называемого файловым, является то, что доступ к его компонентам строго последовательный. Это означает, чтобы получить доступ к i-му компоненту, необходимо пройти i-1-ый.
Файловый тип - это единственный тип, обладающий тем свойством, что данные этого типа могут иметь время жизни более времени выполнения программы! Поэтому этот тип часто используют, чтобы сохранить результаты работы программы для последующей обработки; либо ввести данные извне. Примеры файлового типа, с которыми мы уже много раз встречались мног раз - input и output.
^ Файлы и работа с ними.
<тип файл>::= file of <тип компонент>
Тип компонент - любой, не содержащий файлового. Файлы бывают внутренние и внешние. Внешние файлы описываются в заголовке программы, в скобках, после имени программы:
program <имя программы>(<список внешних файлов>);
В списке внешних файлов указываются те файлы, чье время жизни больше времени выполнения программы. Если файл не указан в этом списке - он внутренний, т.е. время его жизни равно времени выполнения программы.
Над файлами не определено никаких операций, для них не определен даже оператор присваивания.
Для доступа к компонентам файла в Pascal предопределены специальные процедуры : rewrite(f); reset(f); append(f); read(f); write(f); get(f); put(f); и специальная переменная, так назывемая буферная переменная f^.
На примерах излагаются правила работы и использования перечисленных выше средств работы с файлами. Также рассматривается текстовый файл. выше средств работы с файлами. Также рассматривается текстовый файл.
Лекция 16
Ссылочный тип данных. Динамические объекты.
1. Природа динамических объектов и способы их реализации.
Все объекты, представляющие данные в программе и которые рассматривали до сих пор, были статические в том смысле, что все их параматры, размеры были известны до выполнения программы. Следовательно, ресурсы для их можно было заранее спланировать и выделить.
Существуют задачи, для которых характерно наличие данных: - фактичское появление которых возможно, но не обязательно; - время жизни этих объектов меньше времени исполнения программы. Такие объекты называют динамическими объектами.
Например, если нам надо выбрать из входного потока данных, совокупности данных, обладающих определенными свойствами. Встретим или нет мы такие совокупноси это вопрос. Поэтому выделение ресурсов для их хранения заранее вряд ли разумно. Более того мы не знаем как велика будет такая совокупность. Затем, если собранную совокупность мы должны передать по линиям связи, например, на другую машину, то в нашей программе логично было бы ресурсы, занимаемые переданной совокупностью, освободить для других нужд. (Ресурсов нехватает всегда - это закон.)
Для работы со статическими объектами в языках программирования используется хорошо известный механизм имен. Pascal здесь не исключение. Однако, этот механизм вряд ли нам подходит для представления и манипуляции с динамическими объектами. Дело в том, что имя должно быт известно до выполнения программы - это во-первых. Во вторых, порождение всякого именованного объекта связано с выделением памяти. Раз объекты возникают динамически, то заранее мы не знаем сколько их будет. Следовательно не можем заранее выделить(породить, написать, придумать) нужное количество имен. Далее, не ясно чему соответствует в памяти имя не существующего объекта. Когда объект стал не нужен мы не можем уничтожить имя. Нет таких средств в языке. С другой стороны,уже при написании программы нам надо как-то описывать действия над динамическими объектами.
Для решения этой проблемы в программировании был предложен механизм ссылок. Идея его состоит в том, что данамические объекты представлены не явно, а через некоторую статическую переменную, которая указывает на место расположения динамического объекта, если он существует, либо содержит специальное значение - объект отсутствует. Что значит указывает? Это значит что ее значение - "имя" динамического объекта. Это специальное имя, называемое ссылкой (саму переменную, при этом, часто называют указателем) и которое указывает где размещается, как найти объект и получить доступ к значению.
В случае Pascal такми именем является адрес в памяти где размещается динамический объект. Каждый раз, когда порождается динамический объект ему выделяется место в памяти. Адрес начала выделенной области памяти полагается в качестве значения ссылочной переменной, представляющей динамический объект. При уничтожении динамического объекта занимаемая им память считается свободной, а соответствующая ссылочная переменная принимает специальной значение - нет объекта. Все действия над динамическими объектами в программе описываются как действия над значениями ссылочных переменных. Каждая ссылочная переменная указыает, представляет всегда только один динамический объект.
К недостаткам такого решения можно отнести следующее. Если значение ссылочной переменной (ссылка на динамический объект) будет утеряно - этот объект будет безвозвратно утерян. Ведь его "имени" мы явно не знаем. Оно есть значение ссылочной переменной. Если несколько ссылочных переменных указывают на один и тот же объект и этот объект будет уничтожен с помощью одной из них, то все манипуляции с другими ссылочными переменными станут не корректными.