Функциональные системы полиномов и их применение в программировании для вычислительных систем и сетей тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Мамонтов, Андрей Игоревич

• Мамонтов, Андрей Игоревич
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Мамонтов, Андрей Игоревич

1 Введение

1.1 Предварительные замечания.

1.2 Линейные полиномы и параллельные вычисления.

1.3 О функциональных системах.

1.4 Некоторые прикладные вопросы.

1.5 Основные результаты

2 Необходимые определения

2.1 Проблема полноты в функциональных системах полиномов

3 Функциональная система линейных полиномов с целыми неотрицательными коэффициентами

3.1 Проблема полноты в классе Ь(Щ.

3.2 Класс L0(N).

3.3 Класс Li(N).

3.4 Класс L+(N)

3.5 Некоторые замечания о проблеме выразимости в классе L(N)

4 Функциональная система линейных полиномов с целыми коэффициентами

4.1 Классы F(k) и LF(k).

4.2 Классы L+ и F+(k)

4.3 Классы Lc+ и Ld~.

4.4 Классы С(т).

4.5 Классы S0(k) и Si(k).

4.6 Классы FS{k).

4.7 Класс D.

4.8 Классы U{a,b).

4.9 Критерий полноты.

4.10 Некоторые свойства базисов. Алгоритмическая разрешимость проблемы полноты.

5 Функциональная система линейных полиномов с рациональными коэффициентами

5.1 Класс O(Q).

5.2 Класс L+(Q)

5.3 Класс CP(Q).

5.4 Класс E(Q).

5.5 Классы Ua(Q).

5.6 Класс M(Q).

5.7 Критерий относительной полноты.

5.8 О глубине классов L(N) и Ь(Ъ) в L(Q).

5.9 О глубине класса L(Q) в P(Q).

5.10 Мощность некоторых множеств замкнутых классов в L(N), L(Z) и L(Q).

6 О реализации систем булевых функций арифметическими полиномами

6.1 Арифметические полиномы.

6.2 Связь и множества арифметических полиномов

6.3 Связь L(Z) и множества линейных арифметических полиномов

6.4 Библиотека для работы с логическими функциями и арифметическими полиномами.

7 Линейные полиномы и их применение в искусственных нейронных сетях.

7.1 Искусственный нейрон.

7.2 Предложения по распараллеливанию вычислений нейронной сети

7.3 Распараллеливание вычислений нейросети в задаче распознавания образов.

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

7.4.1 О хранении коэффициентов.

7.4.2 Об организации эффективных вычислений.

Введение диссертации (часть автореферата) на тему «Функциональные системы полиномов и их применение в программировании для вычислительных систем и сетей»

1.1. Предварительные замечания

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

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

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

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

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

В соответствии с целью исследования были поставлены следующие конкретные задачи:

1. Исследовать функциональные системы линейных полиномов.

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

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

4. Сравнить результаты применения составленных программ с существующими аналогами.

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

Практическая значимость работы.

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

Обоснованность и достоверность результатов. Реультаты диссертации обоснованы математически, и их достоверность подтверждена экспериментально.

Апробация работы. Результаты работы докладывались и обсуждались на:

1. Научной сессии МИФИ, Москва, 2003, 2004, 2005;

2. Девятой, десятой, одиннадцатой, двенадцатой и тринадцатой международных научно-технических конференциях студентов и аспирантов „Радиоэлектроника, электротехника и энергетика", Москва, 2003, 2004, 2005, 2006, 2007;

3. Девятой международной конференции „Интеллектуальные системы и компьютерные науки", Москва, 2006;

4. Шестой и седьмой международных конференциях „Дискретные модели в теории управляющих систем", Москва, 2004, 2006;

5. Научном семинаре кафедры Математической кибернетики факультета ВМиК МГУ.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Мамонтов, Андрей Игоревич

Заключение.

Итак, в работе получены следующие основные результаты.

1. Исследованы функциональные системы L(N), L{Z) и L(Q) линейных полиномов с целыми неотрицательными, целыми и рациональными коэффициентами и операцией суперпозиции и установлены следующие теоретические результаты.

1.1. Найдены полные системы в замкнутых классах L(N), L(Z), L(Q).

1.2. Установлены необходимые и достаточные условия полноты в каждой из систем L(N), L(Z), L(Q).

1.3. Построен алгоритм распознавания полноты в L(Z), оценена его сложность.

1.4. Найдены все возможные значения мощности базисов в этих функциональных ситемах.

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

2.1. Найден базис, позволяющий эффективно вычислять значения полиномов, в которых большинство коэффициентов делятся на 4.

2.2. Найдено семейство базисов с тремя параметрами, подбирая которые можно эффективно вычислять целочисленные полиномы.

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

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

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

4. Создана программная библиотека для оперирования с арифметическими полиномами и решения названных технических задач.

5. Проведён вычислительный эксперимент, подтверждающий преимущества предложенных методов.

Список литературы диссертационного исследования кандидат технических наук Мамонтов, Андрей Игоревич, 2007 год

1. Алексеев В.Б., Вороненке А.А. О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика.— 1994.— т. 6, №4,- С. 58-79.

2. Андреева О.В., Голунков Ю.В. Программно-замкнутые классы функций алгебры логики и предикатов // Кибернетика.— 1981.— №1.— С. 133.

3. Арутюнян Л.А. О мощности следов классов неоднородных функций // Дискретная математика.— 1993.— т. 5, №3.— С. 35-39.

4. Арутюнян J1.А. О решётке замкнутых классов неоднородных функций со следом типа С // Дискретная математика.— 1993.— т. 5, J№1.— С.130-145.

5. Бабин Д.Н. О разрешимости проблемы полноты для специальных систем автоматов // Дискретная математика.— 1996.— т. 8, №4.— С. 7991.

6. Бабин Д.Н. Разрешимый случай задачи о полноте автоматных функций // Дискретная математика.— 1992.— т. 4, №4.— С. 41-56.

7. Бабин Д.Н. Эффективная проверяемость полноты систем автоматных функций с полной булевой частью // Дискретная математика.— 2003.— т. 15, №1- С. 110-130.

8. Буевич В.А. О т-полноте в классе автоматных отображений // Доклады АН СССР.- 1980.- т. 252, № 5.- С. 708-712.

9. Буевич В.А. Условия Л-полноты для конечных автоматов.— М: Изд-во МГУ, Часть 1, 1986. Часть 2, 1987.

10. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео.— М: ДИАЛОГ-МИФИ, 2002.

11. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления.— СПб: БХВ-Петербург, 2004.

12. Выхованец B.C., Малюгин В.Д. Мультипликативная алгебра и ее применение в логической обработке данных // Проблемы управления.— 2004.-№3.- С. 67-77.

13. Гаврилов Г. П. Вопросы выразимости и мощностной характеризации для дискретных функциональных систем с операцией суперпозиции: Дисс. докт. физ.-мат. наук.— М., 1997.

14. Гаврилов Г.П. Индуктивное представление булевых функций и конечная порождаемость классов Поста // Алгебра и логика.— 1984.— т. 23, №1- С. 3-26.

15. Гаврилов Г.П. О функциональной полноте в счётнозначной логике // Проблемы кибернетики.— 1965.— вып. 15.— С. 5-64.

16. Гаврилов Г.П. Функциональные системы дискретной математики,— М: Изд-во МГУ, 1985.

17. Глушков В.М., Цейтлин Г.Е., Ющенко E.JI. Алгебра. Языки. Программирование.— Киев: Наукова думка, 1978.

18. Голунков Ю.В. Аппроксимационная полнота в алгебрах частично рекурсивных функций и предикатов // Кибернетика.— 1987.— JVe. 6.— С.26-30.

19. Голунков Ю.В. К теории систем алгоритмических алгебр // Доклады АН СССР.- 1997.- т. 232, Ж 4.- С. 749-752.

20. Голунков Ю.В. О полноте операций в системах алгоритмических алгебр // В кн.: Алгоритмы и автоматы.— М: Изд-во Казанского ун-та, 1978.— С. 11-53.

21. Голунков Ю.В. Полнота по модулю идеала в функциональных системах программного типа // Дискретная математика.— 1990.— т. 2, Ж 2.— С. 112-120.

22. Голунков Ю.В. Полнота систем операций в операторных алгебрах, реализующих функции к-значной логики // Вероятностные методы и кибернетика 1980 - вып. 17 - С. 23-34.

23. Горбат А.Н. Обобщенная апрокеимационная теорема и точное представление многочленов от нескольких переменных суперпозициями многочленов от одного переменного // Известия вузов. Математика.— 1998 -№5 С. 6-9.

24. Дарсалия В.Ш. О базисах функциональных систем полиномов // Фундаментальная и прикладная математика.— 2001.— т. 7, №3.— С. 673682.

25. Дарсалия В.Ш. О мощностях множеств всех предполных классов в функциональных системах полиномов // Теоретические проблемы информатики и её приложения.— 1997.— № 1.— С. 35-44.

26. Дарсалия В.Ш. Об алгоритмической разрешимости свойства выразимости для полиномов // Фундаментальная и прикладная математика.— 1999.-т. 5, №3.- С. 931-935.

27. Дарсалия В.Ш. Относительная полнота для функциональных систем полиномов // Фундаментальная и прикладная математика — 2002.— т. 8, №4,- С. 967-977.

28. Дарсалия В.Ш. Проблема полноты для функциональных систем полиномов: Дисс. канд. физ.-мат. наук.— М., 1998.

29. Дарсалия В.Ш. Условия полноты для полиномов с натуральными, целыми и рациональными коэффициентами // Фундаментальная и прикладная математика.— 1996.— т. 2, №2.— С. 365-374.

30. Дзюжанъски П., Малюгин В., Шмерко В., Янушкевич С. Линейные модели схем на многозначных элементах // Автоматика и телемеханика 2002 - №6.- С.99-119.

31. Доу Ж. Вопросы полноты для конечно порождённых систем (P^fi) и {Pkj2,fi> // Дискретная математика — 1990 — т.2, №4 С. 116-124.

32. Доу Ж. Вопросы полноты для конечно порождённых ф.с. (Р^,^) и (Р№, 6) // Дискретная математика 1990 - т. 2, №3 - С. 128-136.

33. Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел.— М: Наука, 1965.

34. Захарова Е.Ю., Кудрявцев В.В., Яблонский С.В. О предполных классах в Ахзначных логиках // Докл. АН СССР— 1969 — т. 186, №3 — С. 509-512.

35. Иорданский М.А. Структура и способы порождения замкнутых классов графов // Дискретная математика.— 2003.— т. 15, № 3.— С. 105-116.

36. Иорданский М.А. Функциональный подход к представлению графов // Доклады РАН.- 1997.- т. 353, №3.- С. 303-305.

37. Кнут Д.Э. Искусство программирования.— т. 2, Получисленные алгоритмы — М: Мир, 1976.

38. Коблиц Н. Курс теории чисел и криптографии.— 2001.— М.: Научное изд-во ТВП, 2001.

39. Коляда К.В. О полноте регулярных отображений // Проблемы кибернетики — 1984.— вып. 41 — С. 41-47.

40. Кратко М.И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов // Доклады АН СССР.— 1964.— т. 155, К0-1 — С. 35-37.

41. Крохин А.А., Сафин К.Л., Суханов Е.В. О строении решётки замкнутых классов полиномов // Дискретная математика.— 1997.— т. 9, № 2.— С. 24-39.

42. Кудрявцев В. Б. О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами // Доклады АН СССР.- 1963.- т. 151, №3.- С. 493-496.

43. Кудрявцев В.Б. О функциональной системе // Доклады АН СССР.- 1973.- т. 210, №3.- С. 521-522.

44. Кудрявцев В.Б. О функциональной системе Ркд // Дискретная математика 1993 - т. 3, №3.- С. 124-134.

45. Кудрявцев В.Б. Относительно функциональной системы Ре // Журнал вычислительной математики и математической физики.— 1974.— т. 14, № 1.— С. 198-208.

46. Кудрявцев В.Б. Относительно функциональных систем // Проблемы кибернетики.— 1984.— вып. 41,— С. 5-40.

47. Кудрявцев В.Б. Функциональные системы.— М: Изд-во МГУ, 1982.

48. Кудрявцев В.В. О функциональной системе пучков логических функций // Фундаментальная и прикладная математика.— 1999.— т. 5, №1.- С. 149-192.

49. Кузнецов А. В. О проблемах тождества и функциональной полноты для алгебраических систем // Труды Третьего Всесоюзного матем. съезда.- М.: Изд-во АН СССР, 1956 т. 2, 145-146.

50. Кузнецов А.В. Структуры с замыканием и критерии функциональной полноты // Успехи математических наук.— 1961.— т. 16, вып. 2.— С. 201-202.

51. Кутепов В.П. Функциональные системы и параллельные вычисления: Дисс. докт. техн. наук.— М., 1981.

52. Летичевский А.А. Условия полноты для конечных автоматов // Журнал вычислительной математики и математической физики.— 1961.— №4.- С. 702-710.

53. Лисовик Л.П. Алгебры полилинейных преобразований над размеченными деревьями // Вычислительные системы.— 1988.— вып. 124.— С.114-143.

54. Ло Чжу Кай. Максимальные замкнутые классы в множестве частичных функций многозначной логики // Кибернетический сборник.— 1988.- вып. 25.- С. 131-141.

55. Ло Чжу Кай. Теория полноты для частичных функций многозначной логики // Кибернетический сборник.— 1988.— вып. 25.— С. 142-161.

56. Малюгин В.Д. Параллельные логические вычисления посредством арифметических полиномов.- М: ФИЗМАТЛИТ, 1997.

57. Мамонтов А.И. Алгоритм распознавания полноты в алгебре линейных полиномов с целыми коэффициентами // Тез. докл. XII Междунар.науч.-техн. конф. "Радиоэлектроника, электротехн. и энергетика. Т. 1." М: Изд-во МЭИ.- 2006.- С. 371-372.

58. Мамонтов А.И. Исследование структуры замкнутых классов в функциональной системе линейных полиномов с целыми неотрицательными коэффициентами // Вестник МЭИ 2006.—№6 — С. 83-90.

59. Мамонтов А.И. Исследование структуры подалгебр в алгебрах полиномов с целыми коэффициентами // Тез. докл. IX Междунар. науч.-техн. конф. "Радиоэлектроника, электротехн. и энергетика. Т. 1." — М: Изд-во МЭИ,- 2003.- С. 263-264.

60. Мамонтов А.И. Критерий полноты в алгебре линейных полиномов с целыми коэффициентами // Тез. докл. X Междунар. науч.-техн. конф. "Радиоэлектроника, электротехн. и энергетика. Т. 1." — М: Изд-во МЭИ.- 2004.- С. 286-287.

61. Мамонтов А.И. Некоторые возможные применения алгебр полиномов с целыми коэффициентами // Научная сессия МИФИ-2005. Сб. научн. трудов. Т. 14. М: МИФИ, Москва, 2005.- С. 52-53.

62. Мамонтов А.И. О проблеме полноты в функциональной системе линейных полиномов с рациональными коэффициентами // Интеллектуальные системы и компьютерные науки. Девятая Междунар. конф. Т. 1 Часть 1 М: МехМат МГУ.- 2005.- С. 183.

63. Марченков С.С. Замкнутые классы булевых функций.— М: ФИЗМАТ-ЛИТ, 2000.

64. Марченков С. С. К существованию конечных базисов в замкнутых классах булевых функций // Алгебра и логика.— 1984.— т. 23, № 1 — С. 8899.

65. Марченков С.С. 5-классификация функций многозначной логики // Дискретная математика,— 1997.— т. 9, №3.— С. 125-152.

66. Марченков С. С. 5-классификация функций трёхзначной логики.— М: ФИЗМАТЛИТ, 2001.

67. Марченков С. С. О предполных классах в декартовых произведениях Р2 и Р3 // Дискретная математика — 1994 — т. 6, №2 — С. 21-42.

68. Марченков С.С. О предполных классах Слупецкого в системах х х . х xPi // Дискретная математика 1992 — т. 4, № 3 — С. 135-148.

69. Марченков С. С. Предполнота замкнутых классов в Рк: предикатный подход // Математические вопросы кибернетики.— 1996.— вып.6.— С. 117-132.

70. Марченков С.С., Угольников А.Б. Замкнутые классы булевых функций.- М: Изд-во ИПМ АН СССР, 1990.

71. Мещанинов Д.Г. О первых с?-разностях функций &-значной логики // Математические вопросы кибернетики.— 1998 — вып. 6 — С. 265-280.

72. Мещанинов Д.Г. О замкнутых классах к-значных функций, сохраняющих первые d-разности // Математические вопросы кибернетики.— 1999,- вып. 8.- С. 219-230.

73. Перфильева И.Г. Построение гиперконтинуального семейства предполных классов счётнозначной логики // Проблемы кибернетики.— 1979.— т. 35.- С. 29-44.

74. Ромов Б.А. О максимальных подалгебрах алгебры частичных функций многозначной логики // Кибернетика.— 1980.— № 1.— С. 28-36.

75. Ромов Б.А. О полноте на квадрате функций алгебры логики и в системе Рк х Pi // Кибернетика 1987 - №4.- С. 9-14.

76. Ромов Б.А. Об одной серии максимальных подалгебр прямых произведений алгебр конечнозначных логик // Кибернетика.— 1987.— №3.—1. С. 11-16.

77. Семигродских А.П. Решётки замкнутых классов функций на бесконечном множестве: Дисс. канд. физ.-мат. наук.— Екатеринбург., 2003.

78. Тайманов В.А. О декартовых степенях Р2 // Доклады АН СССР.— 1983.- т. 270, № 6,- С. 1327-1330.

79. Тайманов В.А. О функциональных системах А;-значной логики с операциями программного типа // Доклады АН СССР.— 1983.— т. 268, №6.- С. 1307-1310.

80. Тарасова О. С. Классы fc-значной логики, замкнутые относительно расширенной операции суперпозиции // Вестник МГУ, Сер. 1: Математика. Механика 2001 - №6 - С. 54-57.

81. Угольников А.Б. О замкнутых классах Поста // Известия вузов. Математика,- 1998,- №7,- С. 79-88.

82. Финько О.А. Реализация систем булевых функций большой размерности методами модулярной арифметики // Автоматика и телемеханика,- 2004.- № 6 С. 37-60.

83. Фрейвалд Р.В. Критерий полноты для частичных функций алгебры логики и многозначной логики // Доклады АН СССР,— 1966,— т. 167, №6.- С. 1249-1250.

84. Фрейвалд Р.В. Функциональная полнота для не всюду определённых функций алгебры логики // Дискретный анализ,— 1966.— № 8.— С. 5568.

85. Хинчин А.Я. Три жемчужины теории чисел.— М: Наука, 1979.

86. Часовских А.А. Об алгоритмической разрешимости проблемы для линейных автоматов // Вестник МГУ, Сер. 1: Математика. Механика,— 1985 -№3- С.82-84.

87. Шмерко В.П. Теоремы Малюгина: новое понимание в логическом управлении, проектировании СБИС и структурах данных для новых технологий // Автоматика и телемеханика.— 2004.— № 6.— С. 61-83.

88. Яблонский С.В. Введение в дискретную математику.— М: Наука, 1979.

89. Яблонский С. В. Вопросы функциональной полноты в Ахзначном исчислении: Дисс. канд. физ.-мат. наук.— М., 1953.

90. Яблонский С. В. О функциональной полноте в трёхзначном исчислении // Доклады АН СССР.- 1954.- т. 92, Ж 6.- С. 1153-1156.

91. Яблонский С.В. Функциональные построения в /г-значной логике // Труды матем. ин-та им. В.А. Стеклова АН СССР.— 1958.— т. 51.— С. 5142.

92. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста.— М: Наука, 1966.

93. Яблонский С.В., Гаврилов Г.П., Набебин А. А. Анализ и синтез схем в многозначных логиках, ч. I,— М: Изд-во МЭИ, 1989.

94. Яблонский С.В., Гаврилов Г.П., Набебин А.А. Предполные классы в многозначных логиках,— М: Изд-во МЭИ, 1997.

95. Янов Ю.И., Мучник А.А. О существовании &-значных замкнутых классов, не имеющих конечного базиса // Доклады АН СССР.— 1959.— т. 127, №1.— С. 44-46.

96. Post E.L. Introduction to a general theory of elementary propositions // Amer. J. Math.- 1921.- т. 43, №3.- С. 163-185.

97. Post E.L. The two-valued iterative systems of mathematical logic // Annals of Math. Studies, v. 5.— Princeton-London: Princeton Univ. Press, 1941.

98. Rosenberg I.G. La structure des fonctions de plusieurs variables sur un ensembe fini // Computes Rendus de l'Acad. Sci. Paris.— 1965.— т. 260 — С. 3817-3819.

99. Rosenberg I.G. Uber die funktionale Vollstandigkeit in den mehrvertigen Logiken // Rospravy Ceskoslovenske Academie ved. Rada matematickych a prirodnich ved.- 1970 т. 80, №4,- С. 3-39.

100. Slupecki J. Kryterium pelnosci wielowar-tosciowych systemow logiki zdari // Comptes Rendus des Seances de la Societe des Sciences et de Lettres de Varsovie, cl. III.- 1939 т. 32.- С. 102-109.