Рабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная




НазваРабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная
старонка2/3
А П Бельтюков
Дата канвертавання31.01.2013
Памер438.04 Kb.
ТыпРабочая программа
1   2   3


Курс входит в раздел: национально-региональный (вузовский) компонент


  1. Принципы построения


Курс состоит из трёх основных разделов: дедуктивный синтез алгоритмов, индуктивный синтез алгоритмов и трансформационный синтез алгоритмов. Основное внимание уделено дедуктивно-логическому подходу к синтезу программ на основе извлечения алгоритмов из конструктивного логического вывода.



  1. Цели курса


Основная цель курса – дать представления о методах автоматического и автоматизированного синтеза алгоритмов и компьютерных программ, в частности, познакомить студентов с работами автора курса – проф. Бельтюкова А. П.



  1. Учебно-тематический план





Тема


Количество часов

Лекц

Прак.

Сам

1

Основные подходы к синтезу программ

3

2

4

2

Основы дедуктивного синтеза алгоритмов

3

2

4

3

Логические основы дедуктивного синтеза программ

3

2

4

4

Формулы как постановки задач программирования

3

2

4

5

Математические основы программирования и функциональный подход

3

2

4

6

Специализированные языки программирования

3

2

4

7

Постановки ациклических задач

3

2

4

8

Постановки задач с циклами

3

2

4

9

Постановки задач с рекурсиями

3

2

3

10

Синтез полиномиальных программ

3

2

3

11

Язык данных для полиномиального программирования

3

2

3

12

Переменные и выражения в полиномиальном программировании

3

2

3

13

Формальное описание синтаксиса ядра языка. Семантика.

3

2

3

14

Полиномиальная временная сложность синтезируемых программ

3

2

3

15

Расширение языка полиномиального программирования

3

2

3

16

Библиотечные функции, контекстные условия, типы выражений и допустимые типы

3

2

3

17

Индуктивный синтез алгоритмов и программ

3

2

3

18

Трансформационный синтез алгоритмов и программ

3

2

3




  1. Содержание лекционных занятий


Лекция 1. Основные подходы к синтезу программ


1.1. Введение.


История синтеза программ и алгоритмов.


1.2. Виды синтеза программ.


- Дедуктивный синтез.

- Индуктивный синтез.

- Трансформационный синтез.


Лекция 2.


1.3. Основы дедуктивного синтеза алгоритмов.


- Цикл дедуктивного синтеза программ.

- Формальная постановка задачи.

- Исчисление.

- Система вывода решения задачи из постановки.


Лекция 3.


1.4. Логические основы дедуктивного синтеза программ.


- Понятие интуиционистского исчисления.

- Цикл дедуктивного алгоритмического синтеза с

формально-логической точки зрения.

- Формальная теория.

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

- Интуиционистское формальное доказательство.

- Система автоматического или автоматизированного поиска вывода.

- Автоматическое извлечение алгоритма из интуиционистского

формального доказательства.


Лекция 4.


1.5. Формулы как постановки задач программирования.


- Логические конструкции как постановки сложных задач.

- Элементарные конструктивные задачи.


Лекция 5.


2. Математические основы программирования

и функциональный подход


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


Лекция 6. Специализированные языки программирования


Язык спецификаций программ. Язык программирования, ориентированный на дедуктивный синтез алгоритмов.


Лекция 7. Постановки ациклических задач


Примеры постановок задач и решений, не привлекающих рассуждений с полной математической индукцией и другими видами индукции.


Лекция 8. Постановки задач с циклами


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


Лекция 9. Постановки задач с рекурсиями


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


Лекция 10.


3. Синтез полиномиальных программ


В настоящем разделе описывается язык, предназначенный для

дедуктивного синтеза программ полиномиальной временной

сложности.


Лекция 11.


3.1. Язык данных для полиномиального программирования


Язык полиномиального программирования работает с некоторыми из

данных, язык которых определен ниже.


Прежде всего, опишем синтаксис языка данных (далее "дан"

означает "данное", "спис" - "список", справа написаны

комментарии):


дан ::= цифры -- натуральное число

| ( дан , дан ) -- упорядоченная пара

| { спис } -- конечное множество

спис ::= дан | дан , спис

цифры ::= цифра | цифра цифры

цифра ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9


Последовательность цифр может считаться соответствующим

натуральным (целым неотрицательным) числом. Натуральные числа

