Список вопросов и типовых задач к экзамену

Список вопросов и типовых задач к экзамену по курсу«Основы кибернетики» (весенний семестр 2015-2016 уч. г.; 320-328 гр.)1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.I. Основные вопросы, входящие в экзаменационные билетыПредставление функций алгебры логики (ФАЛ) дизъюнктивными нормальными формами(ДНФ) и его «геометрическая» интерпретация.

Совершенная ДНФ и критерийединственности ДНФ. См. [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].Формулы и способы их задания, эквивалентность формул и функционалы их сложности[1:гл.1,§1, гл.3,§1]. Оптимизация подобных формул по глубине [1:гл.2,§2].Схемы из функциональных элементов (СФЭ) и операции их приведения. Оценка числаформул и СФЭ в базисе Б0={&,۷,‫}ך‬. См.

[1:гл.2,§§2,3].Контактные схемы (КС) и π-схемы, моделирование формул и π-схем. Оценки числа КС ичисла π-схем, особенности функционирования многополюсных КС. См. [1:гл.2,§§5,6].Эквивалентные преобразования формул с помощью тождеств. Полнота системы основныхтождеств для эквивалентных преобразований формул базиса Б0. См. [1:гл.3,§2].Эквивалентные преобразования СФЭ и моделирование с их помощью формульныхпреобразований. Моделирование эквивалентных преобразований формул и схем вразличных базисах, теорема перехода.

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

[1:гл.3,§5].Задача синтеза. Методы синтеза схем на основе ДНФ и связанные с ними верхние оценкисложности функций. См. [1:гл.4,§1].Нижние оценки сложности ФАЛ, реализация некоторых ФАЛ и минимальность некоторыхсхем. См. [1:гл.4,§2], [7:§7].Разложение ФАЛ и операция суперпозиции схем.

Корректность суперпозиции длянекоторых типов схем, разделительные КС и лемма Шеннона. См. [1:гл.2,§§6,7].Каскадные КС и СФЭ. Метод каскадов и примеры его применения, метод Шеннона.См. [1:гл.4,§3].Нижние мощностные оценки функций Шеннона, их обобщение на случай синтеза схем дляФАЛ из специальных классов [1:гл.4,§4].Дизъюнктивно-универсальные множества ФАЛ.

Асимптотически наилучший методО.Б. Лупанова для синтеза СФЭ в базисе Б0. См. [1:гл.4,§5].Регулярные разбиения единичного куба и моделирование ФАЛ переменными.Асимптотически наилучший метод синтеза формул в базисе Б0. См. [1:гл.4,§6].Асимптотически наилучший метод синтеза КС. Синтез схем для ФАЛ из некоторыхспециальных классов.

См. [1:гл.4, §§7,5].Синтез схем для некоторых дешифраторов и мультиплексоров, оценки их сложности[1:гл.4,§6].Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценкидлины диагностического теста. См. [1:гл.1,§8].Самокорректирующиеся КС и методы их построения. Асимптотически наилучший методсинтеза КС, корректирующих 1 обрыв (1 замыкание). См.

[4:§7], [2: ч. III, р. 2, §1].126.27.28.29.1.2.3.4.5.6.7.8.9.II. Дополнительные вопросыПолиномиальная сводимость языков. Классы P и NP, NP-полнота, формулировка теоремыКука. Примеры NP-полных проблем. См. [6:§§4.1,4.5-4.8].Некоторые модификации основных классов схем (BDD, вычисляющие программы, схемына КМОП-транзисторах и др.), связанные с программно-аппаратной реализацией ФАЛ.См. [1:гл.2,§§4,6,7].Реализация автоматных функций схемами из функциональных элементов и элементовзадержки, схемы с «мгновенными» обратными связями. См. [7:§8], [2: ч. I, р. I, гл.

3, §§2-3].Задачи логического и топологического синтеза СБИС, основные этапы и методы ихрешения. См. [1: гл. 2, §7], [9].III. Типовые задачи к экзаменуПо заданной ФАЛ построить её сокращённую ДНФ, ДНФ Квайна, ДНФ сумма тупиковых,все тупиковые ДНФ.По заданной формуле построить подобную ей формулу минимальной глубины.По заданной формуле с поднятыми отрицаниями построить моделирующую её π-схему иобратно.По заданным эквивалентным формулам или КС построить эквивалентное преобразование,переводящее их друг в друга с помощью основных тождеств.По данной каскадной КС построить инверсную каскадную КС.По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннонапостроить реализующую её СФЭ или КС.Оценить сверху и снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛиз заданного множества в заданном классе схем.По заданной КС построить эквивалентную ей самокорректирующуюся КС.По заданной таблице или КС и списку её неисправностей построить все тупиковыепроверяющие (диагностические) тесты.IV.

