WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

«Кафедра прикладной математики и информатики Основы системы компьютерной алгебры GAP Методические рекомендации и лабораторный ...»

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Тольяттинский государственный университет»

Кафедра прикладной математики и информатики

Основы системы

компьютерной алгебры GAP

Методические рекомендации

и лабораторный практикум

Составители:

Крайнюков Н.И., к.т.н., доцент

Мельников Б.Ф., д.ф.-м.н., профессор

ТОЛЬЯТТИ – 2012

УДК 519.61 Печатается по решению научнометодического

ББК 22.17 совета ФГБОУ ВПО «ТГУ»

К 12 Работа выполнена при поддержке ФЦП «Научные и научнопедагогические кадры инновационной России» на 2009-2013 гг.

Рецензент: Тютюнов Ю.В. – доктор физико-математических наук, профессор кафедры глобальных информационных систем ФГБОУ ВПО «Южный федеральный университет».

К 12 Крайнюков Н.И., Мельников Б.Ф. Основы системы компьютерной алгебры GAP: Методические рекомендации и лабораторный практикум. Тольятти: ТГУ, 2012. 26 с.

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

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



Методические рекомендации предназначены для преподавателей и студентов физико-математических и технических специальностей.

УДК 519.61 ББК 22.17 © Крайнюков Н.И., Мельников Б.Ф.

© ФГБОУ ВПО «ТГУ»

СОДЕРЖАНИЕ

Введение 4 Лабораторная работа №1 Запуск системы компьютерной алгебры GAP. Основные примы работы.

Лабораторная работа №2 Списки и бинарные отношения. Полугруппы бинарных отношений и преобразований.

Лабораторная работа №3 Пакеты программ для прикладных областей. Пакет automata. Функции создание автомата, определение свойств автоматов, операции с автоматами.

Лабораторная работа №4 Конечные поля. Функции над конечными полями. Представление функций полиномами. 22 Лабораторная работа №5 Исследование свойств недетерминированных конечных автоматов. 25 Лабораторная работа №6 Исследование свойств недетерминированных конечных автоматов. 26 Приложение 1 Немного теории о недетерминир

–  –  –

Ссылки в Интернет 43

ВВЕДЕНИЕ

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

Системы компьютерной алгебры GAP ("Groups, Algorithms and Programming") была начата в 1986 г. в г. Аахен, Германия.

GAP является открытой, свободно распространяемой и расширяемой системой. Система GAP разрабатывалась под Unix, a затем была перенесена для работы в других операционных системах. Она работает в версиях Unix/Linux, а также в Windows и Mac OS. Но, к сожалению, ряд пакетов, расширяющих функциональность системы, работает только в среде Unix/Linux.

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

Система включает 4 основные компоненты:

ядро системы – обеспечивающую работу с системой в программном и интерактивном режиме;

пакеты, библиотеки функций – в которой реализованы разнообразные алгоритмы прикладной алгебры;

библиотеки данных – включая, большую библиотеку групп;

подробную документацию.

Первоначально система GAP разрабатывалась для исследований в комбинаторной теории групп.