будем далее обозначать буквами i, j, k, l, m, n.


Считается, что к данным можно применять некоторые заранее

выделенные функции, получая снова натуральные числа (например, к

числам можно было бы применять обычные арифметические операции:

+ (Add, сложение), * (Mult, умножение). В первую очередь нам

понадобится функция Nx (Next, "следующее"): Nx(n)=n+1.


Далее данные будем обозначать строчными латинскими буквами: a,

b. Некоторые натуральные числа в некоторых контекстах будем

рассматривать как коды (номера) сообщений об ошибках. Число

возможных номеров сообщений об ошибках конечно.


Код 0 означает, что ошибки нет. Коды сообщений об ошибках и 0

вместе образуют множество кодов диагностики. Это множество будем

обозначать через Sd (Set of diagnoses).


Данное вида (a,b) считается "парой". С парами можно выполнять

операции .l (left) и .r (right):


(a,b).l=a,

(a,b).r=b.


Считается, что пара (a,b) создается операцией "(,)".


Данное вида {a[1],...,a[n]} считается конечным множеством

(повторения a[i] недопустимы, порядок - несущественен).

Множество {0,1,2,...,n} можно получить из числа a с помощью

"операции создания диапазона" Sr (Set of the range):


Sr(n)={0,1,2,...,n}.


Можно построить "прямую сумму" множеств с помощью операции Sa

(Set addition):


Sa({a[1],...,a[m]},{b[1],...,b[n]}) =

{(0,a[1]),...,(0,a[m]),(1,b[1]),...,(1,b[n])}.


Можно построить "прямое произведение" множеств с помощью

операции Sm (Set multiplication):


Sm({a[1],...,a[m]},{b[1],...,b[n]}) =

{(a[1],b[1]),...,(a[1],b[n]),

...

(a[m],b[1]),...,(a[m],b[n])}.


Данное вида {(a[1],b[1]),...,(a[n],b[n])}, где все a[i]

различны, может считаться таблицей функции (табличной функцикй,

массивом). Например, при применении функции {(0,2),(1,3)} к

аргументу 1 получится значение 3:


{(0,2),(1,3)} ( 1 ) = 3.


Некоторые другие функции над данными будут введены далее.


Лекция 12.


3.2. Переменные и выражения в полиномиальном программировании


Для оперирования с данными будем использовать специальные

"имена" - "переменные" (конечние цепочки строчных латинских

букв). Далее произвольные переменные будем обозначать прописными

латинскими буквами из конца алфавита: X, Y, Z. Буквами E, F, G,

H будем обозначать произвольные выражения, составленные из

переменных, к которым применяются операции над данными,

записанными по излагаемым здесь правилам. Запись вида E[X]

означает выражение, содержащее переменную X. В таком случае E[a]

означает подстановку данного a вместо переменной X.


Операциями "First" и "Second" создания (генерации) первого и

второго вариантов" создаются данные (0,a) и (1,a)

соответственно. К таким данным можно применять операцию разбора

случаев Case-first-second:


Case(X=(0,a))first(E(X))second(F(X)) = E(a),

Case(X=(1,a))first(E(X))second(F(X)) = F(a).


Таблицу функции (массив) можно сгенерировать "операцией

генерации таблицы" Row:


Row(X:{a[1],...,a[n]})val(F(X))

= {(a[1],F(a[1])),...,(a[n],F(a[1]))},


где X - связанная переменная, F(X) - выражение, которое может

содержать переменную X.


Для каждого данного можно ввести понятие "первичной сложности".

Первичная сложность данного измеряется натуральным числом. Один

из вариантов определения первичной сложности - следующий. Для

определения первичной сложности данного все записи чисел в нем

переводятся в "единичную" (монадическую) систему счисления:

число n записывается в виде n единиц. Первичной сложностью

данного считается длина (число позиций символов) получившейся

таким образом цепочки. Например, данное


{(0,2),(1,3)}


преобразуется в цепочку длиной в 15 символов:


{(,11),(1,111)}.


Следовательно, сложность этого данного - 15.


Далее будем считать, что в языке есть константа Cd, обозначающая

некоторую верхнюю границу сложности кодов диагностики. Имеются

также операции Cr, Cm, Ca, Cu со следующим смыслом:


- Cr(a) верхняя граница первичной сложности элементов множества

Sr(a),


- Cm({a[1],...,a[n]},b) - "умножение множества на сложность" -

верхняя граница первичной сложности табличной функции


{(a[1],b[1]),...,(a[n],b[n])},


если b - верхняя граница первичной сложности b[i] при i=1,...,n.


- Ca(a,b) - "сложение сложностей" - верхняя граница первичной

сложности пары (c,d), если a - верхняя граница первичной

сложности c, а b - верхняя граница первичной сложности d,


- Cu(а,b) - "объединение сложностей" - верхняя граница первичной

сложности (0,c) и (1,d), если a - верхняя граница первичной

сложности c, а b - верхняя граница первичной сложности d.


Для обозначения циклического выполнения каких-либо вычислений

будем использовать операцию ограниченного цикла For-do,

которая вырабатывает табличное значение, определяемое следующим

равенством:


For(X,Y:F[x]:=G;H[X,Y])to(n) = Y[n]


где X,Y - связанные переменные, E и G - выражения, не содержащие

переменные X и Y, F[X] - выражение, не содержащее переменную Y,

H[X,Y] - выражение, a значения Y[i] вычисляются следующим

образом:


Y[0] = G,

Y[1] = H[0,Y[0]],

...

Y[i+1] = H[i,Y[i]],

...

Y[n] = H[n-1,Y[n-1]].


При этом требуется, чтобы первичная сложность значения Y[i] не

превосходила значения F[i] при i=0,1,...,n (иначе выполнение

этого цикла приводит к ошибке). В сущности, эта операция -

обобщение операции ограниченной рекурсии (по А.Гжегорчику [4]).

1   2   3

Падобныя:

Рабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная iconПрограмма по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения
Эвм, вычислительной геометрии. Основным содержанием дисциплины является исследования и оценка сложности геометрических построений,...

Рабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная iconРабочая учебная программа по дисциплине «Литература Швейцарии» для специальности «050303- иностранный язык» по циклу опд. В2 дисциплины по выбору Очная форма обучения
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Рабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная iconПрограмма курса для студентов специальности 1-31 01 01-02 математика 1-31 03 03-02 прикладная математика
Автор: Касперко М. В., старший преподаватель кафедры алгебры, геометрии и методики преподавания математики ГрГУ

Рабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная iconРабочая программа по дисциплине "Дерматовенерология" для специальности «Кожные и венерические болезни» 350500 Социальная работа
Рабочая программа составлена с учетом требований Государственного образовательного стандарта высшего профессионального образования...

Рабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная iconПрограмма дисциплины Русский язык и культура речи для направления 010400. 62 «Прикладная математика и информатика»
Государственное образовательное бюджетное учреждение высшего профессионального образования

Рабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная iconРабочая учебная программа по дисциплине «Концепции современного естествознания» для студентов факультета клинической психологии для специальности 030302 «Клиническая психология» Кафедра философии, биомедицинской этики и гуманитарных наук
Рабочая программа составлена в соответствии с требованиями Государственного образовательного стандарта профессиональной подготовки...

Рабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная iconГрафик проведения встреч со студентами университета первого года обучения
Студенты направлений подготовки 140800 «Ядерные физика и технологии», 011200 «Физика», 223200 «Техническая физика», 010400 «Прикладная...

Рабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная iconРабочая программа дисциплины: " математика и архитектура" для специальности
Государственное образовательное учереждение среднего профессионального оброзования

Рабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная iconРабочая программа составлена на основе типовой учебной программы для высших учебных заведений по специальности 1-31 03 01 "Математика (по направлениям)", утверждённой 29. 12. 2008 г. Рег.№ Тд g. 161 / тип
Рабочая программа составлена на основе типовой учебной программы для высших учебных заведений по специальности 1-31 03 01 “Математика...

Рабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная iconРабочая программа составлена на основе типовой учебной программы для высших учебных заведений по специальности 1-31 03 01 "Математика (по направлениям)", утверждённой 29. 12. 2008 г. Рег.№ Тд g. 161 / тип
Рабочая программа составлена на основе типовой учебной программы для высших учебных заведений по специальности 1-31 03 01 “Математика...

Размесціце кнопку на сваім сайце:
be.convdocs.org


База данных защищена авторским правом ©be.convdocs.org 2012
звярнуцца да адміністрацыі
be.convdocs.org
Галоўная старонка