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


         

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

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

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

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

Структура компилятора
Структура компилятора - 2

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

Представление языков
Формальное определение грамматики
Формальное определение грамматики - 2
Типы грамматик и их свойства
Машины Тьюринга
Неразрешимость проблемы останова
Класс рекурсивных множеств
Класс рекурсивных множеств - 2
Связь машин Тьюринга и грамматик типа 0
Связь машин Тьюринга и грамматик типа 0 - 2

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

Лексический анализ
Лексический анализ - 2
Регулярные множества и выражения
Регулярные множества и выражения - 2
Конечные автоматы
Конечные автоматы - 2
Построение автомата по регулярному выражению
Построение автомата по недетерминированному
Построение детерминированного автомата
Автомат с минимальным числом состояний

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

LR(1)-грамматики
LR(1)-грамматики - 2
LR(1)-грамматики - 3
Восстановление процесса после ошибок
Варианты LR-анализаторов
Преобразования КС-грамматик
Преобразования КС-грамматик - 2
Алгоритм Кока-Янгера-Касами
Алгоритм разбора сверху-вниз
Алгоритм разбора сверху-вниз - 2

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

Преобразователи с магазинной памятью
Синтаксически управляемый перевод
Схемы синтаксически управляемого перевода
Схемы синтаксически управляемого перевода
Схемы синтаксически управляемого перевода - 2
Атрибутные грамматики
Определение атрибутных грамматик
Определение атрибутных грамматик - 2
Определение атрибутных грамматик - 3
Классы атрибутных грамматик и их реализация

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

Занесение в среду и поиск объектов
Занесение в среду и поиск объектов - 2

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

Таблицы идентификаторов
Таблицы расстановки
Таблицы расстановки - 2
Таблицы расстановки со списками
Функции расстановки
Таблицы на деревьях
Таблицы на деревьях - 2
Таблицы на деревьях - 3
Реализация блочной структуры
Сравнение методов реализации таблиц

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

Представление в виде ориентированного графа
Трехадресный код
Трехадресный код - 2
Трехадресный код - 3
Линеаризованные представления
Виртуальная машина Java
Организация памяти
Набор команд виртуальной машины
Организация информации в генераторе кода
Уровень промежуточного представления

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

Модель машины
Модель машины - 2
Модель машины - 3
Выбор дерева вывода наименьшей стоимости
Выбор дерева вывода наименьшей стоимости - 2
Атрибутная схема сопоставления образцов
Атрибутная схема сопоставления образцов - 2
Атрибутная схема сопоставления образцов - 3
Динамическая организация памяти
Организация магазина со статической цепочкой

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

Система СУПЕР
Система СУПЕР - 2
Система YACC
Система YACC - 2

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

Формальные свойства
Формальные свойства - 2
Формальные свойства - 3
Формальные свойства - 4
Проверка на зацикленность
Проверка на зацикленность - 2
Проверка на зацикленность - 3
Простой язык программирования
Простой язык программирования - 2
Простой язык программирования - 3

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

Определение атрибутных грамматик
Атрибутированное дерево разбора
Незацикленные атрибутные грамматики
Вычислительные последовательности
Чистые многовизитные грамматики
Незацикленные атрибутные грамматики
Незацикленные атрибутные грамматики - 2
Незацикленные атрибутные грамматики - 3
Простые многовизитные атрибутные грамматики
Одновизитные атрибутные грамматики

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

Представление языков
Грамматики
Грамматики - 2
Регулярные множества и выражения
Конечные автоматы
Алгоритмы построения конечных автоматов
Регулярные множества и их представления
Алгебраические свойства регулярных множеств
КС-грамматики и МП-автоматы
КС-грамматики и МП-автоматы - 2

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

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

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

Категории безнадежных проектов
Категории безнадежных проектов - 2
Категории безнадежных проектов - 3
Почему существуют безнадежные проекты ?
Политика, политика, политика
Наивные представления маркетинговых служб
Наивные представления маркетинговых служб - 2
Наивный оптимизм юности
Менталитет первопроходцев у предпринимателей
Менталитет «Морского Корпуса»

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

