Программа курса, предварительный вариант вопросов к экзамену (2014-04-24) (1133267)
Текст из файла
Курс «Основы кибернетики»для бакалавров (интегрированных магистров)направления 01400 «Прикладная математика иинформатика» профиля «Системноепрограммирование и компьютерные науки»1. Общая информация(учебная нагрузка, формы контроля и др.)Курс является обязательным для всех бакалавров (интегрированных магистров)направления 01400 – «Прикладная математика и информатика».
При этом объём и, внекоторой степени, программа курса варьируются в зависимости от профиля.Для бакалавров 3 курса профиля «Системное программирование и компьютерныенауки» (320-328 группы) курс «Основы кибернетики» читается в 6 семестре в объёме48 часов лекций, сопровождаемых 16 часами семинарских занятий. Курс завершаетсяэкзаменом, на который выносятся как теоретические вопросы, изложенные на лекциях,так и задачи, рассмотренные на семинарских занятиях.В разделах 2-7 данного описания приводится подробная информация о содержаниикурса, программах и планах его изучения в 2013-2014 уч.
году, методическихматериалах, а в разделах 8 и 9 – об особенностях организации учебного процесса,формах и сроках проведения контрольных мероприятий.В соответствии с этими планами в течение семестра проводятся 3 основных (по 2часа) и, возможно, несколько промежуточных (до 1 часа) тестов (контрольных). По ихрезультатам с учётом посещаемости студентов, их работы на лекциях и семинарах, атакже самостоятельной работы (см.
раздел 8) выставляется предварительная оценка,которая играет существенную роль при формировании окончательной оценки наэкзамене (см. раздел 9).Чтение курса обеспечивается кафедрой математической кибернетики, лектор 20132014 уч. года – профессор Ложкин С.А. (lozhkin@cs.msu.su).2. АннотацияКурс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем иосновным лектором которого был чл.-корр.
РАН С.В. Яблонский, читается нафакультете ВМК с первых лет его существования. Он является продолжением курса«Дискретная математика» и посвящён изложению основных моделей, методов ирезультатов математической кибернетики, связанных с теорией дискретныхуправляющих систем (УС), с задачей схемной или структурной реализации дискретныхфункций и алгоритмов.В нём рассматриваются различные классы УС (классы схем), представляющиесобой дискретные математические модели различных типов электронных схем, системобработки информации и управления, алгоритмов и программ. Для базовых классов УС(схем из функциональных элементов, формул, контактных схем, автоматных схем), атакже некоторых других типов УС, ставятся и изучаются основные задачи теории УС:задача минимизации дизъюнктивных нормальных форм (ДНФ), задача эквивалентныхпреобразований и структурного моделирования УС, задача синтеза УС, задачаповышения надёжности и контроля УС из ненадёжных элементов и др.Рассматриваются также некоторые вопросы сложности алгоритмов.
В программу курсавходят классические результаты К. Шеннона, С.В. Яблонского, Ю.И. Журавлева иО.Б. Лупанова, а также некоторые результаты последних лет. Показываетсявозможность практического применения этих результатов на примере задачи1проектирования СБИС,реализации алгоритмов.которыесоставляютосновупрограммно-аппаратной3. ПрограммаМинимизация дизъюнктивных нормальных форм и связанные с нейзадачиЕдиничный куб и функции алгебры логики (ФАЛ), представление ФАЛ спомощью ДНФ. Сокращённая ДНФ и тупиковые ДНФ, их «геометрический» смысл.Способы построения однозначно получаемых ДНФ (сокращённой, пересечениятупиковых, Квайна, суммы тупиковых).
Особенности ДНФ для ФАЛ из некоторыхклассов. Функция покрытия и алгоритм построения всех тупиковых ДНФ, оценкадлины градиентного покрытия. Алгоритмические трудности минимизации ДНФ,оценки максимальных и типичных значений некоторых параметров ДНФ.I.Основные классы дискретных управляющих систем, структурныепредставления схем и оценка их числа.
Некоторые модели и классы схем,связанные с программно-аппаратной реализацией алгоритмовРазличные классы УС (классы схем) как структурные математические моделиразличных типов электронных схем, систем обработки информации и управления,алгоритмов и программ. Основные классы УС – формулы и схемы из функциональныхэлементов (СФЭ), контактные схемы (КС), – их структура, меры сложности,функционирование, эквивалентность, полнота.
Оценка числа схем различных типов.Понятие подсхемы и принцип эквивалентной замены. Операция суперпозициисхем и её корректность, лемма Шеннона.Некоторые модификации основных классов схем, связанные с программнойреализацией ФАЛ.
Автоматные функции, их реализация схемами из функциональныхэлементов и элементов задержки, схемы с «мгновенными» обратными связями. Схемына КМОП-транзисторах, задача логического и «физического» синтеза СБИС, основныеэтапы её решения.II.III. Синтез и сложность управляющих системЗадача синтеза УС, сложность ФАЛ и функция Шеннона. Простейшие методысинтеза схем, реализация некоторых ФАЛ и оценка их сложности. Метод каскадов дляКС и СФЭ, метод Шеннона.
Мощностные методы получения нижних оценок дляфункций Шеннона. Асимптотически наилучшие методы синтеза формул, СФЭ и КС.Синтез схем для ФАЛ из специальных классов и индивидуальных ФАЛ.IV. Эквивалентные преобразования управляющих системТождества и связанные с ними эквивалентные преобразования УС. Построениеполных систем тождеств для формул, СФЭ и КС. Отсутствие конечной полной системытождеств для КС. Представление об эквивалентных преобразованиях автоматных схеми схем программ.V.
Надёжность и контроль управляющих системСамокорректирующиеся КС и простейшие методы их синтеза. Асимптотическинаилучшие методы синтеза КС, корректирующих один обрыв или одно замыкание.Задача контроля УС, тесты для таблиц. Алгоритм построения всех тупиковыхтестов, оценки максимального и типичного значений длины диагностического теста.VI. Некоторые вопросы сложности алгоритмовПолиномиальная сводимость языков, классы Р и NP, теорема Кука.24.
Предварительный список вопросов к экзамену по курсу«Основы кибернетики» (весенний семестр 2013-2014 уч. года;320-328 группы), ориентировочный график их изучения налекциях.Минимизация дизъюнктивных нормальных форм и связанные с нейзадачи (07.II–03.III)Представление функций алгебры логики (ФАЛ) дизъюнктивными нормальнымиформами (ДНФ) и его «геометрическая» интерпретация. Совершенная ДНФ икритерий единственности ДНФ. См.
[1:гл.1,§§2,5].Сокращённая ДНФ и способы её построения [1:гл.1,§3].Тупиковая ДНФ, ядро и ДНФ пересечение тупиковых. ДНФ Квайна, критерийвхождения простых импликант в тупиковые ДНФ и его локальность.См. [1:гл.1,§4].Особенности ДНФ линейных и монотонных ФАЛ. Функция покрытия, таблицаКвайна и построение всех тупиковых ДНФ.
См. [1:гл.1,§§5,6].Градиентный алгоритм и оценка длины градиентного покрытия, лемма о«протыкающих» наборах. Использование градиентного алгоритма для построенияДНФ. См. [1:гл.1,§6].Задача минимизации ДНФ. Поведение функции Шеннона и оценки типичныхзначений для ранга и длины ДНФ [1:гл.1,§7].Алгоритмические трудности минимизации ДНФ и оценки максимальных значенийнекоторых связанных с ней параметров [1:гл.1,§§1,3,7]. Теорема Ю.И. Журавлёва оДНФ сумма минимальных [1:гл.1,§5].I.1.2.3.4.5.6.7.Основные классы дискретных управляющих систем, структурныепредставления схем и оценка их числа.
Некоторые модели и классы схем,связанныеспрограммно-аппаратнойреализациейалгоритмов(07.III–17.III, 16.V)Формулы и способы их задания, эквивалентность формул и функционалы ихсложности [1:гл.1,§1, гл.3,§1]. Оптимизация подобных формул по глубине[1:гл.2,§2].Схемы из функциональных элементов (СФЭ) и операции их приведения. Оценкачисла формул и СФЭ в базисе Б0={&,۷,}ך. См. [1:гл.2,§§2,3].Контактные схемы (КС) и π-схемы, моделирование формул и π-схем.
Оценки числаКС и числа π-схем, особенности функционирования многополюсных КС.См. [1:гл.2,§§5,6].Операция суперпозиции и её корректность для некоторых типов схем.Разделительные КС и лемма Шеннона. См. [1:гл.2,§§6,7].Некоторые модификации основных классов схем (BDD, вычисляющие программыи др.), связанные с программной реализацией ФАЛ. См. [1:гл.2,§§4,6,7].Реализация автоматных функций схемами из функциональных элементов иэлементов задержки, схемы с «мгновенными» обратными связями. См. [7:§8],[2: часть I, разд. I, гл.
3, §§2-3].Схемы на КМОП-транзисторах и реализация ими простейших функций. Задачилогического и топологического синтеза СБИС, основные этапы и методы ихрешения. См. [1:гл.2,§7], [9].II.8.9.10.11.12.13.14.III. Синтез и сложность управляющих систем (21.III–11.IV)15.
Задача синтеза. Методы синтеза схем на основе ДНФ и связанные с ними верхниеоценки сложности функций. См. [1:гл.4,§1].16. Нижние оценки сложности ФАЛ, реализация некоторых ФАЛ и минимальностьнекоторых схем. См. [1:гл.4,§2], [7:§7].317. Каскадные КС и СФЭ. Метод каскадов и примеры его применения, методШеннона. См. [1:гл.4,§3].18. Нижние мощностные оценки функций Шеннона [1:гл.4,§4].19. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучшийметод О.Б. Лупанова для синтеза СФЭ в базисе Б0. См. [1:гл.4,§5].20. Регулярные разбиения единичного куба и моделирование ФАЛ переменными.Синтез схем для некоторых дешифраторов и мультиплексоров.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
