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

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.

Наверх