001 КОНСПЕКТ лекций ИКТ и ММОД


Содержание
Представление информации в компьютере, единицы измерения информации. Кодирование.
Системы счисления.
Алгебра логики.
Тригеры.
Представление информации в компьютере, единицы измерения информации
Человек для записи текстовой информации использует буквы (в русском алфавите – 33). Комбинациями из десяти цифр (от 0 до 9) мы записываем числовые данные. При работе с графической информацией пользуемся палитрой из миллионов цветов. Наши уши различают звуки в диапазоне от 16 до 20000 Гц. Если добавить к этому обоняние, вкусовые и тактильные ощущения, получится огромнейшее разнообразие информационных импульсов, которые может воспринимать, хранить и обрабатывать наш мозг. Но при помощи технических средств невозможно воссоздать аналогичную систему работы с информацией.
В технике намного удобнее иметь дело с множеством простых элементов, чем с небольшим количеством сложных.
Вся информация в компьютере представляется с помощью нулей и единиц, поэтому компьютер может обрабатывать только информацию, представленную в цифровой форме.
Для преобразования числовой, текстовой, графической, звуковой информации в цифровую необходимо применить кодирование.
Двоичное кодирование информации
Любая информация внутри компьютера хранится и обрабатывается в виде длинного кода, состоящего всего из двух символов. Этот код называется двоичным или бинарным. Идея использования бинарного кода принадлежит немецкому математику Готфриду Лейбницу (1646-1716). Он разработал двоичную арифметику и даже сделал чертеж двоичной вычислительной машины, но не сумел ее построить.
Используя разные комбинации большого количества двух символов, в бинарном коде можно зашифровать любую числовую, текстовую, звуковую или графическую информацию. По своей сути он очень похож на всем известный код Морзе, в котором двумя символами (длинный и короткий импульс) шифруются буквы для передачи текстовой информации по проводам или другим способом.
Компьютер является ничем иным, как машиной, предназначенной для хранения и обработки информации в таком виде, принимает одно из двух состояний по аналогии: лампочка горит или нет, магнитное поле есть или его нет и т.д. Бинарный код внутри компьютера хранится в виде комбинаций большого количества элементов, каждый из которых может иметь одно из двух состояний.
В ЭВМ в форме бинарного кода хранятся не только текстовые данные, но и программы, музыка, изображения и даже видео высокой четкости.
Перед выводом информации на экран, в аудиосистему или распечатыванием, компьютер "переводит" ее в понятный человеку язык. Но внутри компьютера она хранится и обрабатывается исключительно в виде двоичного кода.
Перевод данных в двоичный код называется кодированием.
Кодирование – это преобразование данных одного типа через данные другого типа.
Противоположный процесс, в результате которого бинарный код превращается в привычную для людей информацию, называется декодированием.
С технической стороны компьютерный двоичный код реализуется наличием или отсутствием определенных свойств (импульсов) у мельчайших запоминающих элементов. Эти импульсы могут быть:
• фотооптическими
Так, поверхность любого оптического диска (CD, DVD или BluRay) состоит из спирали, которую формируют мелкие отрезки. Каждый из них может быть либо темного, либо светлого цвета. Диск быстро вращается в дисководе. На его спиральной дорожке фокусируется лазер, отражение которого попадает на фотоэлемент. Темные участки спирали поглощают свет и не передают его на фотоэлемент, светлые – наоборот, отражая свет, передают импульс фотоэлементу. В результате фотоэлемент получает информацию, зашифрованную в дорожке диска в виде темных и светлых точек.
• магнитными
Например, внутри жесткого диска находится быстро вращающаяся пластина. Вся ее поверхность тоже представляет собой спираль, состоящую из последовательности миллионов мелких участков. Каждый из них является элементом, который может принимать одно из двух состояний: "намагниченное", "ненамагниченное". Эти элементы и формируют двоичный код, в котором кодируется какая-то информация. Считывание состояния элементов осуществляется специальной головкой, которая быстро движется по поверхности пластины;
• электрическими
Например, оперативная память компьютера является микросхемой, состоящей из миллионов маленьких ячеек, созданных из микроскопических транзисторов и конденсаторов. Каждая такая ячейка может либо содержать электрический заряд, либо нет. Комбинации заряженных и разряженных ячеек оперативной памяти и формируют в ней двоичный код.
В аналогичной форме информация хранится и во всех других запоминающих микросхемах (флешки, SSD-носители и др.).
Процессор компьютера обрабатывает двоичный код тоже в виде электрических импульсов.
Иногда можно встретить ошибочное мнение, что бинарный код внутри компьютера записан в виде обычных нулей и единиц. Это следствие непонимания технической стороны вопроса. Привычных для нас нулей и единиц в компьютере нет. "Символами" компьютерного двоичного кода является наличие или отсутствие у мельчайшего запоминающего элемента определенного свойства (см. выше).
Чтобы было нагляднее, в учебных материалах отсутствие у элемента такого свойства лишь условно обозначают нулем, а его наличие – единицей. Но с таким же успехом их можно бы было обозначать точкой и тире или крестиком и ноликом. 
Единицы компьютерной информации
В ЭВМ применяется система двоичного кодирования, основанная на представлении данных последовательностью двух знаков: 1 и 0, которые называются двоичными цифрами (binary digit – сокращенно bit). Таким образом, единицей информации в компьютере является один бит, т.е. двоичный разряд, который может принимать значение 0 или 1. Битом является, например, каждая темная или светлая точка дорожки оптического диска, каждая запоминающая ячейка оперативной памяти компьютера и т.д.
Но каждый отдельный бит сам по себе не имеет практической ценности. Для кодирования информации используются блоки из нескольких битов.
Представим, например, что в каком-то запоминающем устройстве содержится только один бит. В нем можно будет закодировать всего одно из двух состояний чего либо, например, одну из двух цифр или один из двух цветов. Понятное дело, что практическая ценность такого носителя минимальна.
Блок из 2 битов может принимать одно из 4 состояний:

В 3-хбитном блоке можно закодировать уже одно из 8 состояний:

