oc3-seminar-09 (Программа курса)
Описание файла
Файл "oc3-seminar-09" внутри архива находится в папке "Программа курса". Документ из архива "Программа курса", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "oc3-seminar-09"
Текст из документа "oc3-seminar-09"
План проведения семинарских занятий по курсу
«Основы кибернетики» в 2008-2009 учебном году для 320-328 групп.
-
Представление ФАЛ с помощью ДНФ. Сокращенная ДНФ и методы ее построения.
а) Теоретический материал: [1:с.27-35], [3:с.47, 296-298].
б) В классе ([3]): гл. I – 2.3(3); гл. IX – 2.1(1,2), 2.5 (1,5), 2.6 (1), 2.3 (1,2), 2.2 (1,2), 2.9 (1,2).
в) На дом: ([3]): гл. I – 2.3(4); гл. IX – 2.1(3), 2.5 (2,6), 2.6 (2), 2.2 (3,4), 2.3 (3,4), 2.9 (6).
-
Ядро и ДНФ Квайна, ДНФ «сумма тупиковых». Построение всех тупиковых ДНФ.
а) Теоретический материал: [1:с.38-43, 51-55], [3:с. 301-302].
б) В классе ([3, гл. IX]): 3.1(1,5) 3.3 (1,2 – построить ядро, ДНФ Квайна и ДНФ «сумма тупиковых»), 3.4 (3), 3.6 (1,4,7).
в) На дом ([3, гл. IX]): 3.1(4,6), 3.3 (3,4 – построить ядро, ДНФ Квайна и ДНФ «сумма тупиковых»), 3.4(4), 3.6 (3,6,8).
-
Тесты для таблиц, тесты для контактных схем.
а) Теоретический материал: [1: с. 65-72, 51-55], [2: с. 29-32, 35-36].
б) В классе ([2]): 5.1 (1, 2 – все тупиковые диагностические тесты), 5.1 (3 – все тупиковые проверяющие тесты), 6.2, 6.4, 6.11 (если хватит времени).
в) На дом ([2]): 5.1 (5 – все тупиковые диагностические тесты, 6 – все тупиковые проверяющие тесты), 6.3, 6.5, 6.14.
-
Эквивалентные преобразования формул. Оптимизация подобных формул по глубине.
а) Теоретический материал: [1:с.147-161, 86-90].
б) В классе ([2, 1]): 3.1 (1), 3.3 (1,4), 3.8 (1-3), 3.9 (1); построить для ДНФ x1 x1x3 x4x5x6 подобную ей формулу минимальной глубины.
в) На дом ([2, 1]); 3.1 (2), 3.3 (3,6), 3.8 (5-9), 3.9 (2);
построить для ДНФ x1 x5 x2x3x4 x4x5 x6 подобную ей формулу минимальной глубины.
-
Моделирование формул и π-схем. Эквивалентные преобразования КС.
а) Теоретический материал: [1:с.115-117,169-185].
б) В классе ([1, 2]): по заданной формуле с поднятыми отрицаниями построить моделирующую π-схему и обратно; 4.1 (2,5, 7-9), 4.3 (1).
в) На дом ([2]): 4.1 (10-13), 4.3 (3).
-
Сложность ФАЛ и простейшие методы синтеза схем. Метод каскадов и метод Шеннона.
а) Теоретический материал: [1: с. 186-210].
б) В классе ([3, гл. X]):1.1 (2, 3, 4 – как для СФЭ, так и для КС); доказать минимальность построенных в задаче 1.1 (2) схем на основе леммы 2.3 из [1]; 2.5 (1), 2.13 (1,7), 2.14 (1), 2.14 (5 – как КС, так и СФЭ).
в) На дом ([3, гл. X]): 1.1 (5-7), 2.5 (2); 2.13 (2,6), 2.14 (2), 2.14 (6-как КС, так и СФЭ).
-
Асимптотически наилучшие методы синтеза, синтез схем для ФАЛ из специальных классов. Самокорректирующиеся КС.
а) Теоретический материал: [1, с. 215-216, 222-224], [2, с. 47-48].
б) В классе: установить асимптотику функции Шеннона для сложности класса всех ФАЛ равных 1 при x1=1 (КС), класса всех самодвойственных ФАЛ (СФЭ) и класса всех ФАЛ симметричных по первым трем БП (КС); ([2]): 7.7(б), 7.8 (1), 7.11 (1).
в) На дом: установить асимптотику функции Шеннона для сложности класса всех ФАЛ, равных 0 при x1=x2=0 (КС), и класса, состоящего из всех тех ФАЛ, у которых любая подфункция от первых трех БП линейна; ([2]): 7.7 (в), 7.8 (2), 7.9 (а).
Литература.
-
Ложкин С. А. Лекции по основам кибернетики. — М.: МАКС Пресс, 2004.
-
Алексеев В. Б., Вороненко А. А., Ложкин С. А., Романов Д. С., Сапоженко А. А., Селезнева С. Н. Задачи по курсу «Основы кибернетики». — М.: МАКС Пресс, 2002.
-
Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. — М.: Физматлит, 2004.