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

Ответ: 192.168.0.47

Билет 31

1. Синтаксический разбор. Классификация методов синтаксического разбора.

Задачей синтаксического анализа считается проверка, принадлежит ли произвольная заданная цепочка   T ^* языку L(G) для заданной грамматики G. На основе методов синтаксического анализа решаются задачи синтаксически управляемой обработки данных (например, текстов). Такой задачей является и задача трансляции. Регулярные языки и порождающие их А-грамматики используются, в основном, для лексического анализа  распознавания в тексте его лексических единиц, лексем, т.е. слов, из которых по более сложным правилам строится текст. 

Синтаксический разбор — это основная часть компилятора на этапе анализа. Она выполняет выделение синтаксических конструкций в тексте исходной програм­мы, обработанном лексическим анализатором. На этой же фазе компиляции проверяется синтаксическая правильность программы Синтаксический разбор играет главную роль — роль распознавателя текста входного языка.

Методы (классификация) синтаксического разбора (в основном два способа):

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

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

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

На самом деле в реальных компиляторах редко используются те или иные методы разбора в чистом виде. Обычно используются комбинации известных методов, или же несколько изменённые методы разбора, в основном с целью повышения скорости разбора. Однако, последнее десятилетие из-за повышения при компиляции программ удельной массы проходов оптимизации, время синтаксического разбора занимает небольшой процент общего времени компиляции, потому нет особого смысла заниматься оптимизацией разбора сверх меры. Частично в ряде случаев используются автоматизированные среды для постороения лексических и синтаксических анализаторов: lex, yacc, bison. Так, в версии GCC 3.3 для синтаксического разбора используется bison, но в последнее время разработки пытаются написать проход синтаксического анализа не использующий bison для повышения скорости синтаксического разбора.

2. Интеграция систем автоматизации проектирования и управления(CAD – CAM – CAPP – системы).

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

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

• САПР изделий (САПР И);

• САПР технологических процессов (САПР ТП) их изготовления.

САПР изделий. На Западе эти системы называют CAD (Computer Aided Design) – «проектирование с помощью компьютера» - фактически этот термин означает системы геометрического моделирования и САПР чертежно-конструкторских работ. Эти системы выполняют объемное и плоское геометрическое моделирование, инженерные расчеты и анализ, оценку проектных решений, изготовление чертежей.

САПР технологии изготовления. В России эти системы принято называть САПР ТП или АС ТППП (автоматизированные системы технологической подготовки производства). На Западе их называют CAPP (Computer Automated Process Planning). Здесь Automated – автоматический, Process – процесс, Planning – планировать, планирование, составление плана. С помощью этих систем разрабатывают технологические процессы и оформляют их в виде маршрутных, операционных, маршрутно-операционных карт, проектируют технологическую оснастку, разрабатывают управляющие программы (УП) для станков с ЧПУ (числовое программное управление).

Более конкретное описание технологии обработки на оборудовании с ЧПУ (в виде кадров управляющей программы) вводится в автоматизированную систему управления производственным оборудованием (АСУПР), которую на Западе принято называть CAM (Computer Aided Manufacturing) - “производство с помощью компьютера”. Техническими средствами, реализующими данную систему, могут быть системы ЧПУ станков, компьютеры, управляющие автоматизированными станочными системами.

Самостоятельное использование систем CAD, CAM дает экономический эффект. Но он может быть существенно увеличен их интеграцией посредством CAPP. Такаяинтегрированная система CAD/CAM на информационном уровне поддерживается единой базой данных. В ней хранится информация о структуре и геометрии изделия (как результат проектирования в системе CAD), о технологии изготовления (как результат работы системы CAPP) и управляющие программы для оборудования с ЧПУ (как исходная информация для обработки в системе CAM на оборудовании с ЧПУ) – рис.4.1.

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

Билет 32

1. Понятие алгоритма. Интуитивное понятие алгоритма.

Слово алгоритм возникло от algorithm- латинской транслитерации имени великого математика IX века Мохаммеда ибн Муссы аль-Хорезми, который сформулировал правила выполнения четырех арифметических действий над многозначными числами.

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

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

Алгоритм – понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение цели.

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

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

