пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
 РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Дискретный Анализ информационных систем

1 Множество и элементы множества. Определение множества. Конечные и бесконечные множества. Задание множества. Мощность множества. Условия равенства (неравенства) множеств. Диаграммы Венна (Круги Эйлера). Добавление и удаление элементов.
2 Подмножество, собственное подмножество. Операции над множествами (объединение, пересечение, разность). Законы теории множеств. Линейный порядок. Минимизации представления множества.
3 Определение декартова произведения. Отношение. Бинарные отношения. Тернарные отношения. Эквивалентность. Толерантность. Отношение частичной упорядоченности.
4 Соответствие. Функция. Инъекция, сюръекция, биекция. Обратная функция. Суперпозиция бинарных отношений. Классификация отображений. Изоморфизм. Частично упорядоченные множества.
5 Свойства бинарных отношений (рефлексивность, транзитивность, симметричность, антисимметричность, антирефлексивность, асимметричность). Эквивалентность. Толерантность. Фактор-множества.
6 Декартово произведение, проекция. Булеан и универсумом. Границы множеств. Ограниченные множества. Точная верхняя (нижняя) граница множества.
7 Бинарные отношения: определение бинарных отношений, операции над бинарными отношениями; основные классы бинарных отношений: функциональные отношения, отношение порядка, отношение эквивалентности, примеры. НЕПОЛНЫЙ БИЛЕТ
8 Основные правила комбинаторики. Правило произведения. Правило сумм. Перечислительная комбинаторика. Перестановки. Перестановки с повторениями. Размещения. Размещения с повторениями. Упорядоченное размещение. Сочетания. Сочетания с повторениями.
9 Комбинаторика. Метод производящий функций чисел Фибоначчи, сочетаний. Свойства биномиальных коэффициентов. Экспоненциальная производящая функция.
10 Элементы комбинаторики: рекуррентные соотношения для соответствующих величин; бином Ньютона, свойства биномиальных коэффициентов, треугольник Паскаля.
11 Элементы комбинаторики: производящие функции, примеры; метод включения и исключения; теоремы существования.
12 Бинарные отношения: операции над множествами, определение бинарных отношений, операции над бинарными отношениями; основные классы бинарных отношений: функциональные отношения, отношение порядка, отношение эквивалентности.
13 Алгебраическая система. Алгебры с одной бинарной операцией. Полугруппа. Моноид. Группоид. Группа. Абелева группа. Алгебра с двумя операциями. Кольца. Тело. Поля. Отношения. Морфизмы.
14 Логика высказываний. Основные законы дизъюнкции, конъюнкции и отрицания. Целые числа по модулю m.
15 Элементы теории графов: определение графа, способы задания; теорема Эйлера, полнота, связность, цикломатическое число, его свойства.
16 Элементы теории графов: маршруты и циклы в графах, эйлеровы циклы (необходимое и достаточное условие), гамильтоновы циклы(достаточное условие). определение графа, способы задания, основные понятия в графах;
17 Теорема Эйлера, полнота, связность, цикломатическое число, его свойства; маршруты и циклы в графах.
18 Деревья, теорема Келли; плоские и планарные графы, теорема Эйлера, примеры неплоских графов, теорема Куратовского-Понтрягина (без доказательства); хроматическое число, условие бихроматизма, теорема о пяти красках.
19 Элементы теории графов: деревья, теорема Келли; плоские и планарные графы, теорема Эйлера, примеры неплоских графов.
20 Предикат. Примеры предикатов: разрешимых, тождественно истинных, тождественно ложных. Операции над предикатами. Множество истинности предиката.
21 Алфавит логики предикатов. Квантор. Формула логики предикатов. Основные правила построения формул. Основные правила перехода к новым равносильным формулам. Непротиворечивые, противоречивые, общезначимые формулы.
22 Приведенная форма. Нормальная форма. Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к нормальной форме. Совершенные ДНФ (СДНФ) и КНФ (СКНФ).
23 Исчисление предикатов. Аксиомы исчисления предикатов. Применение логики предикатов. Кванторы. Формулы логики предикатов. Равносильные формулы логики предикатов. Приведенные и нормальные формы в логике предикатов. Алгоритм преобразования формул в нормальную форму.
24 Элементы булевых функций: определение булевых функций, основные понятия, способы задания, существенные и фиктивные переменные,
25 Формулы, равносильность, разложение по “k” переменным; замыкание, замкнутость, полнота; основные классы булевых функций: определения, примеры, свойства;
26 Синтез булевых функций; схемы из функциональных элементов; определение функции Шеннона, верхние и нижние оценки функции Шеннона.
27 Элементы булевых функций: определение булевых функций, основные понятия, способы задания, существенные и фиктивные переменные, формулы, равносильность, разложение по “k” переменным.
28 Элементы булевых функций: основные классы булевых функций: определения, примеры, свойства; теорема Поста. Первая и вторая теоремы Шеннона. Функциональная полнота.
29 Двухэлементная булева алгебра. Элементы булевых функций: синтез булевых функций; схемы из функциональных элементов; определение функции Шеннона, верхние и нижние оценки функции Шеннона. Минимизация булевых функций в классе ДНФ.
30 Элементы теории кодирования: основные задачи; алфавитное кодирование, однозначное декодирование, критерии Маркова и Петтерсона.
31 Элементы теории кодирования: префиксное кодирование, неравенство Крафта, теорема Мак-Миллана. n-мерный булев куб. свойства соответствующего графа, теорема Шпернера, определение и свойства расстояния Хемминга;
32 Элементы теории кодирования: способ построения кода Хемминга, геометрическая интерпретация. основные задачи; алфавитное кодирование, способы построения кодов Фано и Шеннона; оптимальное кодирование, код Хаффмена, алгоритмы сжатия информации; способ построения кода Хемминга, геометрическая интерпретация.
10.06.2014; 17:51
комментариев: 2
хиты: 36571
рейтинг:+3
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь