Основы Pascal. Типы данных. Структура программы на языке Pascal

Вид материала

Документы

Содержание Вычислительная машина Многомашинные и многопроцессорные вычислительные системы Вычислительная система называется многопроцессорной Программирование искусственного интеллекта. Особенности языка LISP/Scheme. Логическое программирование. Язык Prolog.

Подобный материал:

• Компоновать программы из отдельных частей отлаживать программы выполнять программы., 197.76kb.
• Borland Turbo Pascal, знать простые основные алгоритмы работы с простыми типами данных, 316.19kb.
• Программирование на языке высокого уровня, 59.92kb.
• Задачи работы Научиться создавать программы на языке Turbo Pascal с использованием, 598.05kb.
• Курс «Программирование на языке Turbo Pascal 0» Цель курса, 19.6kb.
• Borland Turbo Pascal, знать простые основные алгоритмы работы с простыми типами данных, 324.26kb.
• Правила преобразований из одного типа в другой и правила приведения типов в языке Object, 19.03kb.
• Информатика Ответы на вопросы, 913.15kb.
• Конспект урока по информатике для десятого класса по теме «Условный оператор в Turbo, 32.44kb.
• Доманская Юлия Георгиевна г. Вилейка 2006г пояснительная записка, 74.95kb.

Понятие «Вычислительная система», многомашинные и многопроцессорные вычислительные системы.

Вычислительная машина – это комплекс технических и программных средств, предназначенных для автоматизации подготовки и решения задач пользователя.

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

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