Средства и процессы
Средства и процессы - 2
Средства и процессы - 3
Средства и процессы - 4
Риск выбора новых средств
Риск выбора новых средств - 2
Риск выбора новых средств - 3
Заключение
Заключение - 2
Безнадежные проекты как образ жизни

MATLAB в инженерных и научных расчетах

Данная книга посвящена иллюстрации возможностей одной из самых эффективных систем компьютерного программного обеспечения – пакета универсальных интегрированных программ MATLAB. Любознательному читателю предлагается ознакомиться в первом приближении с основами языка программирования и комплексной визуализации результатов решения ряда научных и инженерных задач. Рассматриваются такие проблемы как табулирование функций, решение нелинейных уравнений, поиск оптимальных решений, решение задач Коши, численное интегрирование и другие задачи, традиционно включаемые в курс численных методов. Алгоритм этих задач хорошо известен и разработчики системы MATLAB (фирма Math Works, Inc., U.S.A.) учли опыт численного решения и программирования задач вычислительной математики за все время существования вычислительной техники. Поэтому в системе MATLAB по каждой проблеме имеется несколько программ (иногда их более 10), предназначенных для ее решения в зависимости от особенностей данной задачи.

Программирование
Квадратичное
Ограничений
Достижение цели
Линейные
Нелинейное
Нелинейные
Наименьших
Неотрицательный
Линейный МНК

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

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

Модели процесса разработки ПО
ГОСТы
SW-CMM
RUP
MSF
PSP/TSP
Agile
Выбор модели процесса
Выбор модели процесса - 2
Что надо делать для успеха программного проекта

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

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

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

Вступительная лекция
Вступительная лекция - 2
Вступительная лекция - 3
Вступительная лекция - 4
Вступительная лекция - 5
Вступительная лекция - 6

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

Объектно-ориентированный подход
Объектно-ориентированный подход - 2
Объектно-ориентированный подход - 3
Объектно-ориентированный подход - 4
Объектно-ориентированный подход - 5
Объектно-ориентированный подход - 6

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

Платформа.NET и ее применение
Платформа.NET и ее применение - 2
Платформа.NET и ее применение - 3
Платформа.NET и ее применение - 4
Платформа.NET и ее применение - 5
Платформа.NET и ее применение - 6
Платформа.NET и ее применение - 7
Платформа.NET и ее применение - 8
Платформа.NET и ее применение - 9
Платформа.NET и ее применение - 10

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

Основные понятия языка C#
Основные понятия языка C# - 2
Основные понятия языка C# - 3
Основные понятия языка C# - 4
Основные понятия языка C# - 5
Основные понятия языка C# - 6
Основные понятия языка C# - 7
Основные понятия языка C# - 8
Основные понятия языка C# - 9
Основные понятия языка C# - 10

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

Краткая информация о платформе .NET
Базовые конструкции языка C#
Основные управляющие операторы
Пространства имен
Пример элементарной программы на C#
Порядок выполнения работы

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

Семантика основных конструкций языка C#
Семантика основных конструкций языка C# - 2
Семантика основных конструкций языка C# - 3
Семантика основных конструкций языка C# - 4

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

Изложим понятийный аппарат
Изложим понятийный аппарат - 2
Рассмотрев интуитивное определение
Рассмотрев интуитивное определение - 2
Основные понятия подхода: объекты, классы
Основные понятия подхода: объекты, классы - 2

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

Классы и обьекты
Создание обьекта
Понятия конструктора и деструктора
Наследование
Порядок выполнения работы
Варианты заданий

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

Теория типов и типизация в .NET
Теория типов и типизация в .NET - 2
Теория типов и типизация в .NET - 2
Теория типов и типизация в .NET - 2
Теория типов и типизация в .NET - 3
Теория типов и типизация в .NET - 4

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

Концепция наследования и ее реализация в C#
Концепция наследования и ее реализация в C# - 2

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

Концепция инкапсуляции и ее реализация в C#
Концепция инкапсуляции и ее реализация в C# - 2
Концепция инкапсуляции и ее реализация в C# - 3
Концепция инкапсуляции и ее реализация в C# - 4

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

