Математический анализ в Maple

         

Математический анализ в Maple

Важным разделом математики является исследование аналитических функций. Оно обычно заключается в определении координат особых точек функции и ее значений в этих точках, а также в выяснении особенностей функции, таких как наличие точек разрыва, асимптот, точек перегибов, разрывов и т. д. К сожалению, пока нет средств, сразу выявляющих все особенности функций, поскольку даже средства, решающие частные задачи анализа функций, довольно сложны и специфичны. Достаточно отметить проблему поиска экстремумов функций (особенно функций нескольких переменных). Поэтому функции приходится анализировать индивидуально.
С помощью функции fsolve легко находятся значения независимой переменной х функций вида f(x), при которых f(x)=0 (корни этого уравнения). При этом данная функция позволяет (в отличие от функции solve) изолировать корни функции f(x) указанием примерного интервала их существования. Ряд функций служит для вычисления экстремумов, максимумов и минимумов функций, а также для определения их непрерывности. Одна из таких функций, extrema, позволяет найти экстремумы выражения ехрr (как максимумы, так и минимумы) при ограничениях constcs и переменных vans, по которым ищется экстремум: extrema(expr. constrs) extrema(expr, constrs, vars) extrematexpr, constrs, vans, V)
Ограничения contrs и переменные vars могут задаваться одиночными объектами или списками ряда ограничений и переменных. Найденные координаты точки экстремума присваиваются переменной 's'. При отсутствии ограничений в виде равенств или неравенств вместо них записывается пустой список {}. Эта функция в предшествующих версиях Maple находилась в стандартной библиотеке и вызывалась командой readlib(extrema). Но в Maple 7 ее можно использовать без предварительного объявления.

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

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

Основные операции с выражениями
Выражения (ехрr) или уравнения (eqn) обычно используются как сами по себе, так и в виде равенств или неравенств. В последнем случае объекты с выражениями имеют левую и правую части.

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

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

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

Феномен науки. Кибернетический подход к эволюции

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

Основной закон эволюции
Кибернетический подход Турчина развивается сегодня международным коллективом ученых в рамках Интернет-проекта Principia Cybernetica4, цель которого — выработка кибернетического взгляда на все явления вплоть до вопросов о смысле жизни и “Что есть Бог?”.

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

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

Разговор с электрическим мозгом
Поверьте мне, все произошло совершенно неожиданно, а может быть, даже случайно. Я давно хотел поехать на Новомосковский химический комбинат. Расположен он недалеко от столицы и пользуется доброй славой. И вдруг сверхсрочная командировка: напишите о кибернетике на комбинате... И я поехал знакомиться с автоматизацией на предприятии. Завод поразил меня.

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

Кибернетика и общество
После второй мировой войны я работал над многими разделами теории сообщения (the theory of messages). Помимо электротехнической теории передачи сигналов, существует более обширная область, включающая в себя не только исследование языка, но и исследование сигналов (messages) как средств, управляющих машинами и обществом; сюда же относятся усовершенствование вычислительных машин и других подобных автоматов, размышления о психологии и нервной системе и сравнительно новая теория научного метода.

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

Кибернетический манифест
Философия отвечает на такие фундаментальные вопросы, как: “Кто я?”, “Откуда я пришел и куда иду?”, “Сколь истинно мое знание?”, “Какова, в конечном счете, природа вещей?”, “Что есть добро и что есть зло?”. Философия важна. Философия является частью нашего знания.

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

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

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

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

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

Синергетика 2, Cинергетика 3 или Эволюционная кибернетика
Слово "эволюция" - одно из наиболее часто встречающихся на данной Web-странице. Например, в статье Э.Ласло предполагается использовать понятие эволюции в качестве основного для трансдисциплинарной унификации наук. Однако в обсуждаемых на данной странице синергетических исследованиях остается где-то на периферии рассмотрения чрезвычайно интересная и актуальная область эволюционных исследований - анализ эволюции биологических информационных систем и обеспечиваемых этими системами кибернетических свойств биологических организмов.

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

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

Кибернетика и человек
Каково ваше мнение относительно возможности развития математики при помощи машин? Можем ли мы ожидать, что таким путем будут открыты новые теоремы или созданы новые доказательства уже существующих?

Теория и практика параллельных вычислений

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

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

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

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

Алгоритмы маршрутизации
К числу наиболее распространенных оптимальных алгоритмов относится класс методов покоординатной маршрутизации (dimension-ordered routing), в которых поиск путей передачи данных осуществляется поочередно для каждой размерности топологии сети коммуникации.

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

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

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

Постановка задачи
При умножении квадратных матриц размера n?n количество выполненных операций имеет порядок O(n3). Известны последовательные алгоритмы умножения матриц, обладающие меньшей вычислительной сложностью (например, алгоритм Страссена (Strassen’s algorithm)), но эти алгоритмы требуют больших усилий для их освоения, и поэтому в данной лекции при разработке параллельных методов в качестве основы будет использоваться приведенный выше последовательный алгоритм.

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

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

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

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

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

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