Ну а 8-битный блок может принимать аж 256 разных состояний. Это уже достаточно существенная частичка двоичного кода, позволяющая отобразить один из значительного количества вариантов.
Например, каждому состоянию 8-битного блока можно сопоставить какую-то букву. Вариантов, а их 256, будет достаточно для кодирования всех русских букв, включая строчные и прописные их варианты, а также всех знаков препинания. Заменяя каждую букву соответствующим 8-мибитным блоком, из двоичного кода можно составить текст.
Этот принцип и используется для записи в компьютере текстовой информации (подробнее речь об этом пойдет ниже).
Как видите, 8-битная ячейка имеет вполне реальную практическую ценность. Поэтому ее и решили считать минимальной единицей компьютерной информации. Эта единица получила название байт.
Текстовые файлы состоят из сотен, тысяч или даже десятков тысяч букв. Соответственно, для их хранения в двоичном коде требуются сотни, тысячи или десятки тысяч байтов.
Поэтому на практике гораздо чаще приходится имеет дело не с байтами, а с более крупными единицами:
• килобайтами (1 килобайт = 1024 байт);
• мегабайтами (1 мегабайт = 1024 килобайт);
• гигабайтами (1 гигабайт = 1024 мегабайт);
• терабайтами (1 терабайт = 1024 гигабайт). 
Целые числа кодируются двоичным кодом довольно просто (путем деления числа на два). Для кодирования нечисловой информации используется следующий алгоритм: все возможные значения кодируемой информации нумеруются и эти номера кодируются с помощью двоичного кода. Например, для представления текстовой информации используется таблица нумерации символов или таблица кодировки символов, в которой каждому символу соответствует целое число (порядковый номер). Восемь двоичных разрядов могут закодировать 256 различных символов.
Кодирование числовой информации
Для работы с числовой информацией мы пользуемся системой счисления, содержащей десять цифр: 0 1 2 3 4 5 6 7 8 9. Эта система называется десятичной.
Кроме цифр, в десятичной системе большое значение имеют разряды. Подсчитывая количество чего-нибудь и дойдя до самой большой из доступных нам цифр (до 9), мы вводим второй разряд и дальше каждое последующее число формируем из двух цифр. Дойдя до 99, мы вынуждены вводить третий разряд. В пределах трех разрядов мы можем досчитать уже до 999 и т.д.
Таким образом, используя всего десять цифр и вводя дополнительные разряды, мы можем записывать и проводить математические операции с любыми, даже самыми большими числами.
Компьютер ведет подсчет аналогичным образом, но имеет в своем распоряжении всего две цифры – логический ноль (отсутствие у бита какого-то свойства) и логическая единица (наличие у бита этого свойства).
Система счисления, использующая только две цифры, называется двоичной.
При подсчете в двоичной системе добавлять каждый следующий разряд приходится гораздо чаще, чем в десятичной.
Вот таблица первых десяти чисел в каждой из этих систем счисления:

Как видите, в десятичной системе счисления для отображения любой из первых десяти цифр достаточно 1 разряда. В двоичной системе для тех же целей потребуется уже 4 разряда.
Соответственно, для кодирования этой же информации в виде двоичного кода нужен носитель емкостью как минимум 4 бита (0,5 байта).
Человеческий мозг, привыкший к десятичной системе счисления, плохо воспринимает систему двоичную. Хотя обе они построены на одинаковых принципах и отличаются лишь количеством используемых цифр. В двоичной системе точно так же можно осуществлять любые арифметические операции с любыми числами. Главный ее минус - необходимость иметь дело с большим количеством разрядов.
Так, самое большое десятичное число, которое можно отобразить в 8 разрядах двоичной системы - 255, в 16 разрядах – 65535, в 24 разрядах – 16777215.
Компьютер, кодируя числа в двоичный код, основывается на двоичной системе счисления. Но, в зависимости от особенностей чисел, может использовать разные алгоритмы:
• небольшие целые числа без знака
Для сохранения каждого такого числа на запоминающем устройстве, как правило, выделяется 1 байт (8 битов). Запись осуществляется в полной аналогии с двоичной системой счисления.
Целые десятичные числа без знака, сохраненные на носителе в двоичном коде, будут выглядеть примерно так:

• большие целые числа и числа со знаком
Для записи каждого такого числа на запоминающем устройстве, как правило, отводится 2-байтний блок (16 битов).
Старший бит блока (тот, что крайний слева) отводится под запись знака числа и в кодировании самого числа не участвует. Если число со знаком "плюс", этот бит остается пустым, если со знаком "минус" – в него записывается логическая единица. Число же кодируется в оставшихся 15 битах.
Например, алгоритм кодирования числа +2676 будет следующим:
1. Перевести число 2676 из десятичной системы счисления в двоичную. В итоге получится 101001110100;
2. Записать полученное двоичное число в первые 15 бит 16-битного блока (начиная с правого края). Последний, 16-й бит, должен остаться пустым, поскольку кодируемое число имеет знак +.
В итоге +2676 в двоичном коде на запоминающем устройстве будет выглядеть так:

Примечательно, что в двоичном коде присвоение числу отрицательного значения предусматривает не только изменение старшего бита. Осуществляется также инвертирование всех остальных его битов.
Чтобы было понятно, рассмотрим алгоритм кодирования числа -2676:
1. Перевести число 2676 из десятичной системы счисления в двоичную. Получим все тоже двоичное число 101001110100;
2. Записать полученное двоичное число в первые 15 бит 16-битного блока. Затем инвертировать, то есть, изменить на противоположное, значение каждого из 15 битов;
3. Записать в 16-й бит логическую единицу, поскольку кодируемое число имеет отрицательное значение.
В итоге -2676 на запоминающем устройстве в двоичном коде будет иметь следующий вид:

