Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200




Скачать 83.88 Kb.
НазваниеКурс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200
Дата06.02.2013
Размер83.88 Kb.
ТипДокументы
Курс «Основы кибернетики»

для студентов специализации 01.02.09.01

(математическое и программное обеспечение вычислительных машин)

и бакалавров направления 510200

(прикладная математика и информатика).


  1. Общая информация (учебная нагрузка, формы контроля и др.).

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


Для студентов специализации 01.02.09.01 и бакалавров направления 510200 курс «Основы кибернетики» читается в 6 (320-328 группы) и 8 (431-432 группы) семестрах соответственно в объеме 48 часов лекций, сопровождаемых 16 часами семинарских занятий. Курс завершается экзаменом, на который выносятся как теоретические вопросы, изложенные на лекциях, так и задачи, рассмотренные на семинарских занятиях.

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

Чтение курса обеспечивается кафедрой математической кибернетики.


  1. Аннотация.

Курс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем и основным лектором которого был чл.-корр. РАН С.В. Яблонский, читается на факультете ВМиК с первых лет его существования. Он является продолжением курса «Дискретная математика» и посвящен изложению основных моделей, методов и результатов математической кибернетики, связанных с теорией дискретных управляющих систем (УС), с задачей схемной или структурной реализации дискретных функций и алгоритмов.

В нем рассматриваются различные классы УС (классы схем), представляющие собой дискретные математические модели различных типов электронных схем, систем обработки информации и управления, алгоритмов и программ. Для базовых классов УС (схем из функциональных элементов, формул, контактных схем, автоматных схем), а также некоторых других типов УС, ставятся и изучаются основные задачи теории УС: задача минимизации ДНФ, задача эквивалентных преобразований и структурного моделирования УС, задача синтеза УС, задача повышения надежности и контроля УС из ненадежных элементов и др. В программу курса входят классические результаты К. Шеннона, С.В. Яблонского, Ю.И. Журавлева и О.Б. Лупанова, а также некоторые результаты последних лет. Показывается возможность практического применения этих результатов.


  1. Программа.

I. Представление функций с помощью дизъюнктивных нормальных форм (ДНФ) и связанные с ним задачи.

Единичный куб и функции алгебры логики (ФАЛ), представление ФАЛ с помощью ДНФ. Сокращенная ДНФ и тупиковые ДНФ, их «геометрический» смысл. Способы построения однозначно получаемых ДНФ (сокращенной, пересечения тупиковых, Квайна, суммы тупиковых). Особенности ДНФ для ФАЛ из некоторых классов. Функция покрытия и алгоритм построения всех тупиковых ДНФ, оценка длинных градиентного покрытия. Алгоритмические трудности минимизации ДНФ, оценки максимальных и типичных значений некоторых параметров ДНФ. Задача контроля УС, тесты для таблиц. Алгоритм построения всех тупиковых тестов, оценки максимального и типичного значений длины теста.


II. Основные классы УС оценка числа схем, их структурные представления и эквивалентные преобразования.

Различные классы УС (классы схем) как структурные математические модели различных типов электронных схем, систем обработки информации и управления, алгоритмов и программ. Основные классы УС-формулы и схемы из функциональных элементов (СФЭ), контактные схемы (КС) – их структура, меры сложности, функционирование, полнота. Некоторые частные случаи и обобщения основных классов, оценка числа схем различных типов. Структурные представления схем на основе операции суперпозиции.

Эквивалентность схем. Понятие подсхемы и принцип эквивалентной замены. Тождества и связанные с ними эквивалентные преобразования УС. Построение полных систем тождеств для формул, СФЭ и КС. Отсутствие конечной полной системы тождеств для КС.


III. Синтез, сложность и надежность УС.

Задача синтеза УС, сложность ФАЛ и функция Шеннона. Простейшие методы синтеза схем, реализация некоторых ФАЛ и оценка их сложности. Метод каскадов для КС и СФЭ, метод Шеннона. Мощностные методы получения нижних оценок для функций Шеннона. Асимптотически наилучшие методы синтеза формул, СФЭ и КС. Самокорректирующиеся КС и простейшие методы их синтеза. Асимптотически наилучшие методы синтеза КС, корректирующих один обрыв или одно замыкание. Синтез схем для ФАЛ из инвариантных и других специальных классов.

IV. Структурные модели высокого уровня и некоторые прикладные вопросы теории сложности.

Автоматные функции и их реализация схемами из функциональных элементов и элементов задержки, схемы с «мгновенными» обратными связями. Представление о логических схемах программ. Схемы на КМОП-транзисторах и задача логического синтеза СБИС. Задача «физического» синтеза СБИС и клеточные схемы.


  1. Литература.

