Билет 27.

1. Рекурсивные функции. Лямбда- исчисление Черча.

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

Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции.

int a()

{.....a().....}

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

Например:

a(){.....b().....} b(){.....c().....} c(){.....a().....} .

Все функции a,b,c являются рекурсивными, так как при вызове одной из них, осуществляется вызов других и самой себя.

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

Программа на языке, использующем концепцию лямбда-исчисления, выглядит как композиция конечного набора функций, каждая из которых, в свою очередь, может быть композицией ещё более элементарных функций, и т.д. При этом каждая функция может прямо или косвенно осуществлять рекурсию, т.е. вызов самой себя. Данная модель лишена недостатков машин Тьюринга, описанных выше, в силу своей структуры, изначально требующей определения функций, значения которых зависят исключительно от аргументов функции и не зависят от контекста вызова и выполнения.

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

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

Как правило, рассматривают так называемое "расширенное лямбда-исчисление". Его грамматику можно описать следующим образом:

Выражение ::= Простое выражение | Составное выражение

Простое выражение ::= Константа | Имя

Составное выражение ::= -абстракция | Применение | Квалифицирванное выражение | Ветвление

Лямбда-абстракция ::= lambda Имя -> Выражение end

Применение ::= ( Выражение Выражение )

Квалифицированное выражение ::= let ( Имя = Выражение ; )* in Выражение end

Ветвление ::= if Выражение then Выражение (elseif Выражение then Выражение)* else Выражение end

Константами в расширенном лямбда-исчислении могут быть числа, кортежи, списки, имена предопределенных функций, и так далее.

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

Результатом применения лямбда-абстракции к аргументу будет подстановка аргумента в выражение - "тело" лямбда-абстракции. Сами лямбда-абстракции так же являются выражениями, и, следовательно, могут быть аргументами.

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

Функциональное программирование обладает следующими двумя примечательными свойствами:

1) Аппликативность: программа есть выражение, составленное из применения функций к аргументам. 2) Настраиваемость: так как не только программа, но и любой программный объект (в идеале) является выражением, можно легко порождать новые программные объекты по образцу, как значения соответствующих выражений (применение порождающей функции к параметрам образца).

2. Обеспечивающие системы САПР.

Система автоматизированного проектирования (САПР) – это совокупность средств и методов для осуществления автоматизированного проектирования.

В САПР вводятся следующие виды обеспечения объектов проектирования:

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

Средства программной обработки данных представлены процессорами и запоминающими устройствами, т.е. устройствами ЭВМ, в которых реализуются преобразования данных и программное управление вычислениями. Средства подготовки, ввода, отображения и документирования данных служат для общения человека с ЭВМ. Средства архива проектных решений представлены внешними запоминающими устройствами. Средства передачи данных используются для организации связей между территориально разнесенными ЭВМ и терминалами (оконечными пунктами).

Математическое обеспечение включает в себя математические модели (ММ) проектируемых объектов, методы и алгоритмы проектных процедур, используемые при автоматизированном проектировании. Элементы математического проектирования САПР чрезвычайно разнообразны. К ним относятся принципы построения функциональных моделей, методы численного решения алгебраических и дифференциальных уравнений, постановки экстремальных задач, поиска экстремума и т.д.

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

- обеспечивать экономичность использования ресурсов ЭВМ (памяти и времени процессора), т.е. быть эффективными;

- обладать надежностью;

- обладать структурностью и модульностью, которые заключаются в том, что сложная задача может быть разделена на более простые, каждой из которых соответствует определенный программный модуль;

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

- допускать переносимость на новые виды вычислительной техники и технологических задач;

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

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

Информационное обеспечение объединяет всевозможные данные, необходимые для выполнения автоматизированного проектирования. Эти данные могут быть представлены в виде тех или иных документов на различных носителях, содержащих сведения справочного характера о материалах, комплектующих изделиях, типовых проектных решениях, параметрах элементов, сведения о состоянии текущих разработок в виде промежуточных и окончательных проектных решений, структур и параметров проектируемых объектов и т.п. Основная часть информационного обеспечения САПР − банк данных, представляющий собой совокупность средств для централизованного накопления и коллективного использования данных в САПР. Банк данных (БНД) состоит из базы данных и системы управления базой данных.

База данных (БД) − сами данные, находящиеся в запоминающих устройствах ЭВМ и структурированные в соответствии с принятыми в данной БД правилами.

Система управления базой данных (СУБД) − совокупность программных средств, обеспечивающих функционирование БД. С помощью СУБД производятся запись данных в БД, их выборка по запросам пользователей и прикладных программ, обеспечивается защита данных от искажений, несанкционированного доступа и т.п.

Лингвистическое обеспечение представлено совокупностью языков, применяемых для описания процедур автоматизированного проектирования и проектных решений. Языки, которые используются в вычислительной технике, являются алгоритмическими. Они служат для задания определенных алгоритмов переработки информации и построены посредством набора символов и системы правил соответствующего языка. В САПР применяют языки программирования и языки общения человека с ЭВМ. С помощью языков программирования составляются программы, входящие в состав общесистемного или прикладного ПО. Эти языки подразделяют на языки низкого и высокого уровней.

Методическое обеспечение составляют документы, характеризующие состав, правила выбора и эксплуатации средств автоматизированного проектирования.

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

3. Написать программу на языке С++ для реверса списка. Например: [1,2,3] [3,2,1].

#include <iostream.h>

void main()

{

int X[10],Y[10],N,j=1,i;

cout<<"\n Vvedite N (<10) ==";

cin>>N;

for(i=1;i<=N;i++)

{

cout<<"\n X["<<i<<"] ==";

cin>>X[i];

}

for(i=N;i>0;i--)

{

Y[j]=X[i];

j++;

}

for(i=1;i<=N;i++)

{

cout<<"\n X["<<i<<"] == "<<Y[i];

}

_getch();

}