Лекции по "Дискретной математике"

ФИО Пальшина Мария Анатольевна   № договора 731-3797118-1122 

Специальность___ИНФОРМАЦИОННЫЕ СИСТЕМЫ И ТЕХНОЛОГИИ__ 

Подпись_____[pic 1]______Дата___20/05/2023_________

STUDY GUIDE

Название дисциплины_______Дискретная математика_______

ЧУВО «Высшая школа предпринимательства (институт)» совместно с Swiss International Institute Lausanne – SIIL

2023

1. Понятие кодирования. Алфавитное кодирование. 

Кодирование - это процесс преобразования информации из одной формы представления в другую, чтобы она могла быть передана, хранена или обработана компьютерной системой или другим устройством. Кодирование используется для представления данных, таких как текст, звук, изображения или видео, в виде последовательности символов или битов.

Алфавитное кодирование является одним из способов кодирования текстовой информации. Оно основано на присвоении каждому символу или символьной последовательности уникального числового значения или кода. Например, в ASCII (American Standard Code for Information Interchange) каждому символу латинского алфавита, цифрам и некоторым специальным символам соответствует уникальный числовой код от 0 до 127. Таким образом, каждый символ может быть представлен в виде числа, и эти числа могут быть использованы для передачи, хранения и обработки символьных данных.

Пример алфавитного кодирования: если у нас есть текстовая строка "Hello", мы можем использовать ASCII для кодирования каждого

символа: H -> 72, e -> 101, l -> 108, l -> 108, o -> 111

Таким образом, строка "Hello" может быть закодирована в виде последовательности чисел: 72 101 108 108 111.

Алфавитные кодирования могут также включать более сложные системы, такие как Unicode, которые поддерживают широкий спектр символов различных письменностей и языков.

Алфавитное кодирование широко используется в различных областях, включая компьютерные системы, коммуникации, интернет и мультимедиа. Оно позволяет представить символы и символьные данные в виде последовательности битов, что удобно для их хранения, передачи и обработки компьютерами.

2. Операция двоичного сложения и ее свойства. Многочлен Жегалкина.

Операция двоичного сложения - это основная арифметическая операция в двоичной системе счисления, которая выполняется на двоичных числах (битах). При двоичном сложении два бита складываются, и результатом является сумма и, возможно, перенос.

Здесь приведены основные правила двоичного сложения:

0 + 0 = 0: Сумма двух нулей равна нулю.

1. + 1 = 1: Сумма нуля и единицы равна единице.
2. + 0 = 1: Сумма единицы и нуля также равна единице.

1 + 1 = 0 с переносом 1: Сумма двух единиц равна нулю, но с генерацией переноса в следующий разряд.

Если выполняется сложение более чем двух битов, применяются те же правила, применяемые к каждой паре битов, начиная с младших разрядов и продвигаясь к старшим разрядам.

Многочлен Жегалкина, также известный как каноническая форма Жегалкина, является представлением булевой функции в виде суммы произведений булевых переменных и их отрицаний. Он назван в честь французского математика Ивана Жегалкина. Многочлен Жегалкина может быть записан в виде:

f(x1, x2, ..., xn) = c0 ⊕ (c1 ∧ x1) ⊕ (c2 ∧ x2) ⊕ ... ⊕ (cn ∧ xn), где xi - булевые переменные, ci - коэффициенты (0 или 1), ∧ - логическое умножение (AND), ⊕ - исключающее ИЛИ (XOR). Коэффициенты ci указывают, какие произведения переменных включены в функцию, а их значения 0 или 1 определяют, соответственно, отсутствие или наличие соответствующего произведения в сумме.

Многочлен Жегалкина позволяет компактно представлять и анализировать булевые функции, а также использовать их в цифровых схемах и логических вычислениях.