Запись отрицательных чисел в инвертированной форме позволяет заменить все операции вычитания, в которых они участвуют, операциями сложения. Это необходимо для нормальной работы компьютерного процессора.
Максимальным десятичным числом, которое можно закодировать в 15 битах запоминающего устройства, является 32767. Иногда для записи чисел по этому алгоритму выделяются 4-байтные блоки. В таком случае для кодирования каждого числа будет использоваться 31 бит плюс 1 бит для кодирования знака числа. Тогда максимальным десятичным числом, сохраняемым в каждую ячейку, будет 2147483647 (со знаком плюс или минус).
• дробные числа со знаком
Дробные числа на запоминающем устройстве в двоичном коде кодируются в виде так называемых чисел с плавающей запятой (точкой). Алгоритм их кодирования сложнее, чем рассмотренные выше. Тем не менее, попытаемся разобраться.
Для записи каждого числа с плавающей запятой компьютер чаще всего выделяет 4-байтную ячейку (32 бита):
• в старшем бите этой ячейки (тот, что крайний слева) записывается знак числа. Если число отрицательное, в этот бит записывается логическая единица, если оно со знаком "плюс" – бит остается пустым.
• во втором слева бите аналогичным образом записывается знак порядка (что такое порядок поймете позже);
• в следующих за ним 7 битах записывается значение порядка.
• в оставшихся 23 битах записывается так называемая мантисса числа.

Чтобы стало понятно, что такое порядок, мантисса и зачем они нужны, переведем в двоичный код десятичное число 6,25.
Порядок кодирования будет примерно следующим:
1. Перевести десятичное число в двоичное (десятичное 6,25 равно двоичному 110,01);
2. Определить мантиссу числа. Для этого в числе необходимо передвинуть запятую в нужном направлении, чтобы слева от нее не осталось ни одной единицы. В нашем случае запятую придется передвинуть на три знака влево. В итоге, получим мантиссу ,11001;
3. Определить значение и знак порядка.
Значение порядка – это количество символов, на которое была сдвинута запятая для получения мантиссы. В нашем случае оно равно 3 (или 112 в двоичной форме);
Знак порядка – это направление, в котором пришлось двигать запятую: влево – "плюс", вправо – "минус". В нашем примере запятая двигалась влево, поэтому знак порядка – "плюс";
Таким образом, порядок двоичного числа 110,01 будет равен +11, а его мантисса ,11001. В результате в двоичном коде на запоминающем устройстве это число будет записано следующим образом

Обратите внимание, что мантисса в двоичном коде записывается, начиная с первого после запятой знака, а сама запятая упускается.
Числа с плавающей запятой, кодируемые в 32 битах, называю числами одинарной точности.
Когда для записи числа 32-битной ячейки недостаточно, компьютер может использовать ячейку из 64 битов. Число с плавающей запятой, закодированное в такой ячейке, называется числом двойной точности. 
Двоичное кодирование текстовой информации
Существует несколько общепринятых стандартов кодирования текста в двоичном коде.
Одним из наиболее "старых" (разработан еще в 1960-х гг.) является стандарт ASCII (от англ. American Standard Code for Information Interchange– Стандартный американский код обмена информацией) – это код для представления символов английского алфавита в виде чисел, каждой букве сопоставлено число от 0 до 127. Является 7-битным стандартом кодирования, т.е., используя его, компьютер записывает каждую букву или знак в одну 7-битную ячейку запоминающего устройства.
Как известно, ячейка из 7 битов может принимать 128 различных состояний. Соответственно, в стандарте ASCII каждому из этих 128 состояний соответствует какая-то буква, знак препинания или специальный символ.
Дальнейшее развитие компьютерной техники показало, что 7-битный стандарт кодирования является слишком "тесным". В 128 состояниях, принимаемых 7-битной ячейкой, невозможно закодировать буквы всех существующих в мире письменностей.
Поэтому разработчики программного обеспечения начали создавать собственные 8-битные стандарты кодировки текста. За счет дополнительного бита диапазон кодирования в них был расширен до 256 символов. Чтобы не было путаницы, первые 128 символов в таких кодировках, как правило, соответствуют стандарту ASCII. Оставшиеся 128 – реализуют региональные языковые особенности.
Восьмибитными кодировками, распространенными в нашей стране, являются KOI8, UTF8, Windows-1251 и некоторые другие.
Разработаны также и универсальные стандарты кодирования текста (Unicode), включающие буквы большинства существующих языков. В них для записи одного символа может использоваться до 16 битов и даже больше.
Существование большого количества кодировок текста является причиной многих проблем, выражаемых в неверном определении компьютером кодировки, в которой этот текст хранится в его памяти и в некоторых программах на экране вместо букв отображаются непонятные знаки.