Концепция полиморфизма
Виртуальные методы
Описание абстрактного метода
Абстрактные классы
Описание абстрактного класса
Порядок выполнения работы

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

Возможности полиморфизма в языке C#
Возможности полиморфизма в языке C# - 2

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

Интерфейсы
Описание интерфейса
Делегаты
Описание делегата
Многоадресность делегатов
Порядок выполнения работы

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

Обработка событий
Широковещательные события
Исключительные ситуации
Описание блока try и catch
Возврат из исключения
Конструкция try/catch с блоком finally
Генерация исключений
Оператор throw
Наследование классов исключений
Порядок выполнения работы

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

Компонентное программирование в .NET
Компонентное программирование в .NET - 2

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

Гетерогенные приложения
Взаимодействие с SML.NET
Описание директивы export
Директива reference
Порядок выполнения работы
Варианты заданий

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

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

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

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

Недетерминированные конечные автоматы
Недетерминированные конечные автоматы - 2
Конфигурация конечного автомата
Автоматы с однобуквенными переходами
Характеризация праволинейных языков
Нормальная форма праволинейных грамматик
Детерминированные конечные автоматы
Преобразование конечного автомата

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

Свойства замкнутости класса автоматных языков
Пересечение и дополнение автоматных языков
Лемма о разрастании для автоматных языков
Примеры неавтономных языков

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

Слова, языки и грамматики
Формальные языки
Операции над языками
Операции над языками - 2
Гомоморфизмы
Порождающие грамматики
Порождающие грамматики - 2
Классы грамматик

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

Дополнительные свойства автоматных языков
Гомоморфизмы и автоматные языки
Локальные языки
Длины слов в автоматных языках

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

Регулярные выражения
Определение регулярного выражения
Свойства регулярных выражений
Теорема Клини
Теорема Клини - 2
Звездная высота

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

Множества правых контекстов
Минимизация детерминированных автоматов
Множества двусторонних контекстов
Классы эквивалентности слов

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

Деревья вывода
Однозначные контекстно-свободные грамматики
Однозначные праволинейные грамматики
Языки Дика и Лукасевича

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

Устранение бесполезных символов
Устранение эпсилон-правил
Нормальная форма Хомского
Нормальная форма Грейбах

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

Лемма о разрастании для языков
Лемма о разрастании для языков - 2
Лемма о разрастании для линейных языков
Свойства замкнутости класса линейных языков
Свойства замкнутости класса
Пересечение и дополнение языков
Пересечение языка с автоматным языком
Теорема Парика

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

Определение автомата с магазинной памятью
Определение автомата с магазинной памятью - 2
Характеризация контекстно-свободных языков
Автоматы с магазинной памятью

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

Свойства контекстно-свободных языков
Деление контекстно-свободных языков
Гомоморфизмы и контекстно-свободные языки
Представления контекстно-свободных языков

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

Детерминированные контекстно-свободные языки
Автоматы с магазинной памятью
Свойства класса детерминированных языков
Свойства класса детерминированных языков - 2

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

Синтаксический разбор
Нисходящий разбор
Восходящий разбор
Восходящий разбор - 2

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

Алгоритмические проблемы
Машины Тьюринга
Разрешимые и перечислимые множества
Массовые задачи
Грамматики типа 0
Проблема соответствий Поста

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

Алгоритмически разрешимые проблемы
Неукорачивающие грамматики
Линейно ограниченные автоматы
Проблема выводимости слова
Проблема пустоты языка
Проблема бесконечности языка
Проблема эквивалентности конечных автоматов
Проблема детерминированных МП-автоматов
Классы P и NP
Проблема неравенства регулярных выражений

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

Алгоритмически неразрешимые проблемы
Пересечение контекстно-свободных языков
Проблема однозначности
Дополнение контекстно-свободного языка
Проблема автоматности
Проблемы контекстной свободности

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

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

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

Основные определения
Основные определения - 2
Принцип обобщения
Виды области значений функции принадлежности
Гетерогенные нечеткие множества
Нечеткие операторы

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

