English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и лабораторий Проблем теоретической кибернетики и Математичеких проблем искусственного интеллекта механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сервера Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Канал кафедры МаТИС в Телеграм
 ТДФ Теория дискретных функций – лекции и семинары для студентов 1 курса (II поток)
 Ташкентский филиал Ташкентский филиал МГУ им. М.В. Ломоносова
 Семинары расписание специальных семинаров кафедры МаТИС
 Курсы расписание специальных курсов кафедры, программа курсов
 Практикум cпециальный математический практикум кафедры МаТИС, III курс
 Студенты список студентов кафедры по курсам и группам, расписание занятий, выпускники
 Магистратура информация для поступающих в магистратуру
 Аспирантура информация для аспирантов и поступающих в аспирантуру; списки аспирантов

 

Программа курса:

  1. Понятие схемы из функциональных элементов (СФЭ). Задание СФЭ в виде линейной программы. Меры сложности СФЭ: объем и глубина. Зависимость объема и глубины от выбора базиса.
  2. Функция Шеннона для объема СФЭ. Точная по порядку нижняя оценка функции Шеннона. Метод Шеннона синтеза СФЭ. Метод О.Б. Лупанова синтеза СФЭ (без доказательства).
  3. Теорема о связи глубины и объема для СФЭ без выходного ветвления. Оценка порядка глубины для схем без выходного ветвления.
  4. Синтез сумматора. Последовательный сумматор. Схемы параллельного вычисления переноса. Сумматор Когге-Стоуна.
  5. Синтез умножителя. Схемы ускоренного суммирования частичных произведений. Компрессор Уоллеса. Метод Карацубы.
  6. Понятие конечного автомата, способы задания конечных автоматов. Языки, определяемые конечным автоматом по выходам и по состояниям, теорема о эквивалентности классов таких языков. Детерминированные и недетерминированные конечные автоматы, теорема о эквивалентности задаваемых ими классов языков.
  7. Эквивалентность состояний детерминированного конечного автомата без выходов. Табличный алгоритм, строящий классы эквивалентности состояний. Квадратичная относительно временной сложности версия табличного алгоритма.
  8. Эквивалентность состояний детерминированного конечного автомата с выходами. Теорема Мура. Алгоритм минимизации числа состояний, основанный на доказательстве теоремы Мура.
  9. Понятие клеточного автомата. Отображения, реализуемые клеточными автоматами. Теорема Ричардсона (без доказательства).
  10. Понятие взаимного моделирования для клеточных автоматов. Теорема о моделировании произвольных клеточных автоматов в клеточных автоматах с шаблоном соседства фон Неймана.
  11. Понятие мозаичных клеточных автоматов. Моделирование мозаичных клеточных автоматов в клеточных автоматах. Модель асинхронного распространения фронта сигнала.
  12. Универсальный относительно операции взаимного моделирования двумерный клеточный автомат с шаблоном соседства фон Неймана. Лемма о моделировании локальных переходов на квадратной конфигурации. Лемма о транспортных слоях. Лемма о синтезе задающего генератора. Лемма о синхронизации.

Литература.

  1. Яблонский С.В. Введение в дискретную математику. Высшая школа, Москва, 2002.
  2. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. Наука, Москва, 1985.
  3. Кудрявцев В.Б., Подколзин А.С., Болотов А.А. Основы теории однородных структур. Наука, Москва, 1990.
  4. Сэвидж Джон Э. Сложность вычислений. Издательство "Факториал", Москва, 1998.
  5. Верещагин Н.В., Шень А. "Логические формулы и схемы". Математическое просвещение, 4, МЦНМО, Москва, 2000.
  6. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation – 2nd ed. Addison-Wesley, 2001, ISBN 0-201-44124-1.
  7. John Savage. Models of computation: exploring the power of computing. Addison-Wesley, 1998, ISBN 0-201-89539-0.
  8. Moshe Sipper. Evolution of Parallel Cellular Machines: The Cellular Programming Approach. Springer, 1997, ISBN 3-540-62613-1.
  9. P. M. Kogge and H. S. Stone, "A parallel algorithm for the efficient solution of a general class of recurrence equations", IEEE Trans. Computers, Vol. C-22, No. 8, 1973.
  10. C. S. Wallace, "A suggestion for a fast multiplier", IEEE Trans. Computers, Vol. EC-13, 1964.
  11. Richardson D. "Tesselations with local transformations". Journal of Computer and System Sciences, No. 5, 1972.

Наверх

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

Спецкурс "Теория синтеза логических устройств"

Теория синтеза логических устройств м.н.с. Кучеренко И.В. В этом семестре не читается
   © 2001- г. Кафедра Математической теории интеллектуальных систем, лаборатория ПТК, лаборатория МПИИ Написать вебмастеру   
Последние новости - в телеграм-канале кафедры МаТИС: Канал кафедры МаТИС в Телеграм Rambler's Top100 Рейтинг@Mail.ru