litceysel.ru
добавить свой файл
1

Информатика


ИУ-8






Дисциплина для учебного плана специальности: 0901050065 и 0901020065

Факультета – «Информатика и системы управления»


Информатика (2 семестр)


Кафедра ИУ-8, «Информационная безопасность»



Раздел 2. Знания, умения и навыки, получаемые после освоения дисциплины.

2.1. Студент должен знать:




основные понятия математической логики



понятие булевой функции, способы ее задания, важнейшие свойства булевых функций.



нормальные формы булевых функций



замкнутые классы булевых функций



теорему Поста о функциональной полноте и следствия из нее



основные методы синтеза логических функций, метод каскадов и метод Шеннона.



2.2. Студент должен уметь:



пользоваться известными алгоритмами применительно к стандартным случаям, уметь модифицировать эти алгоритмы для решения нестандартных задач




пользоваться законами и правилами исчисления высказываний



выполнять операции над булевыми функциями



находить мощность замкнутых классов булевых функций



строить контактные схемы методом каскадов



пользоваться элементарными методами синтеза схем из функциональных элементов и оценивать их сложность


Понятия: логическая функция, нормальная форма, замыкание, полнота и замкнутость, контактная схема, схема из функциональных элементов.

2.3. Студент должен иметь навыки:




построения таблицы истинности булевой функции по заданной формуле



получения СДНФ, СКНФ и АНФ по таблице истинности булевой функции.



Раздел 3. Содержание дисциплины.

3.6. Основные понятия математической логики


3.6.1. Математическая логика как часть формальной логики, ее история и задачи. Значение математической логики для конструирования и программирования ЭВМ

3.6.2. Понятие высказывания. Основные операции. Таблицы истинности.

3.6.3. Законы и правила исчисления высказываний.

3.7. Логические функции


3.7.1. Определение булевой функции и способы ее задания.

3.7.2. Примеры булевых функций. Связь булевых функций с основными понятиями логики.


3.7.3. Элементарные операции над булевыми функциями.

3.7.4. Важнейшие свойства булевых функций. Понятие двойственности.

3.8. Нормальные формы булевых функций


3.8.1. Разложение булевой функции по переменным.

3.8.2. Совершенная дизъюнктивная нормальная форма (СДНФ)

3.8.3. Совершенная конъюнктивная нормальная форма (СКНФ).

3.8.4. Алгебраическая нормальная форма (АНФ)

3.9. Полнота и замкнутость


3.9.1. Функционально полные системы.

3.9.2. Замкнутые классы булевых функций: классы функций, сохраняющих константу, классы самодвойственных, монотонных и линейных функций.

3.9.3. Теорема Поста о функциональной полноте и следствия из нее.

3.10. Реализация логических функций


3.10.1. Понятие контактной схемы. Реализация булевой функции с помощью контактных схем. Последовательно-параллельные схемы.

3.10.2. Метод каскадов для построения контактных схем.

3.10.3. Понятие схемы из функциональных элементов.

3.10.4. Элементарные методы синтеза схем и оценки их сложности.

3.10.5. Нижняя оценка Шеннона сложности реализации булевой функции.

3.10.6. Оптимальный по порядку метод Шеннона для синтеза булевой схемы.

Раздел 8. Учебно-методические материалы.

8.1. Основная литература.


  1. Акулов О.А., Медведев Н.В. Информатика. Базовый курс. – М.: Омега-Л, 2004. – 552 с.

  2. Белоусов А.И., Ткачев С.Б. Дискретная математика. – М.: Изд-во МГТУ им. Н.Э.Баумана, 2001. – 744 с.

  3. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. – 400 с.

  4. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. – М.: МЦНМО, 2006. – 400 с.
  5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискрет­ной математике. – 2-е изд. – М.: Наука, 1992. – 368 с.


  6. Курош А.Г. Курс высшей алгебры. – М.: Наука, 1968. – 432 c.

  7. Савельев А.Я. Основы информатики. – М.: Изд-во МГТУ им. Н.Э.Баумана, 2001. – 328 с.

8.2. Дополнительная литература.


  1. Андерсон Дж. Дискретная математика и комбинаторика. – М.: Издательский дом «Вильямс», 2004. – 960 с.

  2. Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. – 2-е изд. – М.: Лаборатория Базовых Знаний, 2000. – 248 с.

  3. Комбинаторный анализ. Задачи и упражнения (под ред. Рыбникова К.А.). – М.: Наука, 1982. – 368 с.

  4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990. – 384 с.

  5. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – 3-е изд. – М.: Наука, 1995. – 255 с.

  6. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Изд-во МАИ, 1992. – 264 с.

  7. Яблонский С.В. Введение в дискретную математику. – 3-е изд. – М.: Высшая школа, 2001. – 384 с.