Лекции по информатике (1113418), страница 3

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

Текст из файла (страница 3)

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<x2 R(x1)=R(x2)=X => (Для лубого xe[x1,x2]: R(x)=X);

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 = ...;{координаты начального положения Тезея}

Характеристики

Список файлов лекций