Список вопросов и типовых задач к экзамену (1133347)
Текст из файла
Список вопросов и типовых задач к экзамену по курсу«Основы кибернетики» (весенний семестр 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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