Основная:

  1. Ложкин С.А. Лекции по основам кибернетики. М.: МГУ, 2004.

  2. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу «Основы кибернетики». М.: МГУ, 2002.

  3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: ФИЗМАТЛИТ, 2004.

Дополнительная:

  1. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов. М.: МГУ, 2000.

  2. Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974.

  3. Ложкин С.А., Марченко А.М. Математические вопросы проектирования СБИС. http://mathcyb.cs.msu.su (учебники)

  4. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.: МГУ, 1984.

  5. Нигматулин Р.Г. Сложность булевых функций. М.: Наука, 1991.

  6. Сапоженко А.А. Некоторые вопросы сложности алгоритмов. М.: МГУ, 2001.

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

  8. Яблонский С.В. Надежность управляющих систем. М.: Изд-во МГУ, 1991.

  9. Яблонский С.В. Эквивалентные преобразования управляющих систем. М.: Изд-во МГУ, 1986.


5. Вопросы к экзамену.


  1. Предварительный список вопросов к экзамену

по курсу «Основы кибернетики»

(весенний семестр 2005/2006 уч. года, 320-328 и 431-432 группы, лектор – профессор С.А. Ложкин).


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

  1. Единичный куб и функции алгебры логики (ФАЛ). Дизъюнктивные (конъюнктивные) нормальные формы и связанные с ними разложения ([1:гл.1,§2]).

  2. Сокращенная дизъюнктивная нормальная форма (ДНФ) и способы ее построения ([1:гл.1,§3]).

  3. Тупиковые и минимальные ДНФ, ядро и ДНФ Квайна. Критерий вхождения простых импликант в тупиковые ДНФ, его локальность ([1:гл.1,§4]).

  4. Особенности ДНФ для ФАЛ из некоторых классов (линейных, монотонных и др.). Теорема Ю.И. Журавлева о ДНФ сумма минимальных ([1:гл.1,§5]).

  5. Функция покрытия, таблица Квайна и построение всех тупиковых ДНФ. Алгоритмические трудности минимизации ДНФ ([1:гл.1,§6,7]).

  6. Оценки максимальных и типичных значений для некоторых параметров ДНФ ([1:гл.1,§7]).

  7. Градиентный алгоритм и оценка длины градиентного покрытия, примеры его применения ([1:гл.1,§6]).

  8. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценки длины диагностического теста ([1:гл.1,§8]).




  1. Основные классы дискретных управляющих систем. Оценка числа схем, их структурные представления и эквивалентные преобразования.

  1. Представление формул с помощью деревьев. Оптимизация подобных формул по глубине и оценка их чисел ([1:гл.2,§§2,3]).

  2. Схемы из функциональных элементов (СФЭ) и вычисляющие программы. Оценка числа СФЭ в базисе Б0={&,۷,ך} ([1:гл.2,§§3,4]).

  3. Контактные схемы (КС) и π-схемы, оценка их числа. Особенности функционирования многополюсных КС ([1:гл.2,§§5,6]).

  4. Операция суперпозиции и её корректность для некоторых типов схем. Разделительные КС, лемма Шеннона ([1:гл.2,§§3,5,6]).

  5. Эквивалентные преобразования схем на основе тождеств. Моделирование эквивалентных преобразований формул в классе СФЭ ([1:гл.3,§1]).

  6. Эквивалентные преобразования формул базиса Б0, полнота системы основных тождеств. Теорема перехода ([1:гл.3,§§2,3]).

  7. Эквивалентные преобразования КС. Основные тождества, вывод вспомогательных и обобщенных тождеств ([1:гл.3,§4]).

  8. Полнота системы основных тождеств. Отсутствие конечной полной системы тождеств в классе всех КС ([1:гл.3,§5]).




  1. Синтез, сложность и надежность управляющих систем.

  1. Задача синтеза. Простейшие методы синтеза схем и оценки сложности функций ([1:гл.4,§§1,2]).

  2. Каскадные схемы и адресующие программы. Метод каскадов для КС и СФЭ, метод Шеннона ([1:гл.2, §7; гл.4,§3]).

  3. Нижние мощностные оценки функций Шеннона ([1:гл.4,§4]).

  4. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший метод О.Б. Лупанова для синтеза СФЭ в базисе Б0 ([1:гл.4,§5]).

  5. Регулярные сдвиговые разбиения единичного куба. Асимптотика сложности контрактного дешифратора ([1:гл.4,§§6,7]).

  6. Асимптотически наилучший метод синтеза формул в базисе Б0 ([1:гл.4,§6]).

  7. Асимптотически наилучший метод синтеза КС ([1:гл.4,§7]).

  8. Поведение функции Шеннона для глубины ФАЛ ([1:гл.4,§6]).

  9. Самокорректирующиеся КС и методы их построения. Асимптотически наилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание) ([2:§7], [11:§2.1]).

  10. Инвариантные классы С.В. Яблонского, их основные свойства. Синтез схем для ФАЛ из инвариантных и некоторых других специальных классов ([9:§2]).




  1. Структурные модели высокого уровня и некоторые прикладные вопросы теории сложности.

  1. Реализация автоматных функций схемами из функциональных элементов и элементов задержки, схемы с «мгновенными» обратными связями ([4:§8]).

  2. Представление о логических схемах программ. Особенности постановки и решения основных задач теории управляющих систем для автоматных схем и схем программ ([4:§8], [12:§6]).

  3. Схемы на КМОП-транзисторах и реализация ими простейших функций. Задача логического синтеза СБИС ([1:гл.II,§7], [7]).

  4. Клеточные схемы как «грубая» топологическая модель СБИС. Задача «физического» синтеза СБИС ([7]).