Очевидно, что различия между вычислительными машинами и вычислительными системами не могут быть точно определены (вычислительные машины даже с одним процессором обладает разными средствами распараллеливания, а вычислительные системы могут состоять из традиционных вычислительных машин или процессоров.

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

Многомашинные и многопроцессорные вычислительные системы

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

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

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



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

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

Под общим полем понимается равнодоступность устройств. Так, общее поле памяти означает, что все модули ОП доступны всем процессорам и каналам ввода-вывода (или всем периферийным устройствам в случае наличия общего интерфейса); общее поле ВЗУ означает, что образующие его устройства доступны любому процессору и каналу.

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

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

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

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

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

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

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

Используются следующие способы организации межмодульных (межустройственных) связей:

- регулярные связи между модулями;

- многоуровневые связи, соответствующие иерархии интерфейсов ЭВМ;

- многовходовые модули (в частности, модули памяти);

- коммутатор межмодульных связей (“Эльбрус” Рис62);

общая шина (“СМ ЭВМ” Рис.6.3).

Принципы организации МПС и ММС существенно отличаются в зависимости от их назначения. Поэтому целесообразно различать:

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

- ВС, ориентированные в первую очередь на повышение надежности и живучести.

48. Программирование искусственного интеллекта.
    

(возможно не то! Но эт единственное что подходит из их инфы)

Функциональное программирование. Язык Scheme/LISP.

Концепции и особенности функционального программирования.

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

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

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

Особенности языка LISP/Scheme.

Синтаксическими элементами языка LISP являются символьные выражения, которые также называют s-выражениями. В виде s-выражений представляются и программы, и данные. S-выражение может быть атомом или списком. Атомы — это базовые синтаксические единицы языка, включающие числа и символы. Список — это последовательность атомов или других списков, разделенных пробелами и заключенных в круглые скобки. Глубина вложенности списков друг в друга может быть любой, что позволяет создавать символьные структуры любой формы и сложности. Вызовы функций в языке LISP записываются в виде списка в префиксной форме, называемой польской записью, а именно: (<функция> <аргумент1> <аргумент2> … <аргументN>)

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

Для предотвращения оценивания символа или списка используется специальная функция quote. Это функция зависит от одного аргумента и возвращает его без оценки. Функция quote используется для того, чтобы аргументы обрабатывались как данные, а не как оцениваемые выражения. Допускается сокращенное обозначение функции в виде символа ' (одинарной кавычки) непосредственно перед аргументом.

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

Язык Scheme: функции для работы со списками, предикатные функции.

Поскольку основной структурой данных в языке LISP/Scheme являются списки, язык включает различные функции для работы с ними. В частности, имеются функции для создания списков, выбора их частей и манипулирования ими. Для выбора элементов из списка в языке LISP/Scheme могут использоваться функции car и cdr (произносится как «куд-ер»). Функция car возвращает первый элемент заданного списка (называемый «головой» списка), а функция cdr — список (называемый «хвостом»), получаемый из заданного списка после удаления его первого элемента. С функциями car и cdr в языке LISP/Scheme связано понятие «пара» («точечная пара»). «Пара» представляет собой двухэлементную структуру, первый элемент которой (car-поле или «голова») возвращается функцией car, а второй (cdr-поле или «хвост») функцией cdr.

Для конструирования списка может использоваться двухаргументная функция cons. Она создает «пару», «голова» которой представляет собой первый параметр, а «хвост» соответствует второму аргументу. Для формирования с помощью функции cons списка элементов необходимо, чтобы её вторым параметром был какой-либо список. Функция list создает список, элементами которого являются переданные ей параметры, число которых может быть произвольным. Функция length возвращает количество элементов списка.

Предикат — это функция, возвращающая логическое значение («истина» или «ложь») в зависимости от того, удовлетворяют ли её параметры некоторому условию или свойству. В языке Scheme значение «истина» обозначается как #t, а «ложь» как #f. К предикатным функциям для числовых данных в языке Scheme относятся: = (равно), <> (не равно), > (больше), < (меньше), >= (больше или равно), <= (меньше или равно), even? (четное ли число), odd? (нечетное ли число), zero? (равно ли число нулю). Функция eq? позволяет проверить, эквиваленты ли между собой два символьных параметра. Результат применения функции к аргументам других типов (например, числам или спискам) зависит от реализации языка Scheme. Если неизвестно, являются ли атомы символьными или числовыми, то проверить их на равенство можно с помощью предиката eqv?. Однако предпочтительнее по возможности использовать функции eq? и =, поскольку они работают быстрее. Определить, эквивалентны ли два параметра, каждый из которых может являться атомом или списком, позволяет предикат equal?. Предикат list? позволяет проверить, является ли её параметр списком. Функция null? возвращает #t, если её параметр представляет собой пустой список. Предикат pair? проверяет, является ли её аргумент «парой». Функции number? и symbol? позволяют определить, представляет ли их аргумент собой соответственно числовой или символьный атом.

Язык Scheme: функции для определения новых функций и организации разветвляющегося вычислительного процесса.

Для определения новых функций в языке LISP/Scheme используется система лямбда-обозначений в виде списка, который имеет следующий общий синтаксис: (lambda <параметры> <тело>), где <параметры> — имена одного или нескольких формальных параметров функции (лямбда-выражения), <тело> — набор s-выражений, представляющих тело функции, результат вычисления последнего из которых определяет результат применения функции. Формальные параметры могут быть заданы в виде одного символьного атома или их списка. Если определение лямбда-выражения содержит один формальный параметр, то это означает, что соответствующая функция может иметь любое количество фактических параметров, однако при вызове функции они преобразуются в список, который связывается с указанным аргументом. Если определение функции включает список параметров, то при её вызове должно быть передано указанное число аргументов, которые связываются с соответствующими формальными параметрами. Связанные с формальными параметрами значения не изменяются в процессе вычисления функции, что отличает их от параметров подпрограмм в императивных языках программирования. Лямбда-выражение определяет безымянную функцию, которая может применяться так же, как именованная функция.

Для определения именованной функции в языке Scheme используется функция define. В простейшей форме она позволяет связать s-выражение с именем и имеет следующий общий синтаксис: (define <имя> <выражение>), где <имя> — название новой функции, <выражение> — s-выражение, связываемое с данной функцией, результат вычисления которого определяет её значение. Определение именованной функции с параметрами задается с помощью функции define следующим образом: (define (<имя> <параметры>) <тело>), где <параметры> — набор разделенных пробелами имен формальных параметров, <тело> — набор s-выражений, представляющих тело функции, результат вычисления последнего из которых определяет результат применения функции.

Для организации ветвления вычислений в языке LISP/Scheme можно использовать функции if и cond. Работа этих функций зависит от значений соответствующих условий. В языке Scheme только значение #f рассматривается условными функциями как «ложь». Функция if имеет следующий вид:

(if <условие> <выражение> [<альтернатива>])

Общий синтаксис функции cond приведен ниже:

(cond

(<условие1> <выражение> {<выражение>})

(<условие2> <выражение> {<выражение>})

...

(<условиеN> <выражение> {<выражение>})

[(else <выражение> {<выражение>})]

)

Логическое программирование. Язык Prolog.

Концепции и особенности логического программирования. Резолюция.

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

Логическое программирование основывается на логическом выводе и доказательстве теорем, которые позволяет осуществлять исчисление предикатов. Одним из используемых для этого методов является резолюция — правило логического вывода, позволяющее получать одни высказывания из других. Для использования принципа резолюции логические высказывания должны быть приведены к дизъюнктивной форме, имеющей следующий общий вид: A₁ÙA₂Ù…ÙA_m®B₁ÚB₂Ú…ÚB_n или, сокращенно, A®B, где A_i и B_j — термы. Ограниченный вид дизъюнктивных форм, называемый хорновскими дизъюнктами или дизъюнктами Хорна, позволяет упростить процесс логического вывода на основе резолюции. В хорновском дизъюнкте заключение либо отсутствует (дизъюнкт без головы), либо содержит единственный терм (дизъюнкт с головой).

Концепция резолюции заключается в следующем. Предположим, что заданы два следующих высказывания: A®B и B®C. Логически из этого следует, что A®C. Процесс вывода этого высказывания представляет собой резолюцию и в упрощенном виде выглядит следующим образом. Образуется новое высказывание, левая часть которого есть конъюнкция левых частей исходных высказываний, а правая часть — конъюнкция их правых частей, т.е. (AÙB)®(BÙC). Затем термы, появляющиеся в обеих частях нового высказывания, удаляются из него, в результате чего получается выводимое высказывание. Наличие переменных в высказываниях приводит к необходимости выполнять в процессе резолюции поиск их значений, позволяющих установить соответствие между термами. Алгоритм определения необходимых подстановок значений переменных с целью приведения в соответствие двух выражений исчисления предикатов называется унификацией. Временное присваивание значений переменным с целью унификации называется конкретизацией. Обычно во время резолюции переменная конкретизируется неким значением, не полностью удовлетворяющим требуемому соответствию. В этом случае надо конкретизировать эту переменную новым значением. Процесс возврата к предыдущему состоянию называется бектрекингом (backtracking).

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