Информационные материалы (1133245), страница 2
Текст из файла (страница 2)
(17.XI)20. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший методО.Б. Лупанова для синтеза СФЭ в базисе Б0. Синтез схем для ФАЛ из некоторыхспециальных классов. См. [1:гл.4,§5]. (17.XI)21. Регулярные разбиения единичного куба и моделирование ФАЛ переменными.Асимптотически наилучший метод синтеза формул в базисе Б0. См.
[1:гл.4,§6]. (20.XI)22. Асимптотически наилучший метод синтеза КС [1:гл.4,§7]. (24.XI)23. Синтез схем для дешифраторов, мультиплексоров и некоторых других ФАЛ, встречающихся в приложениях, оценки их сложности [1:гл.4,§6]. (27.XI)IV. Надёжность и контроль управляющих систем (1.XII-8.XII)24. Самокорректирующиеся КС и методы их построения. Асимптотически наилучший методсинтеза КС, корректирующих 1 обрыв (1 замыкание). См. [4:§7], [2: ч. III, р. 2, §1]. (8.XII)25.
Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценкидлины диагностического теста. См. [1:гл.1,§8]. (1.XII)V. Некоторые вопросы и классы схем, связанные с программно-аппаратной реализациейалгоритмов (11.XII-18.XII)26. Некоторые модификации основных классов схем (BDD, вычисляющие программы, схемына КМОП-транзисторах и др.), связанные с программно-аппаратной реализацией ФАЛ.См. [1:гл.2,§§4,6,7]. (11.XII)27. Реализация автоматных функций схемами из функциональных элементов и элементовзадержки, схемы с «мгновенными» обратными связями.
См. [6:§8], [2: ч. I, р. I, гл. 3, §§2-3].(11.XII)28. Задачи логического и топологического синтеза СБИС, основные этапы и методы ихрешения. См. [1:гл.2,§7], [8]. (18.XII)5. Типовые задачи к экзаменуI.Задачи на ДНФ1. По заданной ФАЛ построить её сокращённую ДНФ, ДНФ Квайна, ДНФ сумма тупиковых,все тупиковые ДНФ.II. Задачи на структурное моделирование и эквивалентные преобразования2. По заданной формуле построить подобную ей формулу минимальной глубины.3. По заданной формуле с поднятыми отрицаниями построить моделирующую её π-схему иобратно.4. По заданным эквивалентным формулам или КС построить эквивалентное преобразование,переводящее их друг в друга с помощью основных тождеств.III. Задачи на синтез схем5. По данной каскадной КС построить инверсную каскадную КС.6.
По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннонапостроить реализующую её СФЭ или КС.7. Оценить сверху и снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛиз заданного множества в заданном классе схем.IV. Задачи на самокоррекцию и тесты.8. По заданной КС построить эквивалентную ей самокорректирующуюся КС.9. По заданной таблице или КС и списку её неисправностей построить все тупиковыепроверяющие (диагностические) тесты.46. ЛитератураОсновная:1. Ложкин С.А. Лекции по основам кибернетики.
– М.: МГУ, 2004. (Электронные версиилекцийпоследнихлетможнонайтипоадресуhttp://mk.cs.msu.ru/index.php/Основы_кибернетики_(2-й_поток,_3_курс),http://mk.cs.msu.ru/index.php/Основы_кибернетики_(3-й_поток) )2. Яблонский С.В. Элементы математической кибернетики. – М.: Высшая школа, 2007.3. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986.4. Алексеев В.Б.,Вороненко А.А.,Ложкин С.А.,Романов Д.С.,Сапоженко А.А.,Селезнёва С.Н. Задачи по курсу «Основы кибернетики». – М.: МГУ, 2011.5.
Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.:ФИЗМАТЛИТ, 2004.Дополнительная:6. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов. – М.: МГУ, 2000.7. Дискретная математика и математические вопросы кибернетики. – М.: Наука, 1974.8. Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС.(http://mk.cs.msu.ru/images/8/87/Lozhkin-Marchenko-VSLI-models.pdf)9. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. – М.: МГУ, 1984.10.
Нигматулин Р.Г. Сложность булевых функций. – М.: Наука, 1991.7. Особенности организации и контроля аудиторной исамостоятельной работы студентов.Данный вариант курса «Основы кибернетики» является достаточно сложным и объёмнымматематическим курсом, усвоение которого требует от студентов полноценной и регулярной какаудиторной, так и самостоятельной работы, что невозможно без чёткой организации занятий,строгой дисциплины и систематического контроля. При этом необходимо, чтобы в рамкахсамостоятельной работы1 студенты прорабатывали материал, пройденный на предшествующейлекции (семинаре), и желательно, чтобы они знакомились с материалом предстоящей лекции(семинара).Для контроля за освоением программы курса, как уже говорилось, в течение семестрапроводятся 3 основные (по 2 часа) контрольные работы и, возможно, несколько промежуточных(до 1 часа) тестов на знание и понимание определений, формулировок утверждений и т.п., а такжена умение решать задачи.
Планируется, кроме того, осуществлять систематический (выборочный)контроль за работой студентов как на семинарах, так и на лекциях. Все основные контрольныепроводятся в рамках лекционного расписания по следующему графику.Предварительный график проведения основных контрольных работРаздел I:контрольная №1 – 9 октябряРаздел II:контрольная №2 – 13 ноябряРаздел III:контрольная №3 – 11 декабряКроме того, по вопросам раздела IV 18 декабря планируется проведение промежуточноготеста.
Перед указанным тестом, а также перед каждой контрольной предполагается проведениеконсультации.Одной из форм самостоятельной работы является решение предлагаемых на лекциях«трудных» задач2, связанных в ряде случаев с написанием программ, которое позволяет студентамглубже усвоить материал курса и набрать дополнительные к результатам контрольных баллы,повысив, тем самым, свою предварительную оценку (см. раздел 8).11 час самостоятельной работы на 1 час аудиторных занятий.После объявления на лекции формулировки этих задач вывешиваются в интернете, а их решение, оформленное ввиде pdf файла, необходимо прислать по адресу lozhkin@cs.msu.ru (принимается первое и полное правильноерешение).25Информационные объявления, данные о посещаемости и текущей успеваемости студентоввывешиваются на сайте по адресу: http://mk.cs.msu.ru/index.php/Основы_кибернетики_(2-й_поток,_3_курс)8.
О проведении экзамена по курсу «Основы кибернетики»Как уже говорилось, по результатам контрольных работ с учётом посещаемости студентов, ихработы на лекциях и семинарах, а также самостоятельной работы каждому из них выставляетсяпредварительная оценка.Для студентов, имеющих предварительную оценку «5», экзамен проводится в форме общегособеседования по программе курса на определения, формулировки утверждений и идеи ихдоказательства, методы решения задач. Для студентов, имеющих предварительную оценку «2»,экзамен представляет собой письменный тест-контрольную.Все остальные студенты (с предварительной оценкой «3-», «3» и «4») получают билет с двумявопросами и одной задачей и после 15-20 минутной подготовки отвечают на него сначала науровне определений, формулировок утверждений и идей их доказательства, а также методоврешения задач.
Затем студент, по усмотрению экзаменатора, должен раскрыть те или иные деталидоказательства утверждений из вопросов билета по конспектам или иным источникам, а такжеполностью или частично решить задачу билета в течение выделенного специально для этоговремени. Студенты, набравшие не менее 80% от суммы баллов по задачам тестов и контрольныхсоответствующего раздела, то есть получившие по ним оценку «5», от решения билетной задачиданного типа освобождаются. Последний этап экзамена представляет собой описанное вышеобщее собеседование по другим вопросам или задачам программы.В соответствии с установленными нормами итоговая экзаменационная оценка, как правило,не может отличаться от предварительной оценки больше, чем на один балл.
Студенту, которыйимеет предварительную оценку «3» или «4» и не претендует на более высокую итоговую оценку,предоставляется возможность сдавать экзамен по упрощённой процедуре (в форме собеседованияпо программе без предварительной подготовки) с целью подтверждения этой оценки.9.
Планы семинарских занятий на осенний семестр 2017-2018 уч. года иориентировочный график их проведенияСеминар 1 (4.IX-8.IX)Комбинаторика граней единичного булева куба. Представление ФАЛ с помощью ДНФ и его«геометрическая» интерпретация, совершенная ДНФ.
Сокращённая ДНФ и «геометрические»методы её построения, карта Карно. Теоретический материал [1: с. 19-32], [5: с. 290-292, 296-298].В классе. Из [5]: гл. IX – 1.2 (1-6); гл. I – 2.3 (3). Найти число тех ФАЛ от n, n≥2, БП, совершеннаяДНФ которых является их единственной ДНФ и имеет длину 2 (К1); доказать, что длинасовершенной ДНФ от БП x1, …, xn, являющейся единственной ДНФ реализуемой ею ФАЛ, небольше, чем 2n-1 (К2). Из [5]: гл. IX – 2.1 (1,2), 2.5 (1,5), 2.6 (1,5).На дом. Из [5]: гл. IX – 1.2 (7,9); гл. I – 2.3 (4).
Найти число тех ФАЛ от БП x1, …, xn, n≥2,совершенная ДНФ которых является их единственной ДНФ длины 2n-1 (Д1) и длины 3 (Д2). Из [5]:гл. IX – 2.1 (3), 2.5 (2,6), 2.6 (2,6).Семинар 2 (11.IX-15.IX)Алгебраические методы построения сокращённой ДНФ. Тупиковые ДНФ, ядро и ДНФпересечение тупиковых. Теоретический материал [1: с. 32-36,38-41], [5: с. 296-298, 301-303].В классе. Из [5]: гл.
IX – 2.3 (1,2), 2.2 (1,2), 2.9 (3), 2.14 (1,2), 3.3 (1,2) – построить ядро и ДНФ ∩T,2.12 (3).На дом. Из [5]: гл. IX – 2.3 (3,4), 2.2 (3,4), 2.9 (5), 3.3 (3,4) – построить ядро и ДНФ ∩T, 2.12 (6),2.13.Семинар 3 (18.IX-23.IX)ДНФ Квайна и ДНФ сумма тупиковых. Таблица Квайна, методы построения всех тупиковых(минимальных, кратчайших) ДНФ. Теоретический материал [1: с. 41-44,51-55], [5: с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