6. Типовые задачи к экзамену.


I. Задачи на ДНФ.


  1. По заданной ФАЛ построить ее сокращенную ДНФ, ДНФ Квайна, ДНФ сумма тупиковых, все тупиковые ДНФ.


II. Задачи на тесты.


  1. По заданной таблице или КС и списку ее неисправностей построить все тупиковые проверяющие (диагностические) тесты.


III. Задачи на эквивалентные преобразования и структурное моделирование.


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

  2. По заданной формуле построить подобную ей формулу минимальной глубины.

  3. По заданной формуле с поднятыми отрицаниями построить моделирующую ее π-схему и обратно.


IV. Задачи на синтез схем.


  1. По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую ее СФЭ или КС.

  2. Оценить сверху или снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем.

  3. По заданной КС построить эквивалентную ей самокорректирующуюся КС.



7. Темы семинарских занятий и контрольных работ.


  1. Представление ФАЛ с помощью ДНФ. Сокращенная ДНФ и методы ее построения ([3:гл.IX,§2]).

  2. Ядро и ДНФ Квайна, ДНФ сумма тупиковых. Построение всех тупиковых ДНФ ([3:гл.IX,§3]).

  3. Тесты для таблиц, тесты для КС ([2:§5,6]).

Контрольная №1 по темам 1-3 продолжительностью 2 часа с предшествующей консультацией планируются на 24марта.

  1. Эквивалентные преобразования формул. Оптимизация формул по глубине ([2:§3]).

  2. Моделирование формул и π-схем. Эквивалентные преобразования КС ([2:§4]).

Контрольная №2 по темам 4-5 продолжительностью 2 часа с предшествующей консультацией планируются на 21 апреля.

  1. Сложность ФАЛ и простейшие методы синтеза схем. Метод каскадов и метод Шеннона ([3:гл.X]).

  2. Самокорректирующиеся КС. Асимптотически наилучшие методы синтеза, синтез схем для ФАЛ из специальных классов ([2:§ 7]).

Контрольная №3 по темам 6-7 продолжительностью 2 часа с предшествующей консультацией планируются на 19 мая.





Похожие:

Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200 iconКурс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин)
Курс является обязательным для всех студентов, обучающихся по специальности 01. 02 – прикладная математика и информатика. При этом...
Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200 iconПрограмма– Математическое и программное обеспечение вычислительных машин
Ения некорректных задач. Методические указания по выполнению лабораторных работ студентов по специальности "010500. 68 – Прикладная...
Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200 iconЛейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Мцнмо, 1999. Косовский Н. К. Основы теории элементарных алгоритмов
«Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»
Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200 iconСпециальность 05. 13. 11
«Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей»
Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200 iconМетодические указания по самостоятельной работе для направления 010400 Прикладная математика и информатика Магистерская программа Математическое и программное обеспечение вычислительных комплексов и компьютерных сетей
Методические указания по самостоятельной работе студентов для направления 010400 – Прикладная математика и информатика. Магистерская...
Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200 icon1. цели и задачи дисциплины, ее место в учебном процессе согласно гос впо в дисциплину «Вычислительные системы, сети и телекоммуникации» должно включаться
Вычислительных машин: общие принципы построения и архитектуры вычислительных машин, информационно-логические основы вычислительных...
Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200 iconПрограмма-минимум кандидатского экзамена по специальности 05. 13. 11
«Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»
Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200 iconПрограмма-минимум кандидатского экзамена по специальности
«Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»
Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200 iconПрограмма дисциплины Программное обеспечение вычислительных
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 230100 "Информатика...
Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01 (математическое и программное обеспечение вычислительных машин) и бакалавров направления 510200 iconРазработка и исследование методов создания специализированного компьютерного банка знаний для органической химии
Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница