Теория и реализация языков программирования
Теория и реализация языков программирования
В книге представлены "классические" разделы теории разработки компиляторов: лексический и синтаксический анализ, организация памяти компилятора (таблицы символов) и периода исполнения (магазина), генерация кода. Рассматриваются такие средства автоматизации процесса разработки трансляторов, как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую "атрибутную" точку зрения на процесс разработки компилятора. В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов для машин с параллельной архитектурой. Авторы надеются восполнить эти пробелы в будущем. Книга рассчитана как на студентов и аспирантов программистских специальностей, так и на профессионалов в области программирования.Предисловие
В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов для машин с параллельной архитектурой. Авторы надеются восполнить эти пробелы в будущем. Книга рассчитана как на студентов и аспирантов программистских специальностей, так и на профессионалов в области программирования.
Место компилятора в программном обеспечении
Место компилятора в программном обеспечении Компиляторы составляют существенную часть программного обеспечения ЭВМ. Это связано с тем, что языки высокого уровня стали основным средством разработки программ. Сегодня только очень малая часть программного обеспечения, требующая особой эффективности, разрабатывается с помощью ассемблеров.
|
Структура компилятора |
Структура компилятора - 2 |
Алфавиты, цепочки и языки
Пусть V - алфавит. Цепочка в алфавите V - это любая строка конечной длины, составленная из символов алфавита V . Синонимом цепочки являются предложение, строка и слово. Пустая цепочка (обозначается e) - это цепочка, в которую не входит ни один символ.
Лексический анализ
Основная задача лексического анализа - разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, то есть выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители).
Контекстно-свободные грамматики и автоматы с магазинной памятью
Упорядоченным графом называется пара (V,E), где V есть множество вершин, а E - множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v, v1), (v, v2), ... , (v, vn)). Этот элемент указывает, что из вершины v выходят n дуг, причем первой из них считается дуга, входящая в вершину v1, второй - дуга, входящая в вершинуv2, и т.д.
Элементы теории перевода
До сих пор мы рассматривали процесс синтаксического анализа только как процесс анализа допустимости входной цепочки. Однако, в компиляторе синтаксический анализ служит основой еще одного важного шага - построения дерева синтаксического анализа.
Описание областей видимости и блочной структуры
Задачей контекстного анализа является установление свойств объектов и их использования. Наиболее часто решаемой задачей является определение существования объекта и соответствия его использования контексту, что осуществляется с помощью анализа типа объекта.
|
Занесение в среду и поиск объектов |
Занесение в среду и поиск объектов - 2 |
Организация таблиц символов
В процессе работы компилятор хранит информацию об объектах программы в специальных таблицах символов. Как правило, информация о каждом объекте состоит из двух основных элементов: имени объекта и описания объекта. Информация об объектах программы должна быть организована таким образом, чтобы поиск ее был по возможности быстрее, а требуемая память по возможности меньше.
Промежуточное представление программы
В процессе трансляции компилятор часто используют промежуточное представление (ПП) исходной программы, предназначенное прежде всего для удобства генерации кода и/или проведения различных оптимизаций. Сама форма ПП зависит от целей его использования.
Генерация кода
Задача генератора кода - построение для программы на входном языке эквивалентной машинной программы. Обычно в качестве входа для генератора кода служит некоторое промежуточное представление программы.
Системы автоматизации построения трансляторов
Системы автоматизации построения трансляторов (САПТ) предназначены для автоматизации процесса разработки трансляторов. Очевидно, что для того, чтобы описать транслятор, необходимо иметь формализм для описания. Этот формализм затем реализуется в виде входного языка САПТ. Как правило, формализмы основаны на атрибутных грамматиках.
|
Система СУПЕР Система СУПЕР - 2 |
Система YACC Система YACC - 2 |
Формальные свойства
Допустим, что нам нужно дать точное определение двоичной системы записи чисел. Это можно сделать многими способами. В данном разделе мы рассмотрим метод, который может быть использован и для других систем счисления. В случае двоичной системы этот метод сводится к определению, основанному на следующей констекстно-свободной (КС) грамматике
Определение атрибутных грамматик
Среди всех формальных методов описания языков программирования атрибутные грамматики получили, по- видимому, наибольшую известность и распространение. Причиной этого является то, что формализм атрибутных грамматик основывается на дереве разбора программы в КС-грамматике, что сближает его с хорошо разработанной теорией и практикой построения трансляторов.
Представление языков
Принадлежит ли цепочка x = abaababb языку, порождаемому грамматикой с правилами: S SaSb|?
Путь камикадзе
Вряд ли можно где-нибудь увидеть объявление о найме для участия в безнадежном проекте. Какой смысл спрашивать: «Хотите ли вы работать сверхурочно без какой-либо прибавки к зарплате? Привлекает ли вас бесконечная работа по устаревшей технологии и тщетное ожидание участия в каком-нибудь замечательном проекте GUI/DSS/DWH/HTML? Каково будет узнать, что трехзвенная архитектура «клиент-сервер» позволит остальным участникам проекта обойтись без вашей помощи?»На самом деле, безнадежные проекты редко объявляются таковыми во всеуслышание, и вам придется достаточно долго проработать в нанявшей вас компании, прежде чем удастся обнаружить, что она обладает склонностью плодить безнадежные проекты.
Если вашему коллеге приходится руководить безнадежным проектом, то ему можно посоветовать включить в контракт пункт, позволяющий цивилизованным способом выйти из проекта. Одна из серьезных причин выхода - неспособность высшего руководства воспринимать правдивую информацию о проекте. Принимающий на себя руководство безнадежным проектом должен быть готов к тому, что у него будет практически отсутствовать пространство для маневра в отношении функциональности, затрат или времени.
Определение безнадежного проекта
Под безнадежным проектом (death march) я понимаю такой проект, параметры которого отклоняются от нормальных значений по крайней мере на 50%. По отношению к софтверным проектам это обычно означает одно или более из следующих ограничений: План проекта сжат более чем наполовину по сравнению с нормальным расчетным планом; таким образом, проект, требующий в нормальных условиях 12 календарных месяцев, приходится выполнять за 6 или менее месяцев. Жесткая конкуренция на мировом рынке делает такую ситуацию наиболее распространенной.
Минимально необходимый набор средств
Помня обо всех высказанных предостережениях, практически невозможно для такого «дилетанта», как я, с ходу перечислить все средства, рекомендуемые для безнадежного проекта. Когда задают такой вопрос, мой ответ - «это зависит от ... » - обычен для присущего консультантам и приводящего к замешательству стремления уходить от прямого ответа на любой вопрос.
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 |
Объектно-ориентированный подход к программированию
Рассмотрим особенности объектно-ориентированного подхода к программированию в сравнении с функциональным подходом. Напомним, что классификация подходов к программированию была построена нами во вступительной лекции.
Платформа.NET и ее применение
Корпорацией Microsoft предложен новаторский компонентно-ориентированный подход к программированию, который является развитием объектно-ориентированного направления. Согласно этому подходу, интеграция объектов (возможно, гетерогенной природы) производится на основе интерфейсов, представляющих эти объекты (или фрагменты программ) как независимые компоненты. Такой подход существенно облегчает написание и взаимодействие программных "молекул"-компонент в гетерогенной среде проектирования и реализации.
Основные понятия языка программирования C#
Прежде чем перейти непосредственно к исследованию конструктивных особенностей языка программирования C#, рассмотрим ход его развития. История основной ветви языков программирования, которая привела к появлению C#, восходит к 60-м годам, а именно, ко времени возникновения языка B. Последний является типичным представителем ранних императивных языков программирования. Язык B был придуман в 1963 году творческим коллективом разработчиков, основным создателем языка принято считать К. Томпсона
Краткая информация о платформе .NET
Платформа .NET Framework предоставляет среду для поддержки создания и выполнения интероперабельных гетерогенных приложений. Основными особенностями данной платформы являются не зависящая от языка среда исполнения (Common Language Runtime, CLR) и библиотека классов .NET.
|
Краткая информация о платформе .NET Базовые конструкции языка C# Основные управляющие операторы |
Пространства имен Пример элементарной программы на C# Порядок выполнения работы |
Семантика основных конструкций языка программирования C#
В данной лекции будут рассмотрены вопросы, относящиеся к понятийному аппарату и выразительным возможностям семантического представления формальных теорий и языков программирования. При этом основное внимание будет уделено сопоставлению семантики языков объектно-ориентированного и функционального программирования.
|
Семантика основных конструкций языка C# Семантика основных конструкций языка C# - 2 |
Семантика основных конструкций языка C# - 3 Семантика основных конструкций языка C# - 4 |
Основные понятия объектно-ориентированного подхода: объекты, классы и методы
В данной лекции будут рассмотрены вопросы, относящиеся к идеологии, методологии и практике моделирования основных элементов объектно-ориентированного подхода к программированию посредством двухуровневой концептуализации. Особенности практической реализации основных аспектов концепции ООП описаны на примере языка программирования C#.
Классы и обьекты
Понятие класса является фундаментальным в ООП и служит основой для создания объектов. В описании класса определяются данные (т.е. переменные) и код (т.е. методы), манипулирующий этими данными. Объекты являются экземплярами класса.
|
Классы и обьекты Создание обьекта Понятия конструктора и деструктора |
Наследование Порядок выполнения работы Варианты заданий |
Теория типов и типизация в .NET
Прежде всего, отметим то бесспорное преимущество типизированных исчислений, что при таком подходе моделируемая предметная область лучше структурирована, чем в том случае, если отсутствует сегментация на типы. Типизация структурирует предметную область по иерархическому принципу.
Концепция наследования и ее реализация в языке 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# основана на использовании делегатов.
Компонентное программирование в .NET
Cледует отметить то обстоятельство, что компонентно-ориентированный подход к проектированию и реализации программных систем и комплексов является в некотором смысле развитием объектно-ориентированного и практически более пригоден для разработки крупных и распределенных систем (например, корпоративных приложений).
|
Компонентное программирование в .NET |
Компонентное программирование в .NET - 2 |
Гетерогенные приложения
Платформа программирования .NET изначально разрабатывалась для построения приложений на компонентной основе и обеспечения независимости взаимодействия компонентов от языка программирования. Благодаря этому в рамках одного приложения могут быть использованы компоненты, реализующие различные подходы к программированию.
|
Гетерогенные приложения Взаимодействие с SML.NET Описание директивы export |
Директива reference Порядок выполнения работы Варианты заданий |
Математическая теория формальных языков
Цель этого курса - познакомить читателя с некоторыми основополагающими моделями и результатами, используемыми в теоретической информатике. Неудивительно, что они относятся к математике, а не к какой-либо другой области знаний - ведь в науке о компьютерах именно математические абстракции являются самыми плодотворными.Рассматриваемые здесь идеи и результаты принадлежат теории формальных языков, грамматик и автоматов. По существу, эта теория описывает некоторые ограниченные абстрактные машины, способные выполнять определенные операции со строками. Например, конечный автомат может выяснить, содержит ли некоторый файл определенное слово, а автомат с магазинной памятью способен определить, правильна ли система вложенных круглых, квадратных и фигурных скобок.
Предисловие
Как подсказывает само название курса, основным объектом рассмотрения является формальный язык - произвольное множество конечных последовательностей символов, взятых из некоторого конечного множества (такие последовательности называются словами).
Конечные автоматы
Два наиболее распространенных способа конечного задания формального языка - это грамматики и автоматы. Автоматами в данном контексте называют математические модели некоторых вычислительных устройств. В этой лекции рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам.
Основные свойства автоматных языков
Для практического применения теории конечных автоматов нужны средства, позволяющие выяснять, является ли некоторый формальный язык автоматным. Для получения положительного ответа на такой вопрос могут пригодиться достаточные условия автоматности, для отрицательного ответа - необходимые условия автоматности.
|
Свойства замкнутости класса автоматных языков Пересечение и дополнение автоматных языков |
Лемма о разрастании для автоматных языков Примеры неавтономных языков |
Слова, языки и грамматики
Следует заметить, что каждая грамматика порождает ровно один язык, но обратное неверно: некоторые формальные языки нельзя задать никакой порождающей грамматикой, а каждому языку, который порождается хотя бы одной грамматикой, соответствует сразу бесконечное множество грамматик (причем они могут принадлежать разным классам).
|
Слова, языки и грамматики Формальные языки Операции над языками Операции над языками - 2 |
Гомоморфизмы Порождающие грамматики Порождающие грамматики - 2 Классы грамматик |
Дополнительные свойства автоматных языков
Эта лекция содержит дополнительные результаты, не используемые в дальнейшем изложении. В начале лекции доказывается замкнутость класса всех автоматных языков относительно взятия гомоморфного образа и относительно взятия полного гомоморфного прообраза.
|
Дополнительные свойства автоматных языков Гомоморфизмы и автоматные языки |
Локальные языки Длины слов в автоматных языках |
Регулярные выражения
о сих пор мы рассматривали два способа конечного описания формального языка: грамматики и автоматы. Третий способ, часто наиболее удобный и компактный, - регулярные выражения. В них используются символы, обозначающие итерацию, конкатенацию и объединение языков. Например, для обозначения итерации традиционно используется символ "звездочка".
|
Регулярные выражения Определение регулярного выражения Свойства регулярных выражений |
Теорема Клини Теорема Клини - 2 Звездная высота |
Синтаксические моноиды
Основная цель данной лекции - доказать еще один критерий автоматности формального языка. Этот критерий можно сформулировать в терминах классов эквивалентности слов по взаимозаменяемости (однако формальные определения будут даны без использования понятия класса эквивалентности). Слова x и y считаются взаимозаменяемыми (относительно языка L), если при замене в любом слове из языка L подслова, совпадающего с x, на y снова получится слово из языка L и наоборот.
|
Множества правых контекстов Минимизация детерминированных автоматов |
Множества двусторонних контекстов Классы эквивалентности слов |
Неоднозначность в контекстно-свободных грамматиках
Перейдем к более богатому классу языков - к контекстно-свободным языкам. Они находят применение в разнообразных программных продуктах, таких как компиляторы, средства форматирования исходного кода, средства статического анализа программ, синтаксические редакторы, системы верстки, программы просмотра форматированного текста поисковые системы
|
Деревья вывода Однозначные контекстно-свободные грамматики |
Однозначные праволинейные грамматики Языки Дика и Лукасевича |
Нормальные формы контекстно-свободных грамматик
Основная цель этой лекции - доказать, что каждая контекстно-свободная грамматика эквивалентна некоторой контекстно-свободной грамматике специального вида, а именно грамматике в нормальной форме Хомского. Этот факт используется дальше в доказательствах многих теорем о контекстно-свободных языках.
|
Устранение бесполезных символов Устранение эпсилон-правил |
Нормальная форма Хомского Нормальная форма Грейбах |
Основные свойства контекстно-свободных языков
Пусть язык порождается грамматикой в нормальной форме Хомского . Индукцией по k легко доказать, что для любого дерева вывода в грамматике G длина кроны дерева не превышает 2k-2, где k - количество вершин в самом длинном пути, начинающемся в корне дерева и заканчивающемся в некоторой вершине, помеченной символом из
Автоматы с магазинной памятью
Подобно тому, как праволинейным грамматикам соответствуют конечные автоматы, контекстно-свободным грамматикам соответствуют автоматы с магазинной памятью (МП-автоматы). В таком автомате, помимо ограниченной памяти, хранящей текущее состояние, имеется потенциально бесконечная память, используемая как стек (магазин), то есть структура данных, где в каждый момент доступен только тот элемент, который был добавлен позже остальных присутствующих на данный момент элементов
|
Определение автомата с магазинной памятью Определение автомата с магазинной памятью - 2 |
Характеризация контекстно-свободных языков Автоматы с магазинной памятью |
Дополнительные свойства контекстно-свободных языков
В этой лекции излагаются те свойства контекстно-свободных языков, которые удобно доказывать с привлечением автоматов с магазинной памятью. В первых двух разделах приводятся некоторые свойства замкнутости класса контекстно-свободных языков (замкнутость относительно деления, взятия гомоморфного образа и полного гомоморфного прообраза).
|
Свойства контекстно-свободных языков Деление контекстно-свободных языков |
Гомоморфизмы и контекстно-свободные языки Представления контекстно-свободных языков |
Детерминированные контекстно-свободные языки
К сожалению, теорема о детерминизации не переносится с конечных автоматов на автоматы с магазинной памятью. Возникает важный для практических приложений класс языков, распознаваемых детерминированными автоматами с магазинной памятью (то есть такими автоматами с магазинной памятью, которые ни в какой конфигурации не могут выбирать между несколькими очередными тактами).
|
Детерминированные контекстно-свободные языки Автоматы с магазинной памятью |
Свойства класса детерминированных языков Свойства класса детерминированных языков - 2 |
Синтаксический разбор
В этой лекции даются формальные определения, связанные с прямыми (то есть читающими входную строку слева направо) синтаксическими анализаторами. В первом разделе доказывается, что для языков из класса LL(1) можно построить основанный на детерминированном автомате с магазинной памятью анализатор, который создает дерево разбора, двигаясь снизу вверх, то есть от листьев к корню (в теории контекстно-свободных грамматик принято изображать деревья с корнем наверху).
|
Синтаксический разбор Нисходящий разбор |
Восходящий разбор Восходящий разбор - 2 |
Алгоритмические проблемы
Основная цель этой лекции - дать определения понятий, необходимых для математически строгой формулировки результатов следующих двух лекций. Для более подробного ознакомления с вычислимостью, разрешимостью, перечислимостью и универсальными моделями вычислений следует обратиться к какому-либо вводному курсу по теории алгоритмов
|
Алгоритмические проблемы Машины Тьюринга Разрешимые и перечислимые множества |
Массовые задачи Грамматики типа 0 Проблема соответствий Поста |
Алгоритмически разрешимые проблемы
В этой лекции рассматриваются наиболее известные разрешимые проблемы, связанные с грамматиками, автоматами и регулярными выражениями. Поскольку все приведенные выше доказательства эквивалентности разных способов конечного задания формального языка были конструктивными, не важно, какой из эквивалентных способов задания языка (например, посредством контекстно-свободной грамматики или автомата с магазинной памятью) используется в точной формулировке массовой задачи
Алгоритмически неразрешимые проблемы
В этой лекции рассматриваются оказавшиеся неразрешимыми алгоритмические проблемы, связанные с контекстно-свободными языками. Всюду предполагается, что в индивидуальных задачах каждый язык представлен контекстно-свободной грамматикой (но можно, конечно, использовать и автоматы с магазинной памятью).
|
Алгоритмически неразрешимые проблемы Пересечение контекстно-свободных языков Проблема однозначности |
Дополнение контекстно-свободного языка Проблема автоматности Проблемы контекстной свободности |
Основы теории нечетких множеств
Теория нечетких множеств представляет собой обобщение и переосмысление важнейших направлений классической математики. У ее истоков лежат идеи и достижения многозначной логики, которая указала на возможности перехода от двух к произвольному числу значений истинности и поставила проблему оперирования понятиями с изменяющимся содержанием; теории вероятностей, которая, породив большое количество различных способов статистической обработки экспериментальных данных, открыла пути определения и интерпретации функции принадлежности; дискретной математики, которая предложила инструмент для построения моделей многомерных и многоуровневых систем, удобный при решении практических задач.Подход к формализации понятия нечеткого множества состоит в обобщении понятия принадлежности. В обычной теории множеств существует несколько способов задания множества. Одним из них является задание с помощью характеристической функции, определяемой следующим образом. Пусть — так называемое универсальное множество, из элементов которого образованы все остальные множества, рассматриваемые в данном классе задач, например множество всех целых чисел, множество всех гладких функций и т.д.
Основные определения
С точки зрения характеристической функции, нечеткие множества есть естественное обобщение обычных множеств, когда мы отказываемся от бинарного характера этой функции и предполагаем, что она может принимать любые значения на отрезке . В теории нечетких множеств характеристическая функция называется функцией принадлежности, а ее значение — степенью принадлежности элемента нечеткому множеству
|
Основные определения Основные определения - 2 Принцип обобщения |
Виды области значений функции принадлежности Гетерогенные нечеткие множества Нечеткие операторы |
Нечеткие отношения
Нечеткие отношения играют фундаментальную роль в теории нечетких систем. Аппарат теории нечетких отношений используется при построении теории нечетких автоматов, при моделировании структуры сложных систем, при анализе процессов принятия решений.
Классы нечетких отношений
Все типы нечетких отношений в зависимости от свойств, которыми они обладают, могут быть разделены на три больших класса. В первый класс входят симметричные отношения, которые обычно характеризуют сходство или различие между объектами множества . Второй класс образуют антисимметричные отношения; они задают на множестве отношения упорядоченности, доминирования, подчиненности и т.п.
Показатель размытости нечетких множеств. Нечеткие меры и интегралы
Как уже говорилось в прошлых лекциях, нечеткие множества используются для описания плохо определенных, неоднозначно понимаемых ситуаций, объектов, понятий. Де Лука предложил ввести в рассмотрение показатель этой неопределенности, который можно было бы использовать для оценки, классификации объектов, описываемых нечеткими множествами.
Методы построения функции принадлежности. Классификация
С древних времен и до наших дней измерения как один из способов познания играют важную роль в жизни человека. Сначала человек в своей повседневной деятельности довольствовался информацией, доставляемой лишь его органами чувств, а затем привлек им в помощь средства измерительной техники.
Прямые методы для одного эксперта
Прямые методы для одного эксперта состоят в непосредственном задании функции, позволяющей вычислять значения. Например, пусть переменная "ВОЗРАСТ" принимает значения из интервала . Слово "МОЛОДОЙ" можно интерпретировать как имя нечеткого подмножества , которое характеризуется функцией совместимости.
Нечеткие треугольные числа
Нечеткое число — это нечеткое подмножество универсального множества действительных чисел, имеющее нормальную и выпуклую функцию принадлежности, то есть такую, что: а) существует значение носителя, в котором функция принадлежности равна единице, а также b) при отступлении от своего максимума влево или вправо функция принадлежности не возрастает.
|
Основные определения Нечеткие треугольные числа Нечеткие треугольные числа - 2 |
Четкие арифметики треугольных чисел Четкие арифметики треугольных чисел - 2 Размытые арифметики треугольных чисел |
Нечеткая логика
В сочетании слов "нечеткий" и "логика" есть что-то необычное. Логика в обычном смысле слова есть представление механизмов мышления, то, что никогда не может быть нечетким, но всегда строгим и формальным. Однако математики, исследовавшие эти механизмы мышления, заметили, что в действительности существует не одна логика (например, булева), а столько, сколько мы пожелаем, потому что все определяется выбором соответствующей системы аксиом.
|
Нечеткая логика Нечеткая логика - 2 Операции отрицания |
Операции отрицания - 2 Операции конъюнкции и дизъюнкции Операции конъюнкции и дизъюнкции - 2 |
Понятие лингвистической переменной
Лингвистическая переменная отличается от числовой переменной тем, что ее значениями являются не числа, а слова или предложения в естественном или формальном языке. Поскольку слова в общем менее точны, чем числа, понятие лингвистической переменной дает возможность приближенно описывать явления, которые настолько сложны, что не поддаются описанию в общепринятых количественных терминах.
Теория приближенных рассуждений
Под приближенными рассуждениями понимается процесс, при котором из нечетких посылок получают некоторые следствия, возможно, тоже нечеткие. Приближенные рассуждения лежат в основе способности человека понимать естественный язык, разбирать почерк, играть в игры, требующие умственных усилий, в общем, принимать решения в сложной и не полностью определенной среде.
|
Теория приближенных рассуждений Композиционное правило вывода |
Правило modus ponens как частный случай Нечеткие экспертные системы |
Формализация понятия нечеткого алгоритма
Различные понятия, нечеткие по своей природе, могут быть формально описаны посредством нечетких множеств. Нечеткая логика, например, позволяет формализовать простые логические связки нечетких переменных с помощью нечетких высказываний. Для описания же сложных соотношений между переменными удобно использовать нечеткие алгоритмы.
|
Формализация понятия нечеткого алгоритма Формализация понятия нечеткого алгоритма - 2 |
Способы выполнения нечетких алгоритмов Представление нечеткого алгоритма в виде графа |
Нечеткие алгоритмы обучения
Известно, что обучающиеся системы улучшают функционирование в процессе работы, модифицируя свою структуру или значение параметров. Предложено большое число способов описания и построения обучающихся систем. Все они предполагают решение следующих задач: выбор измерений (свойств, рецепторов); поиск отображения пространства рецепторов в пространство признаков, которые осуществляют вырожденное отображение объектов; поиск критерия отбора признаков
Нечеткие цели, ограничения и решения
Непрерывно возрастающая сложность технологии контролируемых объектов настоятельно нуждалась в централизованном управлении и поэтому вызвала к жизни иерархическую структуру принятия решений. Поэтому появилась необходимость разделения всего процесса принятия решений управления на такое число уровней, чтобы решение задачи оптимизации на каждом из них было не сложным.
Игры в нечетко определенной обстановке
Во многих прикладных областях часто встречаются ситуации, в которых выполнение цели или результаты принятия решений одним лицом зависят не только от его действий, но и от действий другого лица или группы лиц, преследующих свои собственные цели. Рассмотренный подход к задачам принятия решений можно применять и для анализа подобных игровых ситуаций в нечетко определенной обстановке.
Архитектура среды тестирования на основе моделей
Представлен подход к построению архитектуры инструментария для тестирования на основе моделей, использующего современные компонентные технологии. Одна из основных идей, лежащих в его основе — применение техник неинвазивной композиции, позволяющих с минимальными затратами интегрировать множество независимо разработанных компонентов в сложную систему и переконфигурировать ее, не изменяя кода компонентов. Также описывается прототипная реализации предложенного подхода на базе свободно доступных библиотек и пример ее использования для построения тестов.Введение
Тестирование на основе моделей и инструменты тестирования
Архитектурный каркас для тестирования на основе моделей
Пример построения теста
Литература
Рынки акций - перейти
Вексельное обращение - перейти
Рынок облигаций - перейти
Фондовая торговля - перейти
Дэйтрейдинг онлайн - перейти
Внутридневной трейдинг - перейти
Игра на бирже - перейти
Фондовый рынок РФ - перейти
Матричная лаборатория MatLab - перейти
Введение - перейти
Знакомство с матричной лабораторией MATLAB - перейти
Установка системы и первые навыки работы - перейти
Основы графической визуализации вычислений - перейти
Работа со справкой и примерами - перейти
Пользовательский интерфейс MATLAB - перейти