В 30 годы ХХ века в противовес классическим представлениям Альхарезми,  возникла гипотеза об алгоритмически неразрешимости нескольких задач.

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

Можно ввести математическую абстракцию:

Пусть Х – совокупность входных данных, Y – совокупность выходных данных.

Y=f(X)

В) Черча. λ – исчисление или ввел понятие систем рекурсивно-вычислимых (РВ) функций. В этой системе было выделено 3 базовых функции и 3 оператора, посредством которых мы из базовых РВ функций строим более сложные РВ функции.

Алгоритм – способ определения РВ функции.

С) Алaна Тьюринга. Он предложил модель гипотетического вычислительного устройства (исполнителя). Алгоритм – программа для этого исполнителя.

D) Маркова. Основан на том, что какие бы ни были входные данные, они описываются определённым языком.

ВХОД – строка

ВЫХОД – строка

Алгоритм – набор правил подстановки одних символов  вместо других.

Был также обоснован тезис Черча – Тьюринга. Различные подходы к формализации понятия алгоритма эквивалентны между собой с точки зрения понятия алгоритмической неразрешимости. С этой точки зрения, любой компьютер с Фон-неймановской архитектурой или другой ныне известной архитектурой, позволяет реализовать только те алгоритмы, которые можно реализовать на машине Тьюринга.

Свойства алгоритма:

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

Дискретность - алгоритм состоит из ряда дискретных шагов.

Определенность - каждый следующий шаг алгоритма однозначно определяется предыдущими шагами.

Результативность - алгоритм должен приводить к решению поставленной задачи за конечное число шагов

Понятность – алгоритм рассчитан на исполнителя, и должен быть сформулирован на понятном ему языке (СКИ – система команд исполнителя).

Каждый исполнитель алгоритма имеет свою систему команд (набор действий) и свою среду (набор объектов, над которыми совершаются действия), в которой, и только в ней, он работает.

Виды алгоритма:

Линейный - алгоритм, в котором все предписания (шаги) выполняются так, как записаны, без изменения порядка следования, строго друг за другом.

Разветвляющийся - алгоритм, в котором выполнение того или иного действия (шага) зависит от выполнения или не выполнения какого-либо условия.

Циклический - алгоритм, в котором некоторая последовательность действий повторяется несколько раз.

Способы записи алгоритма:

Словесно-формульное описание (на естественном языке с использованием математических формул).

Графическое описание в виде блок-схемы (набор связанных между собой геометрических фигур).

алгоритмический язык – система обозначений и правил для единообразной и точной записи алгоритмов и исполнения их.

Разработка алгоритмов.

Существует два подхода к разработке алгоритмов: операциональный и структурный.

Операциональный:

·                   минимум памяти;

·                   минимум операций.

операции:

·              присваивание;

·              арифметические;

·              сравнение;

·              условный и безусловный переход;

·              вызов подпрограммы.

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

2. Объекты и отношения в программировании. Сущность объектного подхода к разработке программных средств. Особенности объектного подхода к разработке внешнего описания программного средства.

Окружающий нас мир состоит из объектов и отношений между ними. Объект воплощает некоторую сущность и имеет некоторое состояние, которое может изменяться со временем как следствие влияния других объектов, находящихся с данным в каком-либо отношении. Он может иметь внутреннюю структуру: состоять из других объектов, также находящихся между собой в некоторых отношениях. Исходя из этого, можно построить иерархическое строение мира из объектов. Однако при каждом конкретном рассмотрении окружающего нас мира некоторые объекты считаются неделимыми ("точечными"), причем в зависимости от целей рассмотрения такими (неделимыми) могут приниматься объекты разного уровня иерархии. Отношение связывает некоторые объекты: можно считать, что объединение этих объектов обладает некоторым свойством. Если отношение связывает n объектов, то такое отношение называется n-местным (n-арным). На каждом месте объединения объектов, которые могут быть связаны каким-либо конкретным отношением, могут находиться разные объекты, но вполне определенные (в этом случае говорят: объекты определенного класса). Одноместное отношение называется свойством объекта (соответствующего класса). Состояние объекта может быть изучено по значению свойств этого объекта или неявно по значению свойств объединений объектов, связываемых вместе с данным тем или иным отношением.

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