- •6 Отношения. Унарные, бинарные, тернарные отношения.
- •13 Способы задания нечетких множеств. Операции над нечеткими множествами.
- •Операции над нечеткими множествами
- •15 Логика высказываний.
- •16 Логические операции. Формулы логики высказываний. Логические операции.
- •Формулы логики высказываний
- •17 Равносильность формул.
- •18 Нормальные формы формул, приведение к днф, кнф.
- •19 Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы.
- •Алгоритм получения сднф по таблице истинности.
- •Алгоритм получения скнф по таблице истинности.
- •20 Булева алгебра. Логические функции одной или нескольких переменных.
- •21 Суперпозиции функций. Полные системы логических функций.
- •22 Минимизация в классе дизъюнктивных нормальных форм.
- •23 Исчисление высказываний и исчисление предикатов.
- •Исчисление предикатов
- •24 Аксиоматические теории. Выводимость формул в исчислении высказываний.
- •25. Теорема дедукции. Предикаты, кванторы.
- •26. Формулы логики предикатов, их равносильность, выполнимость и общезначимость.
- •27. Аксиомы исчисления предикатов.
- •28. Алгебраические структуры. Группы.
- •29. Циклические группы. Группы подстановок. Кольца и поля
- •30. Элементы теории кодирования. Представление о кодировании.
- •31. Расстояние Хемминга.
- •32. Теорема о корректирующей способности кодов.
- •33. Матричное кодирование. Групповые коды.
- •34. Коды Хемминга.
- •35. Элементы комбинаторики. Размещения и сочетания.
- •36 Перестановки и подстановки.
- •37 Разбиения Формула включений и исключений.
- •38 Теория графов. Основные понятия и определения.
- •39 Понятие графа. Виды графов.
- •40 Способы задания графов.
- •41 Смежность, инцидентность.
- •42.Операции над графами. Части графов.
- •43 Связность, компоненты связности.
- •44 Числа графов: цикломатическое, хроматическое, внешней и внутренней устойчивости.
- •45 Поиск маршрутов в графе. Задача о минимальном соединении.
- •46 Задача о кратчайшем пути.
- •47 Эйлеровы цепи и циклы. Гамильтоновы цепи и циклы.
- •48 Транспортные сети. Понятие транспортной сети.
- •49 Поток в транспортной сети. Разрез, пропускная способность разреза.
- •50 Алгоритмы построения максимального потока.
- •1) Процедура помечивания вершин.
- •2) Процедура изменения потока.
30. Элементы теории кодирования. Представление о кодировании.
В теории передачи информации чрезвычайно важным является решение проблемы кодирования и декодирования, обеспечивающее надежную передачу по каналам связи с шумом.
Передача информации сводится к передаче по некоторому каналу связи символов некоторого алфавита. Однако в реальных ситуациях сигналы при передаче практически всегда могут искажаться, и переданный символ будет восприниматься неправильно. Например, в системе ЭВМ ≈ ЭВМ одна из вычислительных машин может быть связана с другой через спутник. Канал связи в этом случае физически реализуется электромагнитным полем между поверхностью Земли и спутником. Электромагнитные сигналы, накладываясь на внешнее поле, могут исказиться и ослабиться. Для обеспечения надежности передачи информации в таких системах разработаны эффективные методы, использующие коды различных типов.
Рассмотрим одну из таких моделей, связанную с групповыми кодами.
Алфавит, в котором записываются сообщения, считаем состоящим из двух символов {0, 1}. Он называется двоичным алфавитом. Тогда сообщение есть конечная последовательность символов этого алфавита. Сообщение, подлежащее передаче, кодируется по определенной схеме более длинной последовательностью символов в алфавите {0, 1}. Эта последовательность называется кодом или кодовым словом. При приеме можно исправлять или распознавать ошибки, возникшие при передаче по каналу связи, анализируя информацию, содержащуюся в дополнительных символах. Принятая последовательность символов декодируется по определенной схеме в сообщение, с большой вероятностью совпадающее с переданным.
Ранее средства кодирования играли вспомогательную роль и не рассматривались как отдельный предмет математического изучения, но с появлением компьютеров ситуация радикально изменилась. Кодирование буквально пронизывает информационные технологии и является центральным вопросом при решении самых разных (практически всех) задач программирования:
- представление данных произвольной природы (например, чисел, текста, графики) в памяти компьютера;
- защита информации от несанкционированного доступа;
- обеспечение помехоустойчивости при передаче данных по каналам связи;
- сжатие информации в базах данных.
Теория кодирования - это раздел теории информации, изучающий способы отождествление сообщений с отображающими их сигналами.
Задача: Согласовать источник информации с каналом связи.
Объект: Дискретная или непрерывная информация, поступающая к потребителю через источник информации.
Кодирование – это преобразования информации в формулу удобную для передачи по определенному каналу связи.
Примером кодирования в математике является метод координат, введенный Декартом, который дает возможность изучать геометрические объекты через их аналитическое выражение в виде чисел, букв и их комбинаций — формул.
Понятие кодирование означает преобразование информации в форму, удобную для передачи по определенному каналу связи.
Декодирование – восстановление принятого сообщения из-за кодированного вида в вид доступный для потребителя.