В книге представлены "классические" разделы теории разработки компиляторов: лексический и синтаксический анализ, организация памяти компилятора (таблицы символов) и периода исполнения (магазина), генерация кода. Рассматриваются такие средства автоматизации процесса разработки трансляторов, как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую "атрибутную" точку зрения на процесс разработки компилятора.

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

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

Алфавиты, цепочки и языки
Пусть V - алфавит. Цепочка в алфавите V - это любая строка конечной длины, составленная из символов алфавита V . Синонимом цепочки являются предложение, строка и слово. Пустая цепочка (обозначается e) - это цепочка, в которую не входит ни один символ.

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

Контекстно-свободные грамматики и автоматы с магазинной памятью
Упорядоченным графом называется пара (V,E), где V есть множество вершин, а E - множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v, v1), (v, v2), ... , (v, vn)). Этот элемент указывает, что из вершины v выходят n дуг, причем первой из них считается дуга, входящая в вершину v1, второй - дуга, входящая в вершинуv2, и т.д.

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

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

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

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

Генерация кода
Задача генератора кода - построение для программы на входном языке эквивалентной машинной программы. Обычно в качестве входа для генератора кода служит некоторое промежуточное представление программы.

Системы автоматизации построения трансляторов
Системы автоматизации построения трансляторов (САПТ) предназначены для автоматизации процесса разработки трансляторов. Очевидно, что для того, чтобы описать транслятор, необходимо иметь формализм для описания. Этот формализм затем реализуется в виде входного языка САПТ. Как правило, формализмы основаны на атрибутных грамматиках.

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

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

Представление языков
Принадлежит ли цепочка x = abaababb языку, порождаемому грамматикой с правилами: S SaSb|?


Путь камикадзе

Вряд ли можно где-нибудь увидеть объявление о найме для участия в безнадежном проекте. Какой смысл спрашивать: «Хотите ли вы работать сверхурочно без какой-либо прибавки к зарплате? Привлекает ли вас бесконечная работа по устаревшей технологии и тщетное ожидание участия в каком-нибудь замечательном проекте GUI/DSS/DWH/HTML? Каково будет узнать, что трехзвенная архитектура «клиент-сервер» позволит остальным участникам проекта обойтись без вашей помощи?»
На самом деле, безнадежные проекты редко объявляются таковыми во всеуслышание, и вам придется достаточно долго проработать в нанявшей вас компании, прежде чем удастся обнаружить, что она обладает склонностью плодить безнадежные проекты.
Если вашему коллеге приходится руководить безнадежным проектом, то ему можно посоветовать включить в контракт пункт, позволяющий цивилизованным способом выйти из проекта. Одна из серьезных причин выхода - неспособность высшего руководства воспринимать правдивую информацию о проекте. Принимающий на себя руководство безнадежным проектом должен быть готов к тому, что у него будет практически отсутствовать пространство для маневра в отношении функциональности, затрат или времени.

Определение безнадежного проекта
Под безнадежным проектом (death march) я понимаю такой проект, параметры которого отклоняются от нормальных значений по крайней мере на 50%. По отношению к софтверным проектам это обычно означает одно или более из следующих ограничений: План проекта сжат более чем наполовину по сравнению с нормальным расчетным планом; таким образом, проект, требующий в нормальных условиях 12 календарных месяцев, приходится выполнять за 6 или менее месяцев. Жесткая конкуренция на мировом рынке делает такую ситуацию наиболее распространенной.

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

Лекции по управлению программными проектами

Термин software (программное обеспечение, ПО) ввел в 1958 году всемирно известный статистик Джон Тьюкей (John Tukey). Термин software engineering (программная инженерия) впервые появился в названии конференции НАТО, состоявшейся в Германии в 1968 году и посвященной так называемому кризису программного обеспечения. С 1990-го по 1995 год велась работа над международным стандартом, который должен был дать единое представление о процессах разработки программного обеспечения. В результате был выпущен стандарт ISO/IEC 12207 . В 2004 году в отрасли был создан основополагающий труд «Руководство к своду знаний по программной инженерии» (SWEBOK) , в котором были собраны основные теоретические и практические знания, накопленные в этой отрасли.

Модели процесса разработки ПО

Введение в теорию программирования

Важнейшими математическими формализациями, рассматриваемыми в данном курсе, являются ламбда-исчисление и комбинаторная логика.
Еще в 1924 г. М. Шейнфинкель (Moses Schonfinkel) разработал простую (simple) теорию функций, которая фактически являлась исчислением объектов-функций и предвосхитила появление ламбда-исчисления – математической формализации, поддерживающей языки функционального программирования (т.е. программирования в терминах функций).
Затем в 1934 г. А. Черч (Alonso Church) предложил собственно исчисление ламбда-конверсий (или ламбда-исчисление) и применил его для исследования теории множеств. Вклад ученого был фундаментальным, так что теория до сих пор называется ламбда-исчислением и часто именуется в литературе ламбда-исчислением Черча.
Позднее, в 1940 г., Х. Карри (Haskell Curry) создал теорию функций без переменных (иначе называемых комбинаторами), известную в настоящее время как комбинаторная логика. Эта теория является развитием ламбда-исчисления и представляет собой формальный язык, подобный языку функционального программирования.
В 60-х годах Х. Барендрегтом (H. Barendregt) были детально описаны синтаксис (т.е. форма конструкций) и семантика (т.е. значение конструкций) ламбда-исчисления.