Применение библиотеки gmp позволяет в GAP производить вычисления с огромными целыми и рациональными числами (ограничение

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

На сайте GAP (http://www.gap-system.org/) можно найти последнюю информацию о текущем состоянии системы и разработках для применения в той или проблемной области.

ЛАБОРАТОРНАЯ РАБОТА №1.

ЗАПУСК СИСТЕМЫ КОМПЬЮТЕРНОЙ АЛГЕБРЫ GAP.

ОСНОВНЫЕ ПРИЁМЫ РАБОТЫ

Цель работы: изучить назначение и приемы работы с системой компьютерной алгебры GAP, сохранение протокола сеанса работы с системой.

В данной лабораторной работе надо последовательно выполнить все этапы.

Рассмотрим работу программы в MS Windows и Linux.

1. В свом каталоге сначала запустите файл gap.bat для работы в окне командной строки Windows (окне MS-DOS) или наберите gap в командной строке. После появления приглашения вида gap введите команду quit; для выхода из системы. Все команды завершаются точкой с запятой, после чего необходимо нажать клавишу Enter.

2. Простейшие вычисления можно выполнять, запуская систему так, как указано в n.1.

3. Выполните вычисления, введя следующие команды:

2^200;

3^300;

4^400;

123456/1234;

2^300 3^200;

5^20000 mod 100;

2^300 3^200;

3^500 5^300;

5 in [l,2,3];

1 in [l,2,3];

2*2 = 5;

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

Введите следующую многострочную команду:

987654321/1234+ 123456789*34*5678+ Factorial(200)+ Sum([1..1000]);

В GAP имеет значение регистр текста.

Например, следующая команда приводит к ошибке:

gap sum(100);

Variable: 'sum' must have a value gap На экран при некоторых ошибках может выводиться промежуточное приглашение системы вида brk. Для выхода из него нужно ввести команду Cntl-d или quit;.

4. Получить подсказку по команде, функции или пакету можно с помощью команды ?имя команды, например:

gap ?quit Help: several entries match this topic - type ?2 to get match [2] [1] Tutorial: quit [2] Reference: quit [3] ITC (not loaded): quit [4] Reference: quit!in emergency [5] Reference: QUIT!emergency quit [6] Reference: QUITTING В каталоге gap4r4/doc находится подкаталог подкаталог htm, в котором нужно открыть файл index.htm – это файл многоуровневой подсказки документации по системе в HTML-формате..

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

6. Если же однозначности нет, то при повторном нажатии клавиши Tab будет предложен список всех возможных вариантов.

Сеанс работы с системой можно сохранить в текстовом файле с помощью команды LogTo("my_logfile201209.txt");.

После этого вс, что отображается на экране, будут дублироваться в файле с именем my_logfile201209.txt, который содержится в текущем рабочем каталоге. Закрыть файл протокола можно командой LogTo();

Рассмотрим пример сеанса работы в GAP.

gap x:=20;

gap y:=36;

gap n:=x+y;

gap Factors(a);

Variable: 'a' must have a value

–  –  –

ЛАБОРАТОРНАЯ РАБОТА №2.

СПИСКИ И БИНАРНЫЕ ОТНОШЕНИЯ.

ПОЛУГРУППЫ БИНАРНЫХ ОТНОШЕНИЙ И ПРЕОБРАЗОВАНИЙ

Цель работы: изучить назначение, приемы работы со списками. Построить бинарное отношение на области (домене). Определить его свойства.





Изучить свойства полугруппы бинарных отношений.

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

Набор элементов, лежащих в одном семействе, называется коллекцией. Примерами коллекций являются однородные списки, а также области/домены (domain) – так в GAP называются множества с дополнительной структурой, например, группа, полугруппа, векторное пространство и т.д. Пусть теперь С – коллекция. Тогда итepaтop Iterator(C) позволяет организовать перебор всех элементов этой коллекции без повторений.

Рассмотрим пример сеанса работы в GAP.

gap list3:=[ 1, 2, 3 ];

[ 1, 2, 3 ] gap list3[2];

gap list13:=[ list3,1, 2, 3 ];

[ [ 1, 2, 3 ], 1, 2, 3 ] gap list13[ 1 ];

[ 1, 2, 3 ] gap list_1:=[1,2,[],,,[1]];

[ 1, 2, [ ],,, [ 1 ] ] gap IsDenseList( list3 );

true gap IsDenseList( list_1 );

false gap Список состоит из объектов, разделнных запятой. Он может содержать другой список. Некоторые элементы списка могут быть пропущены. Для проверки «плотности » списка используется функция IsDenseList( ).

Матрица (Matrix) или таблица – это однородный список их элементов, принадлежащих одному семейству.

gap mat:=[ [ 1, 2 ], [ 3, 4 ] ];

[ [ 1, 2 ], [ 3, 4 ] ] gap IsTable(mat);

true gap DeterminantMat(mat);

-2 gap d4:=Domain([1..4]);

object gap Display(d4);

object gapid_1 := GeneralMappingByElements(d4,d4,List(d4,x-Tuple([x,x])));;

gap IsReflexiveBinaryRelation(id4);

true gap IsSymmetricBinaryRelation(id4);

true gap list_d4:=[Tuple([2,3]),Tuple([1,3]),Tuple([3,4])];

[ Tuple( [ 2, 3 ] ), Tuple( [ 1, 3 ] ), Tuple( [ 3, 4 ] ) ] gap r1 := GeneralMappingByElements(d4,d4,list_d4);

general mapping: object - object gaplist_1:=[Tuple([2,3]),Tuple([1,3]),Tuple([3,4]),Tuple([2,4]),Tuple([2,1 ])];

[ Tuple( [ 2, 3 ] ), Tuple( [ 1, 3 ] ), Tuple( [ 3, 4 ] ), Tuple( [ 2, 4 ] ), Tuple( [ 2, 1 ] ) ] gap r_2 := GeneralMappingByElements(d4,d4,list_1);

general mapping: object - object gap ImagesElm(r_2,2);

[ 1, 3, 4 ] gap IsSymmetricBinaryRelation( id_4 );

true gap IsSymmetricBinaryRelation( r1 );

false gap IsTransitiveBinaryRelation( r1 );

false gap IsTransitiveBinaryRelation( id_4 );

true gap IsEquivalenceRelation( id_4 );

true gap IsEquivalenceRelation( r1 );

false gap Successors( r1 );

[ [ 3 ], [ 3 ], [ 4 ], [ ] ] gap Successors( id_4 );

[ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ] gap Successors( r_2 );

[ [ 3 ], [ 1, 3, 4 ], [ 4 ], [ ] ] В примере задана матрица mat размера 2x2 с элементами 1,2,3,4 и вычислен детерминант матрицы.

Затем приведн пример определения бинарного отношения над областью из четырех элементов, состоящей из чисел 1,2,3,4. Функция Tuple([2,3]) определяет набор (кортеж) состоящий из чисел 2 и 3. Функция GeneralMappingByElements(d4,d4,list_d4); определяет общее отображение над областью d4 в виде множества пар. Это отображение может быть частично определнным, и его аргумент может иметь несколько образов.

С помощью вышеприведнных функций IsReflexiveBinaryRelation(); IsSymmetricBinaryRelation(), IsTransitiveBinaryRelation( ), IsEquivalenceRelation( ); можно проверить, является ли бинарное отношение рефлексивным, симметричным, транзитивным и отношением эквивалентности.

Функция Successors() позволяет определить второй элемент пары отношения. Функция ImagesElm(map, elm); по отображению map, выдает образ элемента elm.

Существуют специальные функции, конструирующие отношения, заданные над множеством X={1,2,…,n}, состоящим из чисел от 1 до n; ниже приведн соответствующий пример:

gap list_1:=[[1],[2],[3,4],[4]];

[ [ 1 ], [ 2 ], [ 3, 4 ], [ 4 ] ] gap b1:=BinaryRelationOnPoints( list_1 );

Binary Relation on 4 points gap ImagesElm(b1,2);

[2] gap ImagesElm(b1,3);

[ 3, 4 ] gap eb1:=EquivalenceRelationByRelation( b1 );

equivalence relation on object gap Successors( eb1 );

[ [ 1 ], [ 2 ], [ 3, 4 ], [ 3, 4 ] ] Особенно интересны отношения эквивалентности; над ними определены операции объединение, пересечение и умножение.

gap list_2:=[[1,2],[2],[3],[4]];

[ [ 1, 2 ], [ 2 ], [ 3 ], [ 4 ] ] gap b2:=BinaryRelationOnPoints( list_2 );

Binary Relation on 4 points gap eb2:=EquivalenceRelationByRelation( b2 );

equivalence relation on object gap Successors( eb2 );

[ [ 1, 2 ], [ 1, 2 ], [ 3 ], [ 4 ] ] gap ej:=JoinEquivalenceRelations(eb1,eb2);

equivalence relation on object gap Successors( ej );

[ [ 1, 2 ], [ 1, 2 ], [ 3, 4 ], [ 3, 4 ] ] gap em:=MeetEquivalenceRelations(eb1,eb2);

equivalence relation on object gap Successors( em );

[ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ] Отношение эквивалентности eb1 разбивает множество, состоящее из четырех элементов { 1, 2, 3, 4 }, на классы эквивалентности [ [ 1 ], [ 2 ], [ 3, 4 ] ], а отношение eb2 – на классы [ [ 1, 2 ], [ 3 ], [ 4 ] ]; в примере приведн результат объединения ( JoinEquivalenceRelations(eb1,eb2); и пересечения MeetEquivalenceRelations(eb1,eb2); отношений eb1 и eb2.

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

Рассмотрим пример:

gap list_2a:=[[1,5],[1,2],[1],[4,5],[5]];

[ [ 1, 5 ], [ 1, 2 ], [ 1 ], [ 4, 5 ], [ 5 ] ] gap a2:=BinaryRelationOnPoints( list_2a );

Binary Relation on 5 points gap list_2b:=[[1,5,3],[2,3],[4,2],[4,5],[5]];

[ [ 1, 5, 3 ], [ 2, 3 ], [ 4, 2 ], [ 4, 5 ], [ 5 ] ] gap b2:=BinaryRelationOnPoints( list_2b );

Binary Relation on 5 points gap s_ab:=Semigroup(a2,b2);

semigroup with 2 generators gap Size(s_ab);

gap is2:=Iterator(s_ab);

iterator gap l:= [];;

gap for i in is2 do Add( l, i ); od; l;

[ Binary Relation on 5 points, Binary Relation on 5 points, Binary Relation on 5 points, Binary Relation on 5 points, Binary Relation on 5 points, Binary Relation on 5 points, Binary Relation on 5 points, Binary Relation on 5 points, Binary Relation on 5 points, Binary Relation on 5 points, Binary Relation on 5 points ] gap Successors(l[1]);

[ [ 1, 3, 5 ], [ 2, 3 ], [ 2, 4 ], [ 4, 5 ], [ 5 ] ] В примере определены два бинарных отношения a2,b2 и этими отношениями порождена полугруппа s_ab, которая имеет 11 элементов. Итератор is2 обеспечивает цикл по элементам полугруппы без повторений.

Полугруппу образуют множество преобразований конечного множества в себя относительно операции композиция преобразований.

Рассмотрим пример:

gap t1:=Transformation( [2,3,1,4,1] );

Transformation( [ 2, 3, 1, 4, 1 ] ) gap t2:=Transformation( [2,3,4,5,1] );

Transformation( [ 2, 3, 4, 5, 1 ] ) gap s12:=Semigroup(t1,t2);

semigroup with 2 generators gap Size(s12);

Порождающими элементами полугруппы s12 являются преобразования

t1 и t2. Существует функция AsBinaryRelationOnPoints( ), которая преобразованию сопоставляет соответствующее этому преобразованию бинарное отношение:

gap rt1:=AsBinaryRelationOnPoints( t1 );

Binary Relation on 5 points gap Successors( rt1 );

[ [ 2 ], [ 3 ], [ 1 ], [ 4 ], [ 1 ] ] gap t1;

Transformation( [ 2, 3, 1, 4, 1 ] ) gap rt2:=AsBinaryRelationOnPoints( t2 );

Binary Relation on 5 points gap r12:=Semigroup(rt1,rt2);

semigroup with 2 generators gap Size(r12);

Преобразования t1 и t2, из предыдущего примера, представляются в виде бинарных отношений rt1 и rt2, понятно, что полугруппа r12 порожденная, этими бинарными отношениями изоморфна полугруппе s12.

Порядок выполнения работы.

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

2. Выполнить задание лабораторной работы для.

3. Описать действие функций (получить подсказку) по функциям BinaryRelationOnPoints(); EquivalenceRelationByRelation( ); JoinEquivalenceRelations(); MeetEquivalenceRelations();

4. Заполнить таблицу, записав в нее результаты выполнения лабораторной работы №2.

5. Какое количество элементов может иметь полугруппа всех бинарных отношений на множестве из n – элементов? Найти порождающие элементы этой полугруппы для n=3.

Содержание отчта.

1. Название и цель работы.

2. Распечатать и приложить файл протокола сеанса выполнения лабораторной работы.

Контрольные вопросы.

1. Какие свойства полугруппы использовались в лабораторной работе?

2. Сколько бинарных отношений можно задать на множестве из n – элементов?

3. Сколько отношений эквивалентности можно задать на множестве из n – элементов?

4. Что такое изоморфизм полугрупп?

5. Какими способами в GAPе можно задать отношение на области (domain)?

ЛАБОРАТОРНАЯ РАБОТА №3.

ПАКЕТЫ ПРОГРАММ ДЛЯ ПРИКЛАДНЫХ ОБЛАСТЕЙ.

ПАКЕТ automata. ФУНКЦИИ СОЗДАНИЯ АВТОМАТА,

–  –  –

ToNDAut() по регулярному выражению строят ДКА и НКА соответственно. Вывести на экран таблицу переходов автомата и начальное и конечное состояние автомата можно с помощью функции Display().

В пакете есть функции минимизации ДКА automata MinimalAutomaton( ) и редукции состояний НКА ReducedNFA( ), и детерминизации НКА, преобразования автоматов различных типов друг в друга (автоматы с -переходами в НКА), построения регулярных выражений по автоматам и проверки эквивалентности gap rae1:=ReducedNFA(nae1);

non deterministic automaton on 2 letters with 3 states gap Display(rae1);

| 1 2 3

--------------------------a|[2] [1] b|[3] [1] Initial state: [ 1 ] Accepting state: [ 1 ] Выше приведн пример редукции состояний НКА для языка, заданного регулярным выражением. Количество состояний автомата уменьшилось на два состояния, по сравнению с исходным автоматом.

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

gap sse1:=SyntacticSemigroupLang( re1 );

semigroup with 2 generators gap Size(sse1);

gap ssae1:=SyntacticSemigroupAut( ae1 );

semigroup with 2 generators gap Size(ssae1);

gap sse1=ssae1;

true gap AsList(sse1);

[ Transformation( [ 1, 2, 2, 2 ] ), Transformation( [ 1, 2, 2, 4 ] ), Transformation( [ 1, 2, 3, 2 ] ), Transformation( [ 2, 2, 1, 2 ] ), Transformation( [ 2, 2, 2, 1 ] ), Transformation( [ 2, 2, 2, 2 ] ), Transformation( [ 2, 2, 2, 3 ] ), Transformation( [ 2, 2, 2, 4 ] ), Transformation( [ 2, 2, 3, 2 ] ), Transformation( [ 2, 2, 4, 2 ] ), Transformation( [ 3, 2, 2, 1 ] ), Transformation( [ 3, 2, 2, 2 ] ), Transformation( [ 4, 2, 1, 2 ] ), Transformation( [ 4, 2, 2, 2 ] ) ] gap Idempotents(sse1);

[ Transformation( [ 1, 2, 2, 2 ] ), Transformation( [ 1, 2, 2, 4 ] ), Transformation( [ 1, 2, 3, 2 ] ), Transformation( [ 2, 2, 2, 2 ] ), Transformation( [ 2, 2, 2, 4 ] ), Transformation( [ 2, 2, 3, 2 ] ) ] Функции AsList() выдает список элементов, Idempotents() – список идемпотентов синтаксической полугруппы.

–  –  –

ToNDAut();

4. Построить минимальный ДКА и определить количество состояний для языков, указанных в п. 2.

5. Какое количество состояний может иметь минимальный реверс-ДКА (автомат для зеркального языка LR ), если минимальный ДКА для прямого языка L имеет n –состояний?

Содержание отчта.

1. Название и цель работы.

2. Распечатать и приложить файл протокола сеанса выполнения лабораторной работы.

Контрольные вопросы.

1. Какими свойствами обладает синтаксическая полугруппа регулярного языка?

2. Сколько всего ДКА с n состояниями можно построить над двухбуквенным алфавитом? Сколько неизоморфных?

3. Дайте определение подавтомата.

4. Что такое процедура детерминизации?

5. НКА имеет n состояний. Может ли ДКА, полученный после детерминизации, иметь 2n n 1 состояний? А 2n 1 состояний?

ЛАБОРАТОРНАЯ РАБОТА №4.

КОНЕЧНЫЕ ПОЛЯ. ФУНКЦИИ НАД КОНЕЧНЫМИ ПОЛЯМИ.

ПРЕДСТАВЛЕНИЕ ФУНКЦИЙ ПОЛИНОМАМИ.

Цель работы: изучить функции и программы работы с конечными полями. Построить полиномы над конечными полями. Вычислить значение полиномов точке поля.

Основными примерами полей являются конечные поля (GF), поле рациональных чисел (Rational), поле вещественных чисел и поле комплексных чисел.

Задать конечное поле в GAP можно командой GF(p^d), где p – простое число характеристика поля, d – размерность конечного поля.

У этой команды есть синонимы:

GaloisField( p^d ) GF( p^d ) GaloisField( p, d ) GF( p, d ) Ниже приведн пример, создания конечных полей из двух элементов GF(2) и поля из 13 элементов GF(13) gap f2:=GF(2);

GF(2) gap AsList(f2);

[ 0*Z(2), Z(2)^0 ] gap f13:=GF(13);

GF(13) gap AsList(f13);

[ 0*Z(13), Z(13)^0, Z(13), Z(13)^2, Z(13)^3, Z(13)^4, Z(13)^5, Z(13)^6, Z(13)^7, Z(13)^8, Z(13)^9, Z(13)^10, Z(13)^11 ] Над полем можно полиномы от одной или нескольких переменных. Для того, чтобы определить переменные рассмотрим примеры, определение переменных над полем GF(3):

gap t:=Indeterminate(GF(3),"t");

t gap Value(t*t+t+t^7,[t],[0*Z(3)]);

0*Z(3) gap Value(t*t+t+t^7+1,[t],[0*Z(3)]);

Z(3)^0 gap Value(t*t+t+t^7+Z(3)^3,[t],[Z(3)^2]);

Z(3) gap Value(t*t+t+t^7+Z(3)^3,[t],[Z(3)^3]);

Z(3)^0 gap r:=Indeterminate(GF(3),"r");

r gap Value(t*t*r+t*r+t^7*r+Z(3)^3,[t,r],[Z(3)^3,Z(3)^2]);

Z(3)^0 Определение двух переменных t,r над полем GF(3) и вычисление значения полинома с помощью функции Value( ratfun, indets, vals ) – ratfun – рациональная функция от переменных, указанных в списке indets., а значения переменных указываются списке vals.

–  –  –

Содержание отчта.

1. Название и цель работы.

2. Распечатать и приложить файл протокола сеанса выполнения лабораторной работы.

Контрольные вопросы.

1. Сколько всего гомоморфизмов имеет конечное поле?

2. Дать определение идеала кольца и определение целостного кольца.

3. Дайте определение подполя.

4. Что такое морфизм Фробениуса?

ЛАБОРАТОРНАЯ РАБОТА №5.

ИССЛЕДОВАНИЕ СВОЙСТВ

НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ

Все используемые в этой лабораторной работы термины были введены ранее либо пояснены в приложении 1. Более подробно см. [2].

Считаем, что задан некоторый недетерминированный автомат K, определяющий регулярный язык L, и при этом задан эквивалентный канонический автомат L. Для заданных объектов необходимо выполнить следующие построения.

1. Построить зеркальный (к каноническому L) автомат.

2. Канонизировать его (т. е. построить канонический к зеркальному автомату).

3. В процессе этой канонизации получить соответствие вершин обоих канонических автоматов – т. е. бинарное отношение #.

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

5. На парах полученного ранее бинарного отношения # построить базисный автомат B используя автомат L.

A,

6. Добавить дохлое состояние (пусть M ) – рассматриваемый автомат во всюду определённый (“total”).

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

8. Выполняем с последним автоматом действия, аналогичные проведённым с исходным автоматом (см. п.п. 2–5 выше).

9. В полученном базисном автомате (т. е. в базисном автомате для языкадополнения) произвольным образом выбрать какое-нибудь состояние (пусть A#X) и рассмотреть язык автомата с единственным входом A#X и единственным выходом – также A#X.

10. Для языка последнего автомата построить базисный автомат.

11. Определить отличия полученного базисного автомата от базисного автоA(L)).

мата для исходного языка (B

12. Для последнего языка также построить язык-дополнение – и сравнить базисный автомат для него с базисным автоматом для исходного языка A(L)).

(B Все программы желательно выполнять одновременно на языке GAP, а также на каком-либо процедурном объектно-ориентированном языке (Си++ и т. п.).

ЛАБОРАТОРНАЯ РАБОТА №6.

ИССЛЕДОВАНИЕ СВОЙСТВ АВТОМАТА WATERLOO

(Само определение автомата Waterloo и некоторые соответствующие обозначения приведены ниже в Приложении 1.) Для автомата Waterloo (точнее – для регулярного языка, определяемого автомата Waterloo) необходимо написать следующие программы.

1. Описать, что именно произойдёт с предполным автоматом (построенным на основе языка автомата Waterloo) в случае, если из 14 указанных ниже блоков выбираются:

• (произвольные) 8 блоков, включающие отмеченные 7;

• (произвольные) 9 блоков, включающие отмеченные 7;

•...;

• (произвольные) 13 блоков, включающие отмеченные 7 (случаи 7 и 14 блоков рассмотрены ниже).

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

Все программы желательно выполнять одновременно на языке GAP, а также на каком-либо процедурном объектно-ориентированном языке (Си++ и т. п.).

ПРИЛОЖЕНИЕ 1.

НЕМНОГО ТЕОРИИ

О НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТАХ

Основные обозначения Будем использовать следующие обозначения, согласованные с [2]. Пусть

–  –  –

некоторый недетерминированный конечный автомат, задающий регулярный язык L = L(K). Q – множество состояний, S Q и F Q – множества стартовых и финальных состояний соответственно. Функция переходов определяется либо как : Q P(Q), либо как : Q ( {}) P(Q) (в зависимости от контекста). Здесь запись P(Q) обозначает множество подмножеств множества Q.

Входной и выходной языки состояния q, т. е. языки, определяемые автоматами

–  –  –

Кроме того, состояние q1 является входным (выходным) в автомате K, тогда и только тогда, когда по крайней мере одно из состояний q1 и q2 является входным (выходным) в автомате K. Будем обозначать такой автомат записью J q1 q2 (K).

Конечно, использование операции J имеет смысл только в тех случаях, когда мы можем доказать, что исходный и получаемый автоматы (т. е. K и K ) – эквивалентны.

Для рассматриваемого языка L его канонический автомат будет обозначаться записью L.

Пусть автоматы L и LR для заданного языка L таковы:

L = (Q,,, {s }, F ) и LR = (Q,,, {s }, F ).

Будем использовать две специальные функции (in и out ), помечающие состояния автомата (1) подмножествами множеств состояний L и LR соответственно.

В данном пособии достаточно рассматривать следующий упрощённый вариант такого определения. А именно, мы полагаем in (q) A тогда и только тогда, K u u когда существует некоторое слово u, такое что q и A; аналогичK BA(L) но для функции out. Заметим, что это определение – конструктивно, т. е. оно K может быть переформулировано как алгоритм такого построения; ниже будут рассмотрены примеры.

Далее рассматриваем специальное бинарное отношение #, заданное на декартовом произведении Q Q, которое относится к заданному регулярному языку (а не к конкретному автомату для него). Наиболее просто это отношение может быть получено путём построения функции in, рассматриваемой для автомата, зеркального к каноническому для заданного языка. Заметим также, что пары состояний, удовлетворяющие отношению #, могут рассматриваться как состояния базисного автомата для заданного языка.

Отношение # также формирует множество псевдоблоков (псевдо-гридов); фактически каждый из них представляет собой пару (P, R) (где P Q и R Q ), такую что для каждой пары состояний p P и r R выполнено условие p#r.

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

Каждый из таких псевдоблоков соответствует некоторому состоянию некоторого автомата для заданного языка. Однако в реальных задачах теории формальных языков подобные множества псевдоблоков содержат очень большое число элементов: например, для блока, состоящего из 4 строк и 3 столбцов, мы получаем (24 1) · (23 1) = 105 псевдоблоков. Одна из рассматривающихся проблем – это задача вершинной минимизации недетерминированных конечных автоматов, т. е. задача построения автомата, определяющего заданный регулярный язык и имеющего минимально возможное число состояний.

Подробное рассмотрение простого примера

Для рассматриваемого нами автомата мы строим одновременно:

–  –  –

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

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

• все пары состояний автомата L;

• а также специальный символ F; он означает, что два состояния – неэквивалентны (причём этот факт известен в начале работы алгоритма).

Для двух различных состояний G и H полагаем {G, H} F (ниже будем упрощённо писать GH вместо {G, H}) тогда и только тогда, когда ровно одно из этих двух состояний является финальным. А для четырёх состояний G1, H1, G2 и H2 (где G1 = H1 и G2 = H2 ) мы полагаем G1 H1 G2 H2 (или G1 H1 H2 G2, это одно и то же) если существует по крайней мере одна буква c, такая что c c G1 G2 и H1 H2.

Итак, в этом примере для описания бинарного отношения нам следовало бы использовать таблицу, имеющую 20 строк (для пар состояний AB,..., EF ) и 21 столбцов (для тех же самых пар, а также специального символа F). Однако подобная таблица – слишком велика, и мы будем рассматривать её упрощённую версию.

А именно, мы сначала применим тот факт, что ни состояние A, ни состояние B не может быть эквивалентно никакому другому состоянию:

• A не может быть эквивалентно, поскольку оно не является финальным – в отличие от всех остальных состояний;

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

Поэтому мы можем рассматривать таблицу, имеющую 6 строк (для пар состояний CD,...

, EF ) и 7 столбцов (для тех же пар и символа F); получающаяся таблица такова:

–  –  –

В её ячейках мы не используем 1 и 0; вместо этого мы пишем либо два разных возможных перехода последнего автомата (и этот факт означает, что отношение выполнено), либо – (что означает отсутствие такого перехода, при этом отношение не выполнено). Аналогично для последнего столбца: все использующиеся в этой таблице состояния суть финальные, поэтому мы записываем в клетке возможный переход в A или B (которые не эквивалентны другим состояниям) – если он имеется в точности для одного из двух состояний рассматриваемой строки.

Далее заменим пустые клетки на 0, а непустые – на 1, после чего построим транзитивное замыкание +.

3 При этом мы получаем следующую таблицу 5:

–  –  –

Согласно её последнему столбцу мы получаем, что состояния C, E и F являются эквивалентными, а состояние D им не эквивалентно.

На основе последнего полученного условия мы можем переписать таблицу 3, получая при этом следующую таблицу 6 для эквивалентного канонического автомата:

–  –  –

В последней таблице мы пометили состояния – состояниями заданного автомата, соответственно таблице 2.

Однако обычно нам нужны не такие пометки – а инверсные ; выполнив для этого аналогичные действия, мы получаем следующую функцию in :

–  –  –

Рассмотрим следующие два рисунка: полученный автомат L (рис. 2) и зеркальный к нему (L)R (рис. 3). Простейший путь построения бинарного отношения # состоит в повторном использовании процедуры канонизации – а именно, в построении автомата LR на основе автомата (L)R.

Мы при этом получаем несколько равных 1 элементов на главной диагонали, однако это непринципиально.

–  –  –

Теперь необходимо получить множество эквивалентных состояний. Для этого составим таблицу 10 – бинарного отношения для последнего автомата: 6 Специально отметим, что состояние C не является стартовым.

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

Метод построения описан выше.

Как и ранее, заменим пустые клетки на 0, а непустые – на 1.

После этого выполним транзитивное замыкание и получим бинарное отношение + в виде следующей таблицы 11:

–  –  –

Каждая клетка последнего столбца содержит 1 – поэтому эквивалентных состояний в данном случае нет. Поэтому мы действительно можем считать автомат, приведённый в таблице 9, каноническим – т. е.

LR :

–  –  –

Однако мы не будем приводить множество псевдоблоков, это множество слишком велико: например, первый блок определяет (23 1) · (22 1) = 21 псевдоблок. 8 Автомат Waterloo. Предварительные построения В этом подразделе мы подробно рассмотрим более сложный пример. Он покажет, среди прочего, как можно определить неравенство двух рассматриваемых языков (заданного регулярного языка и языка заданного конечного автомата, т. е. в использовавшихся ранее обозначениях – L(K) и L) – причём без построения эквивалентных канонических автоматов. Однако для этого нам придётся однократно построить оба таких канонических автомата.

Рассматривая этот пример, мы одновременно докажем возможность выполнения следующего условия.

–  –  –

Рис. 5 Заметим, что мы можем все элементы отношения # тремя блоками, обозначенными нами ранее, и. Более того, существует также множество (собственно) псевдо блоков, имеющееся то же самое свойство; фактически рассматриваемый пример и показывает такое покрытие. (Это замечание прежде всего относится к построению эвристических алгоритмов вершинной минимизации недетерминированных конечных автоматов, и мы не будем подробно его рассматривать.) Этот автомат – детерминированный. Более того, несложно показать, что в нём отсутствуют эквивалентные состояния – поэтому для задаваемого им регулярного языка он является каноническим автоматом, и мы можем обозначать его записью L. Удобно рассматривать этот автомат в виде следующей таблицы 13.

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

–  –  –

Для получения автомата LR, как и ранее, удобнее всего провести процедуру детерминизации для автомата (L)R. Автомат (L)R приведён в виде таблицы 14;

он – недетерминированный, поэтому мы должны рассматривать содержимое каждой её клетки только в качестве множества состояний.

–  –  –

Продетерминируем автомат (L)R. Вначале мы рассматриваем только одно входное состояние; удобно обозначить его записью E, F (аналогично будем поступать ниже). Это входное состояние соответствует множеству {E, F }, и, следовательно, оно может быть получено путём объединения соответствующих строк автомата (L)R (т. е. строк для состояний E и F ). Далее мы получаем существование множества состояний (либо состояния нового автомата) A, B – и, следовательно, включаем в строимый автомат соответствующую строку; и т. д.

Финальные (выходные) состояния – те, которые содержат единственное выходное состояние A автомата (K)R ; это – A и A, B.

Итак, полная таблица 15 соответствующего детерминированного автомата содержит 10 состояния, включая 2 старых состояния A и C (как и ранее, мы для удобства приводим состояния в таблице в порядке их появления ). А произведя переобозначение состояний, мы получаем таблицу 16.

Очевидно, что в последнем автомате нет эквивалентных состояний, следовательно он может рассматриваться в качестве канонического.

В процессе этого переобозначение состояний мы также получаем следующую таблицу 17 бинарного отношения # 9 :

–  –  –

Ниже мы будем использовать в точности эти номера состояний, например – для автомата COM(L). 10 Итак, построим автомат COM(L), используя полученные множества блоков.

Для этого сначала построим таблицы 18 and 19 – для обоих букв рассматриваемого алфавита. В обеих этих таблицах:

• строки (см. их пометки в столбце “q”) помечены состояниями автомата COM(L);

Она может быть получена, например, следующую way. Например, в автомате, приведённом на обеих таблицах 15 и 16, мы переобозначили состояние {E, F } буквой X; отсюда мы получаем E#X и F #X. Аналогичная операция должна быть произведена для всех новых состояний.

Мы не будем приводить строгого определения этого автомата. Один из возможных алгоритмов его построения приведён далее.

• Q (значения функции переходов) получены путём объединения значений Q (q, a) (либо Q (q, b) для второй таблицы) для множества пометок состояний рассматриваемой строки;

• кандидаты для – это состояния, которые удовлетворяют т.н. первому условию, т.е.

q (B1 ) ( (q, a) = {q }) (q (B2 )), где блок B1 является пометкой рассматриваемой строки, а B2 – пометка рассматриваемого столбца; например, в строке, помеченной 3 (таблица 18) мы пишем, в частности, 10 – поскольку блоки 3 (т. е. B1 = {B} {Y, V }) и 10 (т. е. B2 = {F, G} {Z, R}) удовлетворяют указанному здесь условию;

• переходы – это окончательные ответы, т. е. мы записываем в этом столбце те состояния автомата COM(L), которые удовлетворяют обеим условиям

– первому и второму – т.е., дополнительно к предыдущему, ещё и условию q (B2 ) ( (q, a) = {q }) (q (B1 )).

–  –  –

Таблица 21 показывает процесс детерминизации автомата COM(L). Эта таблица может быть использована ещё и для построения функций in и out последнего автомата.

–  –  –

Ниже мы будем использовать также базисный автомат для этого языка; однако мы приведём только саму таблицу функции переходов, без подробного рассмотрения процесса её построения.

Итак, BA(L) может быть задан следующим образом :

–  –  –

Для этого рассмотрим следующее подмножество множества блоков, соответствующих таким состояниям автомата COM(L):

1, 3, 5, 6, 8, 10, 12; (3) Для удобства мы делим запись её 20 строк на две части и, кроме того, записываем состояния A типа X в виде A#X.

Не очень понятно, как переводить слово “badness” на русский язык. Предлагаемый словарями перевод плохость звучит не по-русски, а наиболее точный перевод ( бяка ) вряд ли уместен в строгих текстах. Отметим, что в руководствах по системе TeX это слово часто не переводится.

Рассмотрим этот момент более подробно – на примере. Состоянию 10 автомата, приведённого на таблицах 18 и 19, соответствуют следующие значения функции разметки состояний:

in (10) = {F, G} и out (10) = {Z, R}. Следовательно, это состояние покрывает следующие K K элементы отношения #: F #Z, F #R, G#Z и G#R. Существуют возможные подмножества множеств таких состояний, для которых соответствующие пары (типа F #Z в нашем примере) покрывают все элементы рассматриваемого отношения #.

очевидно, что все 20 элементов отношения # (таблица 17) при этом покрыты. 15

–  –  –

Сформировав все возможные дуги, мы получаем автомат, приведённый в таблице 23. 16 После его детерминизации мы получаем таблицу 24, а после переобозначения её состояний следующим естественным способом –

–  –  –

– получаем автомат, приведённый в таблице 25. Очевидно, что он не эквивалентен исходному – поскольку его состояние F не содержит перехода по букве a, а при этом все остальные входы, выходы и переходы совпадают с соответствующими объектами исходного автомата.

Итак, мы, среди прочего, рассмотрели обычный алгоритм проверки неравенства L(K) = L. Однако мы можем описать и другой алгоритм, предназначенный для той же цели, т. е. алгоритм, на основе которого мы можем в некоторых частных случаях утверждать, что L(K) = L: если для некоторого цикла автомата B A(L) мы можем доказать отсутствие соответствующего ему цикла в автомате K, то L(K) = L. Очень важно отметить, что при этом нет необходимости строить эквивалентные канонические автоматы.

В данной ситуации таковым является рассмотренный ранее цикл (2). Для автомата, приведённого в таблице 20, мы получаем следующее соответствие состояний автоматов BA(L) и COM(L):

B

• соответствует состояниям 2 и 3;

Y F

• соответствует состояниям 8 и 9;

P B

• соответствует состояниям 3 и 4;

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

Другой способ построения того же самого автомата заключается в удалении состояний из автомата COM(L) – тех состояний, которые не принадлежат выбранному нами покрывающему множеству. При этом, конечно, удаляются и все соответствующие дуги.

F

• соответствует состояниям 9 и 10.

Z

–  –  –

ПРИЛОЖЕНИЕ 2.

КРАТКИЙ СЛОВАРЬ ОСНОВНЫХ ТЕРМИНОВ

Алгебра. Алгеброй над полем K называется множество A с операциями сложения, умножения и умножения на элементы поля K, обладающее следующими свойствами:

относительно сложения и умножения на элементы поля K множество A – линейное пространство;

относительно сложения и умножения A – кольцо, при этом умножение (a)b (ab) a(b) ассоциативно для любых K и a, b A.

Бинарное отношение R – подмножество R X X декартового произведения множества X на себя.

Кольцо.

Кольцом называется множество K с операциями сложения и умножения со следующими свойствами:

относительно сложения множество K – абелева группа, умножение дистрибутивно относительно сложения a(b c) ab ac и (a b)c ac bc для любых a, b, c K.

Конечный автомат K = (Q,,,S, F ) – это пятрка, где Q – конечное множество состояний, – конечный алфавит, – функция переходов, S – множество начальных состояний, F – множество заключительных состояний.

Поле – коммутативное ассоциативное кольцо с единицей, в котором всякий ненулевой элемент обратим.

Полугруппа S – множество S с заданной на нм бинарной ассоциативной операцией.

ЛИТЕРАТУРА

1. Хорпкрофт Дж., Мотвани Р., Ульман Дж. «Введение в теорию автоматов, языков и исчислений». – М., изд-во «Вильямс», 2008. – 528с.

2. Мельников Б.Ф. «Недетерминированные конечные автоматы», Тольятти, изд-во ТГУ, 2009. – 161 с.

3. Лаллеман Ж. «Полугруппы и комбинаторные приложения». – М. Мир, 1985. – 440 с.

4. Паун Г., Розенберг Г., Саломаа А. «ДНК-компьютер. Новая парадигма вычислений». – М., Мир, 2004. – 528 c.

5. Шафаревич И.Р. «Основные понятия алгебры». – Итоги науки и техники. Современные проблемы математики. Т 11. – М. ВИНИТИ, 1986.

6. Бирхгоф Г., Барти Т. «Современная прикладная алгебра». – СПб, изд-во «Лань», 2005. – 400 с.

7. Ван дер Ванден Б.Л. «Алгебра». М., Мир, 1976. – 648 с.

ССЫЛКИ В ИНТЕРНЕТ

1. http://www.gap-system.org

2. http://ukrgap.exponenta.ru

–  –  –

Оригинал макет подготовлен в научно-образовательном центре «Математические модели и теоретические основы классической и квантовой информатики»

ФГБОУ ВПО «Тольяттинский государственный университет»

445667, г. Тольятти, ул. Белорусская, 14.

Отпечатано с оригинал-макета в ООО «Колор-Принт»

432063, г. Ульяновск, ул.Ленина, 75



Похожие работы:

«Вычислительные технологии Том 12, № 5, 2007 ИССЛЕДОВАНИЕ (m, 2)-МЕТОДОВ РЕШЕНИЯ ЖЕСТКИХ СИСТЕМ E. A. Новиков Институт вычислительного моделирования СО РАН, Красноярск, Россия e-mail: novikov@icm.krasn.ru The (m, 2)-methods are investigated. It has been shown that the maximum order of accuracy for the L-stable (m, 2...»

«М.Б.Игнатьев, Т.С.Катермина КОНТРОЛЬ И КОРРЕКЦИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ В РЕАЛЬНОМ ВРЕМЕНИ НА ОСНОВЕ МЕТОДА ИЗБЫТОЧНЫХ ПЕРЕМЕННЫХ Учебное пособие Издательство Нижневартовского государственного университета ББК 32.972.11 И 26 Печатается по постановлению редакционно-издательского...»

«Корнеева Мария Геннадьевна ХАРАКТЕРИСТИКА ЭЛЕКТРОННОГО ДЕЛОВОГО ПИСЬМА С ПОЗИЦИИ ЖЕСТКОСТИ / ГИБКОСТИ И ФАТИКИ / ИНФОРМАТИКИ (НА МАТЕРИАЛЕ АНГЛИЙСКОГО ЯЗЫКА) В статье представляется градуальная характеристика речевого жанра электронного делового письма на примере полюсов жесткости...»

«Санкт-Петербургский государственный университет Кафедра технологии программирования Садреева Юлия Ильдаровна Выпускная квалификационная работа бакалавра Автоматическая классификация новостей из коллекции Reuters в таксономию IPTC Направление 01040...»

«Проблемы старения и долголетия, 2016, 25, № 1. – С. 50—58 УДК 612.67 В. И. Гудошников, Л. Ю. Прохоров* Совет Международного общества DOHaD, 97050-500 Санта-Мария, штат Рио-Гранди-ду-Сул, Бразилия *Московский государственный университет им. М. В. Лом...»

«Инструкция для радиостанции Yaesu FT-60R 1.СОДЕРЖАНИЕ Сканирование метеостанций Введение Программируемое (по диапазону) сканирование Аксессуары и Опции памяти Управление и Подключения Сканирование "Приоритетного канала" (двойное Верхняя и Передняя панели...»

«Матвеева Наталья Викторовна ОБУЧЕНИЕ ДЕЛОВОМУ ОБЩЕНИЮ НА АНГЛИЙСКОМ ЯЗЫКЕ В НЕЯЗЫКОВОМ ВУЗЕ: ДИСКУССИЯ ЗА КРУГЛЫМ СТОЛОМ ПО ТЕМЕ СЕРВИС НА ЖЕЛЕЗНОДОРОЖНОМ ТРАНСПОРТЕ В статье рассматриваются вопросы организации информативного, продуктив ного и конструктив ного общения на занятиях по английскому языку в неязыковом в узе в ходе подготовки...»

«Воронцов Константин Вячеславович Локальные базисы в алгебраическом подходе к проблеме распознавания Специальность 01.01.09 математическая кибернетика АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук Москва – 1999 Работа выполнена в Вычислите...»

«Информационные процессы, Том 16, № 2, 2016, стр. 91–102 2016 Бедринцев, Чепыжов. c МАТЕМАТИЧЕСКИЕ МОДЕЛИ, ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ Выпуклая аппроксимация пространства дизайна в задаче оптимизации крыла самолета1 А.А.Бедринцев,...»

«Министерство образования и науки Украины Харьковский национальный университет имени А.Н. Бекетова Кафедра прикладной математики и информационных технологий. Информатика и основы компьютерно...»

«Секция 3: Автоматизация, информатизация и менеджмент на предприятии 5. Новиков Е.А. Явные методы для жестких систем. – Новосибирск: Наука. Сиб. Предпр. РАН, 1997.– 195 с.6. Nasyrova...»

«Документ с сайта http://ai-center.botik.ru/planning. * Значимый контекст рассуждений в задаче планирования Трофимов Игорь Владимирович1 Автоматическое планирование – задача высокой вычислительной сложности. Универсальные классические планировщики, опирающиеся на эври...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.