План Разбор описания Алгоритма "точное предписание о порядке выполнения действий, из заданного фиксированного множества, для решения всех задач, заданного типа". Вводятся понятия: исходные данные, результат, действия, исполнитель
| Вид материала | Лекции |
- «бесконечность», 189.92kb.
- Понятие, свойства и способы описания алгоритма, 81.96kb.
- Ю. А. Самарский 10 июня 2011 г. Программа, 140.09kb.
- Понятие алгоритма, 18.42kb.
- Программа по дисциплине: информатика (алгоритмы и алгоритмические языки). Продвинутый, 140.13kb.
- Программа по дисциплине информатика (алгоритмы и алгоритмические языки). Основной курс, 103.21kb.
- План урока Организационный момент(1 мин) Проверка материала прошлого урока(10 мин.), 53.54kb.
- Для заданного полупроводникового диода, 92.07kb.
- Сценарий занятия по теме «Инсценировка произведения С. Маршака «Сказки о глупом мышонке», 37.09kb.
- Методические рекомендации: Взадачах такого типа используются понятия: объем видеопамяти, 338.92kb.
Лекция 5
Язык программирования Pascal
Введение
Язык программирования - формальная алгоритмическая система, ориентированная на практическую реализацию А на ЭВМ. Именно на практическую реализацию, а не изучение, как в случае МТ и НАМ.
На беглом review алгоритмов нахождения НОД и определения четности числа (b=2) в интуитивной форме обсуждаются основные понятия :
точка управления;
данные - константы и переменные;
выражения - правила вычисления значений;
действия - над данными по изменению значения; изменение положения точки управления.
Изучение любого языка программирования сводится к изучению того какие данные и как могут быть представлены в программах на языке, вычисления какого типа значений и как могут быть заданы; какие действия над значениями и точкой управления допустимы. Поскольку ранее было показано, что формально достаточно последовательной композиции, выбора и цикла надо понять как они воплощены в языке.
Язык программирования - формальная система обозначений для описания А в виде текста, пригодного для восприятия автоматом.
Вводятся понятия алфавита, синтаксиса и семантики, синтаксической диаграммы. (Основной источник Абрамов, Трифонов, Трифонова Введение в Паскаль.)
Концепция данных в Pascal.
Обсуждаются понятия значение, константа и переменная.
Значение - это имя специального вида, изображение этого значения.
Константа - программный объект, имеющий уникальное имя и постоянное значение, которое нельзя изменить в ходе работы программы. Константа характеризуется именем и значением.
Рассматривается СД для константы.
Семантика константы: фиксирование значение, доступное через имя. Имя не может быть использовано для изменения значения. Допустимые значения : число, символ, строка.
Описание констант в разделе констант (CONST).
Переменная - программный объект, имеющий уникальное имя и способное принимать значения ТОЛЬКО из множества значений, фиксированного для данного имени.
Семантика:
1.В каждый момент переменная может принимать только одно значение;
2.Может хранить значение из строго фиксированного множества;
3.При размещении новго значения - старое теряется;
4.Копировать текущее значение можно сколько угодно;
5.Доступ к значению только через имя;
6.До того как переменной было впервые присвоено значение, ее значение не определено.
Переменная характеризуется - именем, через которое осуществляется доступ к ее текущему значению; множеством допустимых значений называемым типом переменной.
То насколько множество типов, допустимых в языке, соотвествует требованиям задачи, в занчительной степени определяет пригодность языка для задачи.
Вводится иерархия типов в Pascal. Последовательно обсуждаются элементы этой иерархии.
^ Система типов в Pascal
Основные Производные
Скалярные Ссылочные
Стандартные Определенные
Тип Integer
Этот тип рассматривается как тройка
({подмн-во целых чисел},{+,-,*,div,mod},{>,succ,pred}) т.е. множество объектов, множество операций (алгебраических) над объектами, отношение упорядочения на множестве объектов.
{подмн-во целых чисел} характеризуется двумя константами
maxint: AieInteger (i є maxint);
minint: AieInteger (i Є minint);
Иногда minint = -maxint Конкретное значение констант определяется реализацией.
Формулируется свойство:
Ax,y,z: |x+y|
Пример
(60+50) + (-40) ; 60+ (50+(-40))
Все операции выполняются точно.
Дополнительные функции: abs, sqr,succ,pred.
Тип Char = ({мн-во символов},{},{<,succ,pred})
Еще раз подчеркиывается отличие имени от значения: О - имя, 'О'- значение.
Стандартный набор мн-ва символов: - A - Z; - 0 - 9; - ;.:!?'eol и д.р.
Выводы :
1. Программа - А описанный для его выполнения автоматом специального вида, называемого компьютер;
2. Язык программирования - формальная система обозначений для описания А, в форме пригодной для восприятия автоматом;
3.Язык программирования - А.с., ориентированная на практически эффективную реализацию А и где испонитель есть автомат специального вида - компьютер;
4. Изучение всякого Я.п. сводится к изучению того как в этом Я.п. реализованы концепция данных (значения, константы и переменные), выражения (правила вычислений значений), действия над значениями переменных и действия над управлением.
5. Синтаксис Я.п. - формальные правила описания вышеперечисленных концепций в Я.п.
6. Семантика Я.п. - точное значение этих концепций.
Вопросы:
1.Что такое программа?
2.Чем программа отличается от А?
3.Что такое имя (синтаксис, семантика)?
4.Для чего оно используется?
5.Чем имя отличается от значения?
6.Что такое синтаксис?
7.Что такое семантика?
8.С помощью каких понятий данные представляются в программе?
9.Обязательно ли константа имеет имя?
10.Что такое служебные слова?
11.Что такое стандарт языка?
12.Чем константа отличается от значения?
13.Что такое переменная?
14.Что такое тип переменной?
15.Определите семантику константы?
16.Определите семантику переменной?
Лекция 6
Типы Real и Boolean
Тип Real = {(мн-во представителей веществ},{+,-,*,/},{})
Подробно рассматиривается устройство мн-ва представителей вещественных чисел (ПВЧ). x - ПВЧ: x = m*B ,
Любой x представляет множество X - подмножество R. Операции над X не точны и удовлетворяют следующим аксиомам:
1.Тип Real (R) - подмножество R: R U C < R . {0,1} C R
2. Для любого x, принадлежащего R существует единственный s, прин. R: (R(x)=s);
3. x представляет связный интервал, т.е. Для любых x1 ,x2 ,прин.R и x1
4. Сущ. Max, принадл. R: Для любого x, прин. R . (x > Max) => R(x) неопределено;
Из А1 - А4 следует:
x < y => X<=Y
x = y => X=Y
x > y => X>+Y .
5. R симметрично относительно 0: (-x ) = -(x) .
6. Коммутатовность: x+y = y+x; x*y = y*x.
7.x>=y>=0 => (x-y)+y = x.
8.Симметричность операций относительно 0:
x-y = x+(-y) = -(y-x) (-x)*y = x*(-y) = -(x*y) (-x)/y = x/(-y) = -(x/y).
9.Монотонность: Если 0<=x<=a и 0<=y<=b, то
x+y<=a+b
x-b<=a-y
x*y<=a*b
Разъясняется смысл этих аксиом. На примерах показывается нарушение ассоциативности и диструбутовности арифметики на множестве представителей вещественных чисел.
Рассматривается пример решения квадратного уравнения. Демонстрируетсякак в зависимости от порядка вычислений мы можем получить разные результаты.
Стандартный набор функций: sin, cos, arctan, ln, exp, sgrt. Обращается внимание на полимофизм операций сложения, умножения и вычистания.
^ Тип Boolean = ({true,false},{NOT, OR, AND},{false < true}). Вводятся определения логических операций.
Рассматриваются встроенные функции свзывающие разные типы: trunc, round, ord, odd, chr.
Выводы :
1. Арифметические операции на Integer всегда выполняются точно.
2.Множество Integer упорядочено.
3.Множество Char обязательно содержит большие латинские, 10 цифр и набор спец.символов.
4.Множество Char упорядочено.
5.Тип Real - это множество представителей вещественных чисел.
6.Каждый представитель соответсвует целому подмножеству вещественных чисел.
7.На множество Real законы ассоциативности и дистрибутивности арифметтических операций не выполняются.
8.Арифметические операции на Real выполняются с ограниченной точностью.
Вопросы :
1. Пильщиков разделы 1-2;
2. Для каких типов данных определена функция ord?
3.Что такое полиморфизм арифметическитх операций?
4.В чем состоит полиморфизм операций +,-,*?
5.Как устроен представитель вещественных чисел?
6.Что такое мантисса?
7.Что такое порядок?
8. Почему
x < y => x <= y
x = y => x = y
x > y => x >= y ?
9.Как связаны между собой Integer - Real, Integer - Char, Integer - Boolean, Real - Char, Real - Boolean, Char - Boolean?
Лекция 7
Выражение. Концепция действия
Выражение - правило вычисления значения. Оно строится из операндов, знаков опреаций и скобок, определяющих порядок вычислений.
Операнд - Костанта, Переменная или Вычисляемый.
Рассматриваются каждый из этих операндов. Выражение имеет тип такой же как и тип значения, который оно определяет. Тип выражения не может меняться.
Арифметические операции +,-,* - это полиморфные операции. Операция называется полиморфной если она определена на значениях разных типов.
В арифметических выражениях если хоть один из операндов полиморфной операции имеет тип Real, то результат этой операции имеет этот же тип.
Подробно рассматриваются синтаксические диаграммы Арифметического выражения. Обращается внимание что эти диаграммы определяют порядок вычисления. Подробно рассматриваются синтаксические диаграммы для логических выражений.
Рисуется диаграмма взаимосвязи типов. Например, с помощью каких операций или функций, имея значение типа real, можно получить тип integer и наоборот.
Концепция действия
В соотвествии с результатами первой части выделяем действия над данными (изменение значения) и над управлением. Ранее был построен полный набор действий последовательной композиции, параллельной композиции, если_то_иначе, цикл. Рассматривается реализация этих действий а Pascal.
^ Оператор присваивания.
V := E
V - переменная, E - выражение. V и E должны быть одного типа. Результат действия - изменение значения переменной.
Составной оператор.
Рассматривается синтаксис и семантика составного оператора. Подчеркивается что ; - разделяет операторы, но не входит в их состав. ; - аналог последовательной композиции.
Обращается внимание что в Pascal нет средств, позволяющих передать управление внутрь составного оператора. Управление в составной оператор может попасть только через операторную скобку begin.
Выбирающий оператор.
Рассматривается синтаксис и семантика условного оператора. Приводятся примеры его использования. Подчеркивается, что в Pascal нет средств, позволяющих передать управление внутрь альтернативы или из одной альтернативы в другую. альтернативы или из одной альтернативы в другую.
Лекция 8
Операторы повторения. Структура программы. Перечислимый и
ограниченный типы.
^ Операторы повторения.
Рассматриваются синтаксис и семантика операторов цикла с предусловием, постусловием и параметром. Демонстрируются примеры использования этих операторов. Обращается внимение что Pascal непозволяет войти в тело цикла иначе как через заголовок цикла.
Кратко рассматривается структура программы в Pascal, как синтаксической конструкции.
В качестве примеров использования ранее рассмотренных операторов и программ на Pascal рассматриваются: вычисление факториала, суммы гармонического ряда, умножения двух целых чисел через сложение. Для каждого варианта программы подсчитывается сложность.
^ Скалярные типы, определяемые программистом.
Перечислимый тип.
({мн-во имен},{},{<,succ,pred,ord})
Рассматривается синтаксис и семантика перечислимого типа в Pascal. Значения этого типа - множество имен в смысле Pascal. Показываются два способа описания этого типа через введение нового имени типа и непосредственное определение при описании переменной.
Обращается внимание на то, что недопустимо использование одного и того же имени как значения в разных перечислимых типах. Объясняется в каких случаях типы считаются одинаковыми, а в каких различные.
Рассматриваются операции определенные над значениями этого типа: succ, pred, ord, <.
Обращается внимание на сложности при вводе и выводе значений перечислимого типа. В частности, что функции write и writeln не определены на множестве значений этого типа. Решить эту проблему позволяет опретаор варианта case.
Рассматривается синтакис и семантика этого опреатора. Обращается внимание на два ограничения этого оператора: в теле оператора case должны быть перечислены все возможные альтернативы; нельзя передать управление внутрь тела этого оператора или из одной альтернативы на другую.
Выводы :
. В любой оператор цикла нельзя войти иначе как через заголовок;
. В Pascal есть три вида циклов while_do, repeat_until, for;
. После выхода из цикла for значение параметра цикла не определено, менять значение параметра цикла в теле цикла запрещено;
. Перечислимый тип - множество имен.
Лекция 9.
Ограниченный тип. Производный тип: массивы.
^ Ограниченный тип.
Ограниченный тип данных - это подмножество перечислимого типа либо одного из стандартных типов (кроме Real), ограниченного сверху и снизу константами.
Рассматривается синтаксис и семантика ограниченного типа, способы описания этого типа, условия эквивалентности ограниченных типов данных.
^ Производные типы. Массивы.
Производные типы - это типы данных с неатомарными значениями. Первым из этой группы типов рассматриваются массивы.
^ Одномерные массивы.
Массив - упорядоченный набор фиксированного числа однотипных компонент. Тип компонент называется базовым типом. Каждый массив имеет уникальное имя. Это имя представляет полную переменную-массив. Подчеркивается что значением этой переменной является весь массив.
Для доступа к отдельным компонентам полной переменной импользуется селектор называемый индексом массива. Имя массива с индексом конкретного компонента назывется частичной переменной. Значение индекса может меняться. Следовательно частичная переменная может представлять разные компоненты массива. Значение индекса может быть задано явно в виде константы, переменной, выражения. Значение индекса должно принадлежать скалярному упорядоченному типу. Отсюда следует что тип real не может служить типом индекса.
Над полным значением типа массив в Pascal не определено никаких операций кроме присваивания.
Рассматривается синтаксис описания и использования массивов, примеры программ.
^ Многомерные массивы - это массив компонентами которого являются массивы. Рассматриваются синтаксис, семантика и примеры использования многомерных массивов.
^ Строковые переменные принимают значения из строкового типа. Строковый тип - упакованный одномерный массив, компоненты которого имееют символьный тип. В отличие от массивов строковый тип имеет ряд особенностей:
- есть строковые константы (у массивов нет констант);
- значения строковых переменных одинаковой длины можно сравнивать.
Лекция 10
Пример составления программы
^ Рассматривается задача:
Написать программу на Pascal, которая бы для произвольного лабиринта в котором есть две площадки, помеченные как A и как M, строила бы простой путь от A к M. Если M не достижима (или например отсутствует), то останавливается на площадке A.
Путь назывется простым если он не проходит дважды ни через одну площадку.
Лабиринт есть множество площадок, соединенных коридорами. Все коридоры равноценны. По коридору можно двигаться в любом направлении.
Эта задача рассматривается в интерпритации легенды об Ариадне и Тезее. Площадка A - площадка где находится Ариадна, площадка M - площадка Минотавра. Тезей должен найти Минотавра, убить его и вернуться к Ариадне (по простому пути, ведь у него есть нить Ариадны).
Акцентируется внимание на следующих проблемах:
- как описать лабиринт;
- как это описание представить на Pascal;
- как отразить в лабиринте нить Ариадны;
- надо построить алгоритм;
- доказать его корректность, т.е. что он решает поставленную задачу;
- реализовать этот алгоритм в виде программы на Pascal.
Считается что все корридоры в лабиринте изначально зеленого цвета. Если Тезей прошел один раз по коридору, то коридор становится желтым. Если Тезей прошел по желтому коридору, то коридор становится красным. По красному коридору Тезей никогда не ходит.
Каждая площадка имеет тип. Есть следующие типы площадок:
Минотавр (М) - на этой площадке есть Минотавр;
Петля - к этой площадке ведут два желтых коридора;
Зеленая улица - у площадке есть хотя бы один зеленый коридор;
Ариадна - на площадке есть Ариадна;
Прочее - все остальные случаи.
Ясно что тип площадки определяется не однозначно. Тезей может либо наматывать нить, либо ее разматывать. Наматывать - пройти по последнему желтому коридору, по которому Тезей пришел на эту площадку, перекрасив этот коридор в красный цвет. Разматывать - пройти зеленым коридором на другую площадку, изменив цвет коридора на желтый.
Алгоритм:
1. Начинаем с площадки, где стоит Ариадна;
2. Проверь:
если есть Минотавр, то тип площадки - Минотавр;
если есть два желтых коридора, то - Петля;
если есть хоть один зел.корилор, то - Зел.улица;
если есть Ариадна - Ариадна;
во всех остальных случаях тип площадки есть Проч.
3. Если тип площадки:
Минотавр - стоп;
Петля - наматывай нить;
Зелулица - разматывай;
Ариадна - стоп;
Проч - наматывай.
4. Вернись к шагу 2.
Доказатальство корректности Алгоритма.
Утв.1 При любом взаимном расположении А и М в лабиринте, после конечного числа шагов обязательно наступит остановка либо на площадке А, либо на площадке М;
Утв.2 Если отановка произошла на площадке М, то Минотавр достижим и нить протянута по простому пути, наматывая ее Тезей вернется к Ариадне.
Утв.3 Если остановке произошда на площадке А, то Минотавр не достижим.
Все утвеждения доказываются.
program Тезей (input, output);
const I0 = ...; J0 = ...;{координаты начального положения Тезея}
N = ....;{количество площадок в лабиринте}
type коридор = (Ардна,Мнтвр,Никого,Жлт,Злн,Крс);
var движение:boolean {логический признак выхода из основного цикла};
ищи:boolean{логический признак для определения типа площадки};
S,K,I,J,C:integer;{S - длина пройденного пути,
K - вспомогательная переменная,
I - номер площадки;
J - номер коридора;
C - число жлт коридоров}
ЛБРНТ:array [1..N,0..N] of коридор;
{ ЛБРНТ[I,0] - указывает есть ли кто на площадке;
ЛБРНТ[I,J] - указывает цвет коридора J}
ПУТЬ:array [1..N] of 1..N;
{площадка идентифицируется своим номером}
типлщдки:(минотавр,петля,злнулица,ариадна,проч);
begin
for I:=1 to N do
for J:=0 to N do {read (ЛБРНТ[I,J]); - Ввод лабиринта}
{Надо иметь ввиду, что ЛБРНТ[I,J]- перечислимого типа}
{поэтому просто read проблему ввода не решит}
I:=I0; J:=J0; {начальное размещение Тезея; ЛБРНТ[I,0]=Ардна}
{I0,J0 - могут быть введены из вне}
движение := true;
while движение do
begin
{определение типа площадки};
case типлщдки of
минотавр: движение:=false;
{нашли Минотавра}
петля : {наматывай};
злнулица: {разматывай}
ариадна : движение:=false;
{Минотавр не достижим}
проч : {наматывай}
end {case}
end{while}
end{program}.
{определение типа площадки}
типлщдки:=Минотавр;
Ищи:=true;
while ищи do
begin C:=0;
case типлщдки of
Минотавр: if ЛБРНТ[I,0] = мнтвр then ищи:=false
else типлщдки:= succ(типлщдки);
Петля: begin K:=1; while K<=N do
begin
if ЛБРНТ[I,K]=Жлт then
begin J:=K; C:=C+1 end;
K:=K+1;
end;
if C>=2 then ищи:=false
else типлщдки:= succ(типлщдки);
end{Петля}
Злнулица: begin К:=1;
while(К<=N)AND(ЛБРНТ[I,K]<>Злн) do К:=К+1;
if К<=N then begin J:=K; ищи:=false end
else типлщдки:= succ(типлщдки);
end{Злнулица};
Ариадна: if ЛБРНТ[I,0]=Ариадна then ищи:=false
else типлщдки:= succ(типлщдки);
Проч: begin if NOT(C=1)AND NOT(ЛБРНТ[I,J]=Жлт)
{Это условие должно выполяться после Петля}
then begin writeln('Ошибка в лабиринте');
движение:=false
end;
ищи:=fasle
end{Проч}
end {case};
end;
{Наматывай} ЛБРНТ[I,J]:=Крс; K:=I; I:=J; J:=K; ЛБРНТ[I,J]:=Крс;S:=S-1;
{Разматывай} ЛБРНТ[I,J]:=Жлт; K:=I; I:=J; J:=K; ЛБРНТ[I,J]:=Жлт;
^ S:=S+1; ПУТЬ[S]:=I;
Следует обратить внимание на следующие моменты:
- процесс абстракции при выборе структуры (математической) для описания понятия лабиринт;
- выбор способа представления выбранной структуры средствами языка программирования;
- ЛБРНТ[I,0] и ЛБРНТ[I,J] имеют разный тип, но мы вынуждены определять их одного типа;
- способ работы с перечислимым типом в цикле;
- способ выхода из цикла.