Файл: ответы.doc

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

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

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

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

Лямбда-абстракция ::= 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();

}

Билет 28.

1. Память. Типы адресов. Виды распределения памяти.

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

Типы адресов. Для идентификации переменных и команд используются символьные имена (метки), виртуальные адреса и физические адреса.

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

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

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

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

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

Распределение памяти фиксированными разделами

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

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