Нечеткие отношения
Основные определения
Основные определения - 2
Операции над нечеткими отношениями
Свойства нечетких отношений
Декомпозиция нечетких отношений
Транзитивное замыкание нечетких отношений
Проекции нечетких отношений

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

Классы нечетких отношений
Отношения сходства и различия
Отношения сходства и различия - 2
Задачи нечеткой классификации
Порядки и слабые порядки
Порядки и слабые порядки - 2
Порядки и слабые порядки - 3
Задачи нечеткого упорядочения

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

Показатель размытости нечетких множеств
Аксиоматический подход к определению
Метрический подход к определению
Связь показателя размытости
Нечеткие меры
Нечеткие меры - 2
Супераддитивные меры
Субаддитивные меры
Нечеткие интегралы
Применение нечетких мер и интегралов

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

Типы шкал
Типы шкал - 2
Типы шкал - 3
Методы измерений
Методы проведения групповой экспертизы
Построение функции принадлежности
Построение функции принадлежности - 2
Построение функции принадлежности - 3

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

Прямые методы для одного эксперта
Косвенные методы для одного эксперта
Косвенные методы для одного эксперта - 2
Прямые методы для группы экспертов
Косвенные методы для группы экспертов
Косвенные методы для группы экспертов - 2
Методы построения терм-множеств
Методы построения терм-множеств - 2

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

Основные определения
Нечеткие треугольные числа
Нечеткие треугольные числа - 2
Четкие арифметики треугольных чисел
Четкие арифметики треугольных чисел - 2
Размытые арифметики треугольных чисел

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

Нечеткая логика
Нечеткая логика - 2
Операции отрицания
Операции отрицания - 2
Операции конъюнкции и дизъюнкции
Операции конъюнкции и дизъюнкции - 2

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

Понятие лингвистической переменной
Понятие лингвистической переменной - 2
Лингвистические переменные истинности
Лингвистические переменные истинности - 2
Связки в нечеткой лингвистической логике
Значения истинности неизвестно и не определено

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

Теория приближенных рассуждений
Композиционное правило вывода
Правило modus ponens как частный случай
Нечеткие экспертные системы

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

Формализация понятия нечеткого алгоритма
Формализация понятия нечеткого алгоритма - 2
Способы выполнения нечетких алгоритмов
Представление нечеткого алгоритма в виде графа

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

Нечеткие алгоритмы обучения
Обучающийся нечеткий автомат
Обучение на основе условной нечеткой меры
Обучение на основе условной нечеткой меры - 2
Адаптивный нечеткий логический регулятор
Алгоритм нечеткого отношения предпочтения
Алгоритм нечеткого отношения предпочтения - 2
Алгоритм уточнения лингвистических критериев

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

Нечеткие цели, ограничения и решения
Нечеткие цели, ограничения и решения - 2
Нечеткие цели, ограничения и решения - 3
Задачи нечеткого мат. программирования
Задачи нечеткого мат. программирования - 2
Модели нечеткой ожидаемой полезности

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

Игры в нечетко определенной обстановке
Игры в нечетко определенной обстановке - 2
Многошаговые процессы принятия решений
Многошаговые процессы принятия решений - 2
Контроль в стохастической неопределенности
Контроль в стохастической неопределенности - 2

Архитектура среды тестирования на основе моделей

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

Введение
Тестирование на основе моделей и инструменты тестирования
Архитектурный каркас для тестирования на основе моделей
Пример построения теста
Литература


Рынки акций - перейти
Вексельное обращение - перейти
Рынок облигаций - перейти
Фондовая торговля - перейти
Дэйтрейдинг онлайн - перейти
Внутридневной трейдинг - перейти
Игра на бирже - перейти
Фондовый рынок РФ - перейти
Матричная лаборатория MatLab - перейти
Введение - перейти
Знакомство с матричной лабораторией MATLAB - перейти
Установка системы и первые навыки работы - перейти
Основы графической визуализации вычислений - перейти
Работа со справкой и примерами - перейти
Пользовательский интерфейс MATLAB - перейти