ЛитератураОсновная:1. Ложкин С.А. Лекции по основам кибернетики. – М.: МГУ, 2004. (Электронные версиилекцийпоследнихлетможнонайтипоадресуhttp://mk.cs.msu.ru/index.php/Основы_кибернетики_(3-й_поток) )2. Яблонский С.В. Элементы математической кибернетики. – М.: Высшая школа, 2007.3. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986.4. Алексеев В.Б.,Вороненко А.А.,Ложкин С.А.,Романов Д.С.,Сапоженко А.А.,Селезнёва С.Н. Задачи по курсу «Основы кибернетики». – М.: МГУ, 2011.5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике.

– М.:ФИЗМАТЛИТ, 2004.6. Алексеев В.Б. Введение в теорию сложности алгоритмов. – М.: Изд-во МГУ, 2002.Дополнительная:7. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов. – М.: МГУ, 2000.8. Дискретная математика и математические вопросы кибернетики. – М.: Наука, 1974.9. Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС.(http://mk.cs.msu.ru/images/8/87/Lozhkin-Marchenko-VSLI-models.pdf)10. Лупанов О.Б. Асимптотические оценки сложности управляющих систем.

– М.: МГУ, 1984.11. Нигматулин Р.Г. Сложность булевых функций. – М.: Наука, 1991.2Порядок проведения экзамена по курсу «Основы кибернетики»В соответствии с объявленными в начале семестра правилами, по результатам контрольныхработ с учётом посещаемости студентов, их работы на лекциях и семинарах, а такжесамостоятельной работы каждому из них выставляется предварительная оценка.Для студентов, имеющих предварительную оценку «5», экзамен проводится в форме общегособеседования по программе курса на определения, формулировки утверждений и идеи ихдоказательства, методы решения задач.Для студентов, имеющих предварительную оценку «2», экзамен представляет собойписьменный тест-контрольную из 9-10 вопросов и задач продолжительностью 2 астрономическихчаса.

Данный тест могут по желанию писать и студенты, имеющие оценку «3-», но их итоговаяоценка в этом случае будет не больше «3».Все остальные студенты (с предварительной оценкой «3-», «3» и «4») получают билет с двумявопросами и одной задачей и после 15-20 минутной подготовки отвечают на него сначала науровне определений, формулировок утверждений и идей их доказательства, а также методоврешения задач. Затем студент, по усмотрению экзаменатора, должен раскрыть те или иные деталидоказательства утверждений из вопросов билета по конспектам или иным источникам, а такжеполностью или частично решить задачу билета в течение выделенного специально для этоговремени.

Студенты, набравшие не менее 80% от суммы баллов по задачам тестов-контрольныхсоответствующего раздела, то есть получившие по ним оценку «5», от решения билетной задачиданного типа освобождаются. Последний этап экзамена представляет собой описанное вышеобщее собеседование по другим вопросам или задачам программы.В соответствии с принятыми правилами итоговая экзаменационная оценка не можетпревосходить предварительную оценку больше, чем на один балл. Студент, который имеетпредварительную оценку «3» или «4» и не претендует на более высокую итоговую оценку, сдаётэкзамен, как правило, по упрощённой процедуре (в форме собеседования по билету и программебез предварительной подготовки) с целью подтверждения этой оценки.3.