Вступительная лекция
Что касается теоретических основ семантики вычислений, то в конце 60-х годов Д. Скотт (Dana S. Scott) предложил применить для формализации семантики математических теорий так называемые домены (пока будем неформально понимать их как особый вид множеств). При этом на основе доменов Д. Скоттом был предложен так называемый денотационный подход к семантике.

Объектно-ориентированный подход к программированию
Рассмотрим особенности объектно-ориентированного подхода к программированию в сравнении с функциональным подходом. Напомним, что классификация подходов к программированию была построена нами во вступительной лекции.

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

Основные понятия языка программирования C#
Прежде чем перейти непосредственно к исследованию конструктивных особенностей языка программирования C#, рассмотрим ход его развития. История основной ветви языков программирования, которая привела к появлению C#, восходит к 60-м годам, а именно, ко времени возникновения языка B. Последний является типичным представителем ранних императивных языков программирования. Язык B был придуман в 1963 году творческим коллективом разработчиков, основным создателем языка принято считать К. Томпсона

Краткая информация о платформе .NET
Платформа .NET Framework предоставляет среду для поддержки создания и выполнения интероперабельных гетерогенных приложений. Основными особенностями данной платформы являются не зависящая от языка среда исполнения (Common Language Runtime, CLR) и библиотека классов .NET.

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

Основные понятия объектно-ориентированного подхода: объекты, классы и методы
В данной лекции будут рассмотрены вопросы, относящиеся к идеологии, методологии и практике моделирования основных элементов объектно-ориентированного подхода к программированию посредством двухуровневой концептуализации. Особенности практической реализации основных аспектов концепции ООП описаны на примере языка программирования C#.

Классы и обьекты
Понятие класса является фундаментальным в ООП и служит основой для создания объектов. В описании класса определяются данные (т.е. переменные) и код (т.е. методы), манипулирующий этими данными. Объекты являются экземплярами класса.

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

Концепция наследования и ее реализация в языке C#
Под наследованием в дальнейшем будем понимать свойство производного объекта сохранять поведение родительского объекта. Под поведением будем иметь в виду для математического объекта его атрибуты и операции над ним, а для языкового объекта ООП - поля и методы.

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

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

Расширенные возможности полиморфизма в языке C#
Проиллюстрируем особенности использования абстрактных свойств и методов следующим фрагментом программы на языке C#: abstract class Sequence { public abstract void Add(object x); // метод public abstract string Name{ get; } // свойство public abstract object this [int i] { get; set; } // индексатор }

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

Обработка событий
Под событием будем понимать автоматическое извещение о каком-либо действии среды программирования или пользователя. События являются членами класса и объявляются с использованием ключевого слова event. Реализация механизма событий в языке программирования C# основана на использовании делегатов.

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

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

Математическая теория формальных языков

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основы теории нечетких множеств

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

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

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

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

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

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

Прямые методы для одного эксперта
Прямые методы для одного эксперта состоят в непосредственном задании функции, позволяющей вычислять значения. Например, пусть переменная "ВОЗРАСТ" принимает значения из интервала . Слово "МОЛОДОЙ" можно интерпретировать как имя нечеткого подмножества , которое характеризуется функцией совместимости.

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

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

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

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

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

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

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

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

Нейрокомпьютинг и его применения в экономике и бизнесе

Наш опыт свидетельствует, что главным препятствием к широкому практическому применению нейрокомпьютинга служит недостаточное понимание его основ. Эта книга писалась с целью восполнить этот пробел. Поэтому основное внимание здесь уделяется описанию принципов нейросетевой обработки данных, их потенциальных возможностей и преимуществ, а также подробному разбору нескольких конкретных применений. Упор делается на концептуальной стороне дела, а не на описании конкретных алгоритмов. Предполагается, что в случае необходимости читатель сможет воспользоваться одним из многочисленных коммерческих нейро-эмуляторов, а не возьмется программировать нейросети "с нуля" на С++. Главная задача книги - научить читателя "видеть" нейросетевые постановки задач в его повседневной работе, помочь ему автоматизировать рутинную обработку сложной многофакторной информации с помощью современного математического аппарата - искусственных нейронных сетей.
Хотя мы старались избегать математических выкладок и, по возможности, упростить изложение, хотелось бы заранее предупредить, что материал этой книги рассчитан на достаточно подготовленного читателя - как минимум студента старших курсов. Наш "идеальный" читатель - студент, научный работник, финансовый аналитик, консультант, брокер или просто бизнесмен, желающий повысить эффективность своего бизнеса путем более вдумчивой работы с доступной ему информацией.

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

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

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

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

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

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

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

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

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

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

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