Кодирование изображений в двоичный код
Чтобы сохранить в двоичном коде фотографию, ее сначала виртуально разделяю на множество мелких цветных точек, называемых пикселями (что-то на подобии мозаики).
После разбивки на точки цвет каждого пикселя кодируется в бинарный код и записывается на запоминающем устройстве.
Первая цифровая фотокамера, созданная в 1975 г. инженерами компании Kodak, весила 3 кг, делала черно-белые снимки размером 100Х100 пикселей и сохраняла их в двоичном коде на магнитную ленту. Запись одного снимка длилась дольше 20 секунд.
Если говорят, что размер изображения составляет, например, 512 х 512 точек, это значит, что оно представляет собой матрицу, сформированную из 262144 пикселей (количество пикселей по вертикали, умноженное на количество пикселей по горизонтали).
Прибором, "разбивающим" изображения на пиксели, является любая современная фотокамера (в том числе веб-камера, камера телефона) или сканер.
И если в характеристиках камеры значится, например, "10 Mega Pixels", значит количество пикселей, на которые эта камера разбивает изображение для записи в двоичном коде, - 10 миллионов.
Чем на большее количество пикселей разделено изображение, тем реалистичнее выглядит фотография в декодированном виде (на мониторе или после распечатывания).
Для кодирования графических данных применяется, например, такой метод кодирования как растр. Координаты точек и их свойства описываются с помощью целых чисел, которые кодируются с помощью двоичного кода. Однако качество кодирования фотографий в бинарный код зависит не только от количества пикселей, но также и от их цветового разнообразия.
Так черно-белые графические объекты могут быть описаны комбинацией точек с 256 градациями серого цвета, т.е. для кодирования яркости любой точки достаточно 8-разрядного двоичного числа.
Алгоритмов записи цвета в двоичном коде существует несколько. Самым распространенным из них является RGB. Эта аббревиатура – первые буквы названий трех основных цветов: красного – англ. Red, зеленого – англ. Green, синего – англ. Blue. Режим представления цветной графики в системе RGB с использованием 24 разрядов (по 8 разрядов для каждого из трех основных цветов) называется полноцветным.
Смешивая эти три цвета в разных пропорциях, можно получить любой другой цвет или оттенок. На этом и построен алгоритм RGB. Каждый пиксель записывается в двоичном коде путем указания количества красного, зеленого и синего цвета, участвующего в его формировании.
Чем больше битов выделяется для кодирования пикселя, тем больше вариантов смешивания этих трех каналов можно использовать и тем значительнее будет цветовая насыщенность изображения.
Цветовое разнообразие пикселей, из которых состоит изображение, называется глубиной цвета.
Если для кодирования каждого пикселя какого-то изображения выделяется 8 битов двоичного кода, цветовое разнообразие составит 256 цветов.
Глубина цвета 12-битов даст 4096 цветов, 16-битов - 65536 цветов, 18-битов - 262144 цветов.
Максимальная глубина цвета, используемая в компьютерной технике – 24 бита. Такую глубину часто называют True Color ("Настоящий цвет"). Она позволяет отобразить около 16,7 млн. цветов. Глаз человека не способен воспринимать большее их количество.
Для полноцветного режима в системе CMYK необходимо иметь 32 разряда (четыре цвета по 8 разрядов).
Но кроме растровой графики, в компьютерах используется еще и так называемая векторная графика.
Векторные изображения создаются только при помощи компьютера (фотокамеры этого делать "не умеют") и формируются не из пикселей, а из графических примитивов (линий, многоугольников, окружностей и др.).
Зачем нужна векторная графика? В известной детской песенке поется, что для изображения "человечка" достаточно нарисовать всего две "палки" и "огуречек". А представьте, насколько трудно вручную составить человечка из большого числа точек.
Векторная графика – это чертежная графика. Она очень удобна для компьютерного "рисования" и широко используются дизайнерами при графическом оформлении печатной продукции, в том числе создании огромных рекламных плакатов, а также в других подобных ситуациях.
Векторное изображение в двоичном коде записывается как совокупность примитивов с указанием их размеров, цвета заливки, места расположения на холсте и некоторых других свойств.
Например, чтобы записать на запоминающем устройстве векторное изображение круга, компьютеру достаточно в двоичный код закодировать тип объекта (окружность), координаты его центра на холсте, длину радиуса, толщину и цвет линии, цвет заливки.
В растровой системе пришлось бы кодировать цвет каждого пикселя. И если размер изображения большой, для его хранения понадобилось бы значительно больше места на запоминающем устройстве.
Тем не менее, векторный способ кодирования не позволяет записывать в двоичном коде реалистичные фото. Поэтому все фотокамеры работают только по принципу растровой графики. Рядовому пользователю иметь дело с векторной графикой в повседневной жизни приходится не часто.
 Кодирование звуковой информации
Любой звук, слышимый человеком, является колебанием воздуха, которое характеризируется двумя основными показателями: частотой и амплитудой.
Амплитуда колебаний – это степень отклонения состояния воздуха от начального при каждом колебании. Она воспринимается нами как громкость звука.
Частота колебаний – это количество отклонений состояний воздуха от начального за единицу времени. Она воспринимается как высота звука.
Так, тихий комариный писк – это звук с высокой частотой, но с небольшой амплитудой. Звук грозы наоборот имеет большую амплитуду, но низкую частоту.
Если графически изобразить звуковую волну, она будет выглядеть следующим образом:

Схему работы компьютера со звуком в общих чертах можно описать так.
Микрофон превращает колебания воздуха в аналогичные по характеристикам электрические колебания.
Звуковая карта компьютера "умеет" преобразовывать электрические колебания в двоичный код, который записывается на запоминающем устройстве. При воспроизведении такой записи происходит обратный процесс (декодирование) – двоичный код преобразуется в электрические колебания, которые поступают в аудиосистему или наушники.
Динамики акустической системы или наушников имеют противоположное микрофону действие. Они превращают электрические колебания в колебания воздуха.
Но каким же образом звуковая карта преобразовывает электрические колебания в двоичный код?
Если взглянуть на графическое изображение волны и внимательно проанализировать ее геометрию, можно увидеть, что в каждый конкретный момент времени звук имеет определенную интенсивность (степень отклонения от начального состояния).

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

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

Описанный принцип разделения звуковой волны на мелкие участки и лежит в основе двоичного кодирования звука.
Аудиокарта компьютера разделяет звук на очень мелкие временные участки и кодирует степень интенсивности каждого из них в двоичный код. Такое "дробление" звука на части называется дискретизацией. Чем выше частота дискретизации, тем точнее фиксируется геометрия звуковой волны и тем качественней получается запись.
Так, простая речь (например, диктофонная запись) нормально воспринимается человеком, если частота дискретизации при кодировании была не ниже 8000 Гц (8 КГц). То есть, каждая секунда такой записи в двоичном коде должна состоять как минимум из 8000 частей.
Музыкальные же произведения, хранимые в компьютере, должны иметь еще более высокую частоту дискретизации. При записи стандартных звуковых CD она составляет минимум 44,1 КГц (44100 Гц).
Качество записи сильно зависит также от количества битов, используемых компьютером для кодирования каждого участка звука, полученного в результате дискретизации.
Представим, например, что для кодирования каждого такого участка компьютер использует 8 битов. Как известно, 8-битная ячейка может принимать одно из 256 значений. Но вдруг разнообразие интенсивности участков, полученных при дискретизации какого-то звука, оказалось более широким (например, 512 вариантов). В таком случае, компьютер "округлит" интенсивность участков до ближайших доступных значений чтобы "уложиться" в 256 вариантов и качество записи получится низким.
Количество битов, используемых для кодирования каждого участка звука, полученного при дискретизации, называется глубиной звука.
Глубины звука в 8-битов достаточно для кодирования простой речи. Но музыкальные произведения с такой глубиной будут звучать отвратительно. Поэтому гораздо чаще встречаются звуковые файлы, закодированные с глубиной 16, 24 или даже 32 бита.
Следует учитывать, что далеко не все устройства, предназначенные для воспроизведения "цифрового" звука, могут работать с файлами, закодированными с высокой частотой дискретизации и/или большой глубиной звука. Такие файлы могут проигрываться на одном компьютере, и "не открываться" на другом (если звуковая карта не поддерживает настолько высокий уровень дискретизации или глубины звука). 
Особенности бинарного кодирования видео
Видеозапись состоит из двух компонентов: звукового и графического.
Кодирование звуковой дорожки видеофайла в двоичный код осуществляется по тем же алгоритмам, что и кодирование обычных звуковых данных (см. предыдущий пункт).
Принципы кодирования видеоизображения схожи с кодированием растровой графики (рассмотрено выше), хотя и имеют некоторые особенности.
Как известно, видеозапись – это последовательность быстро меняющихся статических изображений (кадров). Одна секунда видео может состоять из 25 и больше картинок. При этом, каждый следующий кадр лишь незначительно отличается от предыдущего.
Учитывая эту особенность, алгоритмы кодирования видео, как правило, предусматривают запись лишь первого (базового) кадра. Каждый же последующий кадр формируются путем записи его отличий от предыдущего.
СИСТЕМЫ СЧИСЛЕНИЯ
Основные понятия
Система счисления — это совокупность правил записи чисел посредством конечного набора символов (цифр).
Системы счисления бывают:
непозиционными (в этих системах значение цифры не зависит от ее позиции — положения в записи числа);
позиционными (значение цифры зависит от позиции).
Непозиционные системы счисления
Примеры: унарная, римская, древнерусская и др.
Позиционные системы счисления
Основание системы счисления — количество различных знаков цифр, используемых в этой системе.
Вес разряда — отношение количественного эквивалента цифры в этом разряде к количественному эквиваленту той же цифры в нулевом разряде
pi = si, 
где i — номер разряда, а s — основание системы счисления.
Разряды числа нумеруются справа налево, причем младший разряд целой части (стоящий перед разделителем — запятой или точкой) имеет номер ноль. Разряды дробной части имеют отрицательные номера:
число 5 3 7 2 . 2 5
номера разрядов  3 2 1 0 -1 -2
Перевод в десятичную систему счисления
По определению веса разряда
pi = si,
где i — номер разряда, а s — основание системы счисления.
Тогда, обозначив цифры числа как ai, любое число, записанное в позиционной системе счисления, можем представить в виде:
x = ansn + an-1sn-1 + ... + a2s2 + a1s1 + a0s0 + a-1s-1 + ...Например, для системы счисления с основанием 4:
1302.24 = 1⋅43 + 3⋅42 + 0⋅41 + 2⋅40 + 2⋅4-1
Выполнив вычисления, мы получим значение исходного числа, записанное в десятичной системе счисления (точнее, в той, в которой производим вычисления). В данном случае:
1302.24 = 1⋅43 + 3⋅42 + 0⋅41 + 2⋅40 + 2⋅4-1 = 1⋅64 + 3⋅16 + 0⋅4 + 2⋅1 + 2⋅0,25 =
= 64 + 48 + 2 + 0,5 = 114,5
Таким образом, для перевода числа из любой системы счисления в десятичную следует:
пронумеровать разряды исходного числа;
записать сумму, слагаемые которой получаются как произведения очередной цифры на основание системы счисления, возведенное в степень, равную номеру разряда;
выполнить вычисления и записать полученный результат (указав основание новой системы счисления — 10).
Перевод из десятичной системы счисления
В общем случае для перевода целой части числа из десятичной системы счисления в систему с каким-либо другим основанием необходимо:
Выполнить последовательное деление с остатком исходного числа и каждого полученного частного на основание новой системы счисления.
Записать вычисленные остатки, начиная с последнего (т.е. в обратном порядке)
Примеры:

Системы счисления с кратными основаниями
При работе с компьютерами широко применяют двоичную систему счисления (поскольку на ней основано представление информации в компьютере), а также восьмеричную и шестнадцатеричную, запись в которых более компактна и удобна для человека. С другой стороны, благодаря тому, что 8 и 16 — степени 2, переход между записью в двоичной и одной из этих систем осуществляется без вычислений. 
Достаточно заменить каждый разряд шестнадцатеричной записи четырьмя (16=24) разрядами двоичной (и наоборот) по таблице. 

367665-95250
Примеры:
шестнадцатеричная -> двоичная
A 3 2 E
1010 0011 0010 1110
двоичная -> шестнадцатеричная
(00)10 1010 0111 1101
2 A 7 D
Аналогично происходит и перевод между двоичной и восьмеричной системой, только разряд восьмеричной соответствует трем разрядам двоичной (8=23)
Примеры:
восьмеричная -> двоичная
  5 3 2 1
  101 011 010 001
двоичная -> восьмеричная
(0)10 101 001 111 101
2 5 1 7 5
Арифметика
Арифметические операции в позиционной системе с любым основанием производятся по одним и тем же правилам: сложение, вычитарние и умножение «в столбик», а деление — «уголком». Рассмотрим пример выполнения действий сложения и вычитания в двоичной, восьмеричной и шестнадцатеричной системах счисления.
Арифметические операции в позиционных системах счисления
Рассмотрим основные арифметические операции: сложение, вычитание, умножение и деление. Правила выполнения этих операций в десятичной системе хорошо известны — это сложение, вычитание, умножение столбиком и деление углом. Эти правила применимы и ко всем другим позиционным системам счисления. Только таблицами сложения и умножения надо пользоваться особыми для каждой системы.
Сложение
Таблицы сложения легко составить, используя Правило Счета. 
Сложение в двоичной системе
Сложение в восьмеричной системе

                 Сложение в шестнадцатиричной системе
 При сложении цифры суммируются по разрядам, и если при этом возникает избыток, то он переносится влево.
    Пример 1. Сложим числа 15 и 6 в различных системах счисления.
       
Шестнадцатеричная: F16+616
Ответ: 15+6=
=2110  =101012  =258 =1516.  Проверка. Преобразуем полученные суммы к десятичному виду:
101012 = 24 + 22 + 20 = 16+4+1=21, 
258 = 2 . 81 + 5 . 80 = 16 + 5 = 21,
1516 = 1 . 161 + 5 . 160 = 16+5 = 21.
  Пример 2. Сложим числа 15, 7 и 3.


Шестнадцатеричная: F16+716+316
Ответ: 5+7+3 = 2510 = 110012 = 318 = 1916.  Проверка: 110012 = 24 + 23 + 20 = 16+8+1=25, 318 = 3 . 81 + 1 . 80 = 24 + 1 = 25,  1916 = 1 . 161 + 9 . 160 = 16+9 = 25. 
  Пример 3. Сложим числа 141,5 и 59,75.



   Ответ: 141,5 + 59,75 = 201,2510 = 11001001,012 = 311,28 = C9,416 
Проверка. Преобразуем полученные суммы к десятичному виду: 
11001001,012 = 27 + 26 + 23 + 20 + 2-2 = 201,25 
311,28 = 3 . 82 + 181 + 1 . 80 + 2 . 8-1 = 201,25 
C9,416 = 12 . 161 + 9 . 160 + 4 . 16-1 = 201,25
Вычитание
Пример 4. Вычтем единицу из чисел 102, 108 и 1016 
            Пример 5. Вычтем единицу из чисел 1002, 1008 и 10016. 
            Пример 6. Вычтем число 59,75 из числа 201,25.



   Ответ: 201,2510 - 59,7510 = 141,510 = 10001101,12 = 215,48 = 8D,816. 
Проверка. Преобразуем полученные разности к десятичному виду: 
10001101,12 = 27 + 23 + 22 + 20 + 2-1 = 141,5; 
215,48 = 2 . 82 + 1 . 81 + 5 . 80 + 4 . 8-1 = 141,5; 
8D,816 = 8 . 161 + D . 160 + 8 . 16-1 = 141,5.
Умножение
Выполняя умножение многозначных чисел в различных позиционных системах счисления, можно использовать обычный алгоритм перемножения чисел в столбик, но при этом результаты перемножения и сложения однозначных чисел необходимо заимствовать из соответствующих рассматриваемой системе таблиц умножения и сложения.
Умножение в двоичной системе
Умножение в восьмеричной системе

Ввиду чрезвычайной простоты таблицы умножения в двоичной системе, умножение сводится лишь к сдвигам множимого и сложениям. 
Пример 7. Перемножим числа 5 и 6.

 Ответ: 5 . 6 = 3010 = 111102 = 368. 
Проверка. Преобразуем полученные произведения к десятичному виду: 
111102 = 24 + 23 + 22 + 21 = 30; 
368 = 381 + 680 = 30. 
    Пример 8. Перемножим числа 115 и 51.

 Ответ: 115 . 51 = 586510 = 10110111010012 = 133518. 
Проверка. Преобразуем полученные произведения к десятичному виду: 
10110111010012 = 212 + 210 + 29 + 27 + 26 + 25 + 23 + 20 = 5865; 
133518 = 1 . 84 + 3 . 83 + 3 . 82 + 5 . 81 + 1 . 80 = 5865.
Д е л е н и е
Деление в любой позиционной системе счисления производится по тем же правилам, как и деление углом в десятичной системе. В двоичной системе деление выполняется особенно просто, ведь очередная цифра частного может быть только нулем или единицей. 
Пример 9. Разделим число 30 на число 6.

 Ответ: 30 : 6 = 510 = 1012 = 58.
    Пример 10. Разделим число 5865 на число 115.


Восьмеричная: 133518 :1638
 Ответ: 5865 : 115 = 5110 = 1100112 = 638. 
Проверка. Преобразуем полученные частные к десятичному виду: 
1100112 = 25 + 24 + 21 + 20 = 51; 638 = 6 . 81 + 3 . 80 = 51. 
    Пример 11. Разделим число 35 на число 14.


Восьмеричная: 438 : 168
 Ответ: 35 : 14 = 2,510 = 10,12 = 2,48. 
Проверка. Преобразуем полученные частные к десятичному виду: 
10,12 = 21 + 2 -1 = 2,5; 
2,48 = 2 . 80 + 4 . 8-1 = 2,5. 
АЛГЕБРА ЛОГИКИ. Булева алгебра. Элементы математической логики
В современном мире мы все чаще используем разнообразные машины и гаджеты. И не только тогда, когда необходимо применить буквально нечеловеческую силу: переместить груз, поднять его на высоту, вырыть длинную и глубокую траншею и т. д. Автомобили сегодня собирают роботы, еду готовят мультиварки, а элементарные арифметические расчеты производят калькуляторы. Все чаще мы слышим выражение «булева алгебра». Пожалуй, пришло время разобраться в роли человека в создании роботов и умении машин решать не только математические, но и логические задачи.
Логика
В переводе с греческого Логика – это упорядоченная система мышления, которая создает взаимосвязи между заданными условиями и позволяет делать умозаключения, основываясь на предпосылках и предположениях.
Довольно часто мы спрашиваем друг друга: «Логично?» Полученный ответ подтверждает наши предположения либо критикует ход мысли. Но процесс не останавливается: мы продолжаем рассуждать.
Порой количество условий (вводных) настолько велико, а взаимосвязи между ними столь запутанны и сложны, что человеческий мозг не в состоянии «переварить» все сразу. Может понадобиться не один месяц (неделя, год) для понимания происходящего. Но современная жизнь не дает нам таких временных интервалов на принятие решений. И мы прибегаем к помощи компьютеров. И вот тут-то и появляется алгебра логики, со своими законами и свойствами. Загрузив все исходные данные, мы позволяем компьютеру распознать все взаимосвязи, исключить противоречия и найти удовлетворительное решение.
В принципе, булева алгебра очень проста. Существуют высказывания (логические выражения), которые, с точки зрения математики, можно определить только двумя словами: «истина» или «ложь».
Например: «весной деревья расцветают» – истина, «летом идет снег» – ложь.
Вся прелесть этой математики заключается в том, что нет строгой необходимости использовать только числа. Для алгебры суждений вполне подходят любые высказывания с однозначным смыслом.
Таким образом, алгебра логики может быть использована буквально везде: в составлении расписаний и написании инструкций, анализе противоречивой информации о событиях и определении последовательности действий. Самое главное - понять, что совершенно неважно, как мы определили истинность или ложность высказывания. От этих «как» и «почему» нужно абстрагироваться. Значение имеет только констатация факта: истина-ложь.
Безусловно, для программирования важны функции алгебры логики, которые записываются соответствующими знаками и символами. И выучить их – это значит освоить новый иностранный язык. Нет ничего невозможного.
Основные понятия и определения
Не вдаваясь в глубины, разберемся с терминологией. Итак, булева алгебра предполагает наличие:
высказываний;
логических операций;
функций и законов.
Высказывания – любые утвердительные выражения, которые не могут быть истолкованы двузначно.
Они записываются в виде чисел (5 > 3) или формулируются привычными словами (слон – самое большое млекопитающее). При этом фраза «у жирафа нет шеи» также имеет право на существование, только булева алгебра определит её как «ложь».
Все высказывания должны носить однозначный характер, но они могут быть элементарными и составными. Последние используют логические связки. Т. е. в алгебре суждений составные высказывания образуются сложением элементарных посредством логических операций.
190518224500
Чтобы определиться с термином «логика высказываний», необходимо четко понимать, что же такое «высказывание».
Итак, высказывание представляет собой предложение, выстроенное грамматически правильно, и являющееся ложным или истинным. Данное понятие должно выражать определенный смысл. Например, выражение «канарейка есть птица» включает такие составные части: «канарейка» и «птица».
Именно поэтому одним из ключевых, исходных понятий логики и являются высказывания. Эти понятия должны описывать конкретную ситуацию, в которой будет либо утверждение чего-то, либо отрицание.
Истинным принято считать высказывание, если прослеживается соответствие реальности ситуации при ее описывании. Сами по себе «ложь» и «истина» определяют истинность высказываний.
Логика высказываний складывается из простых и сложных выражений. Так, простым считается высказывание, не включающее в свой состав другие выражения. А к сложным относятся выражения, которые получены из простых, логически связанных между собой высказываний.
Классическая логика высказываний может быть представлена общей теорией дедукции. Это именно та часть логики, в которой описываются не зависящие от структуры высказываний логические связи простых выражений.
Логика высказываний направлена на решение такой центральной задачи, как разделение правильных и неправильных схем рассуждения и систематизация первых. Чтобы получить правильный результат, необходимо сосредоточить свое внимание на специальных символах, которые могут представить ту или иную форму. Отсюда и обозначается интерес к таким незначительным на первый взгляд словам, как «или», «и» и т.д.
Операции булевой алгебры
Мы уже помним, что операции в алгебре суждений – логические. Подобно тому, как алгебра чисел использует арифметические операции для сложения, вычитания или сравнения чисел, элементы математической логики позволяют составить сложные высказывания, дать отрицание или вычислить конечный результат.
Логические операции для формализации и простоты записываются формулами, привычными для нас в арифметике. Свойства булевой алгебры дают возможность записывать уравнения и вычислять неизвестные. Логические операции обычно записывают с помощью таблицы истинности. Её столбцы определяют элементы вычислений и операцию, которая над ними производится, а строки показывают результат вычислений.
Основные логические действия
Самыми распространенными в булевой алгебре операциями являются отрицание (НЕ) и логические И и ИЛИ.
Так можно описать практически все действия в алгебре суждений. Изучим подробнее каждую из трех операций.
Отрицание (не) применяется только к одному элементу (операнду (объект математической операции, величина, на базе которой выполняется какая-либо операция)). Поэтому операцию отрицания называют унарной. Для записи понятия «не А» используют такие символы: ¬A, неA или !A.
В табличной форме это выглядит так:190518351500
Для функции отрицания характерно такое утверждение: если А истинно, то A – ложно. Например, «Луна вращается вокруг Земли» – истина; «Земля вращается вокруг Луны» – ложь.
Логическое умножение
Логическое И называют операцией конъюнкции.
Что это значит?
Во-первых, что применить ее можно к двум операндам, т. е. И – бинарная операция.
Во-вторых, что только в случае истинности обоих операндов (и А, и Б) истинно и само выражение. Пословица «Терпение и труд все перетрут» предполагает, что только оба фактора помогут человеку справиться со сложностями.
Для записи используются символы: A∧Б, A⋅Б или A&Б.
Конъюнкция – сложное высказывание, получаемое путем соединения двух простых выражений с помощью слова «И». Истинность конъюнкции подтверждается достоверностью всех высказываний, входящих в ее структуру. В случае, когда хоть один из ее членов ложный, вся конъюнкция имеет признак «ложь».
Конъюнкция аналогична умножению в арифметике. Иногда так и говорят – логическое умножение. Если перемножить элементы таблицы по строкам, мы получим результат, аналогичный логическому размышлению.
45148526797000Таблица истинности операции логического И:
Логическое сложение
Дизъюнкцией называют операцию логического ИЛИ. Она принимает значение истинности тогда, когда хотя бы одно из высказываний истинно (А или Б). Записывается это так: A∨Б, A+Б или A||Б.
Дизъюнкция подобна арифметическому сложению. Операция логического сложения имеет только одно ограничение: 1+1=1. Но мы же помним, что в цифровом формате математическая логика ограничена 0 и 1 (где 1 – истина, 0 - ложь).
Например, утверждение «в музее можно увидеть шедевр или встретить интересного собеседника» означает, что можно посмотреть произведения искусства, а можно познакомиться с интересным человеком. В то же время, не исключен вариант одновременного свершения обоих событий.
Таблица истинности операции логического ИЛИ:
451485000
Помимо основных логических операций математическая логика и теория алгоритмов использует производные. Под производными понимаются исключающее ИЛИ, импликация и эквивалентность.
Исключающее ИЛИᴓ
А В А XOR В
0 0 0
0 1 1
1 0 1
1 1 0
Импликация, или логическое следование – это высказывание, в котором одно действие является условием, а другое – следствием его выполнения. Иными словами, это предложение с предлогами «если... то».
«Любишь кататься, люби и саночки возить».
Т. е. для катания необходимо затянуть санки на горку. Если же нет желания съехать с горы, то и санки таскать не приходится.
Записывается это так:
A→Б или A⇒Б.
При определении импликации существует утверждение, что основание высказывания не может быть истинным при ложном следствии. Другими словами, данное понятие предполагает зависимость истинности или ложности выражения от значения его составляющих и способов их связей.
Несмотря на то, что импликация достаточно полезна для некоторых целей, она не очень согласуется с пониманием условной связи в общем виде. Так, при охватывании многих важных черт логического поведения высказывания данное понятие не может являться его адекватным описанием.
А В А=> В
0 0 1
0 1 1
1 0 0
1 1 1
Эквивалентность предполагает, что результирующее действие наступает только в том случае, когда истиной являются оба операнда. Например, ночь сменяется днем тогда (и только тогда), когда солнце встает из-за горизонта. На языке математической логики это утверждение записывается так: A≡Б, A⇔Б, A==Б.
А В А<=> В
0 0 1
1 0 0
0 1 0
1 1 1
Последовательность операций
Последовательность операций имеет немаловажное значение. Собственно, как и для алгебры, существует приоритетность функций, которые использует булева алгебра. Формулы могут упрощаться только при условии соблюдения значимости операций. Ранжируя от самых значимых до незначительных, получим такую последовательность:
1. Отрицание.
2. Конъюнкция.
3. Дизъюнкция, исключающее ИЛИ.
4. Импликация, эквивалентность.
Как видим, только отрицание и конъюнкция не имеют равных приоритетов. А приоритет дизъюнкции и исключающего ИЛИ равны, так же как и приоритеты импликации и эквивалентности.
Функции и законы
Итак, мы уже знаем, какие логические операции использует булева алгебра.
Функции описывают все свойства элементов математической логики и позволяют упрощать сложные составные условия задач.
Ассоциативность означает, что в высказываниях типа «и А, и Б, и В» последовательность перечисления операндов не играет роли.
Формулой это запишется так:
(A∧Б)∧В=A∧(Б∧В)=A∧Б∧В,
(A∨Б)∨В=A∨(Б∨В)=A∨Б∨В.
26098520066000Как видим, это свойственно не только конъюнкции, но и дизъюнкции.
Коммутативность утверждает, что результат конъюнкции или дизъюнкции не зависит от того, какой элемент рассматривался вначале:
A∧Б=Б∧A;
A∨Б=Б∨A.
Дистрибутивность позволяет раскрывать скобки в сложных логических выражениях. Правила схожи с раскрытием скобок при умножении и сложении в алгебре:
A∧(Б∨В)=A∧Б∨A∧В;
A∨Б∧В=(A∨Б)∧(A∨В).
Свойства единицы и нуля, которые могут быть одним из операндов, также аналогичны алгебраическим умножению на ноль или единицу и сложению с единицей:
A∧0=0,
A∧1=A;
A∨0=A,
A∨1=1.
Идемпотентность говорит нам о том, что если относительно двух равных операндов результат операции оказывается аналогичным, то можно «выбросить» лишние усложняющие ход рассуждений операнды. И конъюнкция, и дизъюнкция являются идемпотентными операциями.
Б∧Б=Б;
Б∨Б=Б.
Поглощение также позволяет нам упрощать уравнения. Поглощение утверждает, что когда к выражению с одним операндом применяется другая операция с этим же элементом, результатом оказывается операнд из поглощающей операции.
A∧Б∨Б=Б;
(A∨Б)∧Б=Б.
Другие законы булевой алгебры
Алгебра суждений развивается, и многие заинтересовавшиеся ученые сформулировали новые законы.
Наиболее известными считаются постулаты шотландского математика О. де Моргана. Он заметил и дал определение таким свойствам, как тесное отрицание, дополнение и двойное отрицание.
Тесное отрицание предполагает, что перед скобкой нет ни одного отрицания:
не (А или Б)= не А или НЕ Б.
Когда операнд отрицается, независимо от своего значения, говорят о дополнении: Б∧¬Б=0; Б∨¬Б=1.
Двойное отрицание само себя компенсирует. Т.е. перед операндом либо исчезает отрицание, либо остается только одно.
¬¬А=А.
Как построить таблицу истинности
Для любого логического выражения можно построить таблицу истинности. Эта таблица наглядно показывает, при каких значениях логических переменных выражение обращается в единицу или является истинным. С помощью составления таблиц истинности можно доказать равенство (или неравенство) двух сложных логических выражений.
Инструкция
1
Посчитайте количество переменных в выражении. Для n логических переменных понадобится 2^n строк таблицы истинности, не считая строки с заголовками. Затем посчитайте количество логических операций в выражении. Столбцов в таблице будет столько же, сколько операций плюс n столбцов для переменных.Пусть дано выражение с тремя переменными, записанное на рисунке. Переменных три, поэтому строк потребуется 8. Количество операций - 3, поэтому число столбцов с учетом переменных равно 6. Начертите таблицу и заполните ее заголовок.

2
Теперь заполните столбцы, надписанные названиями переменными, всеми возможными вариантами переменных. Чтобы не пропустить ни одного варианта, удобно представить для себя эти последовательности нулей и единиц в виде двоичных чисел от 0 до 2^n. Для трех переменных это двоичные числа от 0 до 8 или от 000 до 111 в двоичной системе счисления.

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

4
Затем подставляйте последовательно значения переменных в логические операции, указанные в заголовках столбцов, и записывайте в соответствующие ячейки таблицы, последовательно заполняя таблицу.


Приложенные файлы

  • docx 9481040
    Размер файла: 741 kB Загрузок: 0

Добавить комментарий