Математика в информатике
элективный курс по информатике и икт по теме

«Математика в  информатике».

Пояснительная записка.

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

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

Курс «Математика в  информатике» носит междисциплинарный характер. Вопросы, изучаемые в рамках данного курса, отчасти затрагиваются в базовом  курсе информатики. Но недостаточный уровень математической подготовки учащихся  не позволяет преподавателям  продвинуться дальше «бытового» уровня раскрытия основных понятий. Многие представленные разделы практически не разбираются в базовом курсе информатики. Курсу отводится 1 час в неделю в течение одного года обучения. Всего 34 часа.

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

Задачи курса:

Расширить представление учащихся о сферах применения  математики;

Дать представление о математических основах информатики;

Убедить в практической необходимости владения способами выполнения математический действий (на примере арифметических операций в q – ичных системах счисления);

Формирование положительной мотивации  к изучению математики.

В результате изучения этого курса учащиеся должны знать:

Содержание понятий «информация» и «количество информации»;

Содержание понятия «базис», «алфавит», «основание» для позиционных систем счисления;

Особенности арифметики в позиционных системах счисления;

Способы представления вещественных чисел в компьютере;

Принцип представления различных видов информации в компьютере;

Аксиомы и функции алгебры логики;

Логические схемы и логические выражения.

Программа курса:

Содержание программы.

Основы теории информации (10 часов).

Понятие информации.

Измерение информации.

Информация и вероятность.

Системы счисления (10 часов).

Общие сведения о системах счисления.

Представление чисел в позиционных системах счисления.

Арифметические операции в q – ичных системах счисления.

Перевод чисел из десятичной системы в q – ичную.

Представление информации в компьютере (8 часов).

Представление целых чисел.

Представление вещественных чисел.

Представление текстовой информации.

Представление графической информации.

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

Алгебра логики (6 часов).

Понятие высказывания. Логические операции.

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

Логические законы и правила преобразования логических выражений.

Логические устройства компьютера.

Глава 1.  Основы теории информации.

Понятие информации. Измерение информации.

Со словом "информация" знаком каждый.  Мы смотрим по телевизору информационные программы,  слушаем радиопередачи, читаем газеты  (информация!).  На  улице нас предупреждают дорожные знаки, сигналы светофора,  автомобильные гудки (опять  информация!).  Со всех  сторон  обрушивается всевозможная реклама (часто ненужная и не всегда правдивая информация). Информация проникает к нам в виде писем,  телеграмм и телефонных звонков. Учебники, справочники, словари и энциклопедии хранят в себе огромные запасы всевозможной информации. Создана целая индустрия информации, включающая в себя издательства, типографии, архивы, библиотеки, системы связи, различные технические устройства для быстрого поиска и обработки информации.

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

Однако само понятие "информация" оказывается совсем не простым  и однозначным и дать ему строгое определение очень трудно. Обратившись к толковому словарю, мы узнаем, что информация - это "сведения об окружающем мире и протекающих в нем процессах, воспринимаемые человеком или специальным устройством". Но относительно самой природы информации существует два противоположных мнения. Некоторые философы, математики, физики, биологи и особенно кибернетики  считают  информацию  всеобщим свойством материального мира, наряду с веществом и энергией.  Их аргументом  является  то,  что именно информация способствовала возникновению жизни. Другая точка зрения заключается в том,  что необходимость введения  понятия информации  возникает  лишь  с возникновением жизни,  так как все процессы, происходящие в "неживой природе" подчиняются только законам физики и химии, и могут быть объяснены и поняты без привлечения термина "информация",  В обычном (то есть житейском) смысле информация  означает  сумму сведений,  которую получает "некто" - человек или группа людей (или животных) - об окружающем  мире,  о самом себе, о "ком-то" другом или изучаемом явлении - сведений, с помощью которых он может точнее прогнозировать  результаты  своих действий  и отбирать способы использования своих возможностей для обеспечения собственных интересов и для  достижения  поставленных целей.

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

             Все в мире состоит из вещества и энергии.  Элементарные частицы.  атомы,  молекулы, минералы, планеты, живые существа, люди. Объединения  людей - все это существует независимо от нашего сознания. Каждое мгновение все это невообразимое множество различных объектов изменяется.  При этом мир становится "чуть-чуть" другим. Любое изменение сопровождается  затратами  энергии.  Одни  требуют больше  энергии,  другие  меньше,  но  затраты энергии происходят всегда. Вы, конечно, можете сказать, что существуют и такие изменения, при которых энергия не затрачивается, а появляется горение угля или пороха, ядерные реакции. На это можно возразить тем, что при этих изменениях происходит не "появление", а лишь высвобождение ранее запасенной энергии.  Съев утром бутерброд или тарелочку супа,  вы  запасаетесь энергией,  которая позволит вам произвести некоторые изменения в мире,  отвечающие вашим целям. Но это  запасенная  энергия  может быть использована с разной эффективностью. Выйдя из дома,  вы обнаруживаете, что начинается дождь и возвращаетесь за зонтом,  опоздали на автобус и вынуждены ждать следующего или идти пешком. Перед уроком вы обнаружили,  что взяли не те учебники или забыли тетрадь с домашним заданием и начинаете нервничать.  В результате всего этого,  запасенная вами за  завтраком энергия растрачивается впустую,  она оказалась израсходованной, а вы так и не произвели нужных вам  изменений,  полезных  для  вас действий. А  вот если бы вы сначала выглянули в окно и взяли зонт перед выходом на улицу, если бы вы точно знали расписание автобуса  или вышли немного пораньше,  если бы вы собрали свой портфель еще вчера - использование энергии было бы более эффективным.  Использование карты города избавляет от напрасных блужданий в поисках нужного вам места,  расположение в энциклопедии слов по алфавиту увеличивает скорость нахождения нужного вам слова. Использование информации повышает эффективность использования энергии.

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

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

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

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

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

Но обрабатывать и  использовать  информацию  человек  по-прежнему должен был сам.

             Кода появились машины,  человек, исполняющий работу,  стал превращаться в человека, управляющего работой. Действительно, нельзя "управлять лопатой",  но можно управлять экскаватором. Управлять - значит влиять на процесс,  совершаемый кем-то (или чем-то).

Причем влиять так,  чтоб этот процесс приводил к заранее намеченной цели.  Конечно управлять человеку приходилось и раньше: кучер управлял лошадьми,  капитан кораблем, садовник - ростом растений, правительство- государством. Но с появлением машин человеку пришлось вводить в них элементы "самоуправления",  элементы автоматики.  Это  привело  в середине 20 века к возникновению новой науки кибернетики,  которая занялась,  изучением процессов управления с новой  точки зрения.  Обнаружилось,  что и в технических устройствах.  и в живых организмах,  и в общественных системах принципы управления практически одинаковы и все они,  так или иначе, базируются на понятии информации.

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

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

             Вычислительные машины, или компьютеры, первоначально использовались  в основном для вычислений.  Но оказалось,  что с их помощью можно обрабатывать любую информацию, которой придана форма, позволяющая ввести ее в машину. Такой "универсальной" формой стали двоичные цифры (0 и  1).  Этими  двумя  элементарными  знаками (сигналами) можно "записывать" числа и буквы,  изображения и звуки,  логические понятии и последовательности действий. Физическая природа  этих знаков также может быть самой разнообразной,  главное,  чтоб их можно было отличить друг от  друга:  высокий/низкий уровень напряжения в электрической цепи, большая/меньшая степень намагниченности участка магнитной ленты или магнитного диска, наличие/отсутствие отверстия в перфоленте или перфокарте и т.д.

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

Измерение информации.

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

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

 Единица измерения количества информации называется бит.

Сообщение, уменьшающее неопределенность знаний человека в 2 раза, несет для него 1 бит информации.

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

2х= N.

Данная формула является показательным уравнением относительно неизвестной х. Решением такого уравнения является    х = log2N  .     Если N равно целой степени двойки, то такое уравнение можно решить «в уме». В противном случае воспользуемся таблицей логарифмов.

Пример 1. 1. При бросании монеты сообщение о результате жребия (например, выпал орел) несет 1 бит информации, поскольку количество возможных вариантов результата равно 2 (орел или решка). Оба эти варианта равновероятны.

Решение: 2х= 2, х=1 бит. Вывод: в любом случае сообщение о б одном событии из 2 равновероятных несет 1 бит информации.

Пример 1.2. При игре в кости используется кубик с 6 гранями. Сколько бит информации получает игрок при каждом бросании кубика?

Решение: выпадение каждой грани кубика равновероятно. Поэтому 2х= 6, х = log26, х=2, 585 бит.

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

              Множество символов, используемых при записи текста, называется алфавитом. Полное количество символов в алфавите называется мощностью (размером) алфавита. Если допустить, что все символы алфавита встречаются в тексте с одинаковой частотой (равновероятно), то количество информации, которое несет каждый символ, вычисляется по формуле i = log2N, где N – мощность алфавита.

        Один символ из алфавит мощностью 256 несет в тексте 8 бит информации. Такое количество информации называется байт. Алфавит из 256 символов используется для представления текстов в компьютере.

1 байт = 8 бит.

           Если весь текст состоит из К символов, то при алфавитном подходе размер содержащейся в нем информации равен

I=K*i,

где  i – информационный вес 1 символа в используемом алфавите.

        Для измерения информации используются и более крупные единицы:

1 Кбайт (килобайт)=210 байт=1024 байта.

1 Мбайт (мегабайт)=210 Кбайт=1024 Кбайта.

1 Гбайт (гигабайт)=210 Мбайт=1024 Мбайта.

Пример 1.3. Книга, набранная с помощью компьютера, содержит 150 страниц; на каждой странице – 40 строк, в каждой строке – 60 символов. Каков объем информации в книге?

Решение: Мощность компьютерного алфавита равна 256. 1 символ несет 1 байт информации. Значит, страница содержит 40*60=2400 байт информации. Объем всей информации в книге:

2400*150=360000 байт.

360000/1024=351,5625 Кбайт.

351,5625/1024=0,34332275 Мбайт.

Пример 1.4. Племя мульти имеет 32-символьный алфавит. Племя Пульти использует 64-х символьный алфавит. Вожди племен обменялись письмами. Письмо племени Мульти содержало 80 символов, а письмо племени Пульти 70 символов. Сравните объемы информации, содержащейся в письмах.

Решение: Найдем информационный вес одного символа в каждом письме. i= log2N , i1= log232=5 бит, i2= log264=6 бит. Размер информации, содержащийся в письмах равен    I=K*i , I1=80*5=400 бит, I2=70*6=420 бит. I1/ I2=400/420=20/21.                                   

Информация и вероятность.

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

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

Количественная связь между вероятностью события (р) и количеством информации в сообщении о нем (i) выражается формулой

i= log2(1/р).

Пример 1.5. В коробке имеется 50 шаров. Из них 40 белых и 10 черных. Определить количество информации в сообщении о попадании белого шара и черного шара.

Решение: i= log2(1/р), iб= log2(1/(40/50))=0,321928, iч= log2(1/(10/50))=2,321928.

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

                                            (*)                                          

где I – количество информации,

 N – количество возможных событий,

 pi- вероятности отдельных событий.

Если события равновероятны, то количество информации определяется по формуле:    

I = log2N       (**)

  или из показательного уравнения:         N = 2I     (***)

Пример 1.5. После экзамена по информатике, который сдавали ваши друзья, объявляются оценки («2», «3», «4» или «5»). Какое количество информации будет нести сообщение об оценке  учащегося A, который выучил лишь половину билетов, и сообщение об оценке учащегося B, который выучил все билеты.

Решение: Опыт показывает, что для учащегося A все четыре оценки (события) равновероятны и тогда количество информации, которое несет сообщение об оценке можно вычислить по формуле (**):

I = log24 = 2 бит

На основании опыта можно также предположить, что для учащегося B наиболее вероятной оценкой является «5» (p1 = 1/2),  вероятность оценки «4» в два раза меньше (p2 = 1/4),  а вероятности оценок «2» и «3» еще в два раза меньше  (p3 = p4  = 1/8). Так как события неравновероятны, воспользуемся для подсчета количества информации в сообщении формулой (*):

I = -(1/2Elog21/2 + 1/4Elog21/4 + 1/8Elog21/8 + 1/8Elog21/8) бит = 1,75 бит

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

Глава 2.  Системы счисления

"Все есть число", — говорили пифагорийцы, подчеркивая необычайно важную роль чисел в практической деятельности. Известно множество способов представления чисел.  В любом  случае число изображается  символом  или группой символов (словом) некоторого алфавита. Будем называть такие символы цифрами. Для представления чисел используются непозиционные и позиционные системы счисления.

Непозиционные системы счисления

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

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

Единичная система — не самый удобный способ записи чисел. Записывать таким образом большие количества утомительно, да и сами записи при этом получаются очень длинными. С течением времени возникли иные, более удобные, системы счисления.

Древнеегипетская десятичная непозиционная система счисления. Примерно  в третьем тысячелетии до нашей эры древние египтяне придумали свою числовую систему, в которой для обозначения ключевых чисел 1, 10, 100 и т.д. использовались специальные значки — иероглифы. Все остальные числа составлялись из этих ключевых при помощи операции сложения. Система счисления Древнего Египта является десятичной, но непозиционной.

В непозиционных системах счисления количественный эквивалент  каждой  цифры не зависит  от ее положения (места, позиции) в записи числа.

Например, чтобы изобразить 3252 рисовали три цветка лотоса (три тысячи), два свернутых пальмовых листа (две сотни), пять дуг (пять десятков) и два шеста (две единицы). Величина числа не зависела от того, в каком порядке располагались составляющие его знаки: их можно было записывать сверху вниз, справа налево или вперемежку.

Римская система счисления. Примером непозиционной системы, которая  сохранилась  до  наших  дней, может служить система счисления, которая применялась более двух с половиной тысяч лет назад в Древнем Риме. В основе римской системы счисления лежали знаки I (один палец) для числа 1, V (раскрытая ладонь) для числа 5, X (две сложенные ладони) для 10, а для обозначения чисел 100, 500 и 1000 стали применять первые буквы соответствующих латинских слов (Сentum — сто, Demimille — половина тысячи,  Мille — тысяча).

Чтобы записать число, римляне разлагали его на сумму тысяч, полутысяч, сотен, полусотен, десятков, пятков, единиц. Например, десятичное число 28 представляется следующим образом:

XXVIII=10+10+5+1+1+1 (три десятка, пяток, три единицы).

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

        Например, IX — обозначает 9, XI — обозначает 11.

        Десятичное число 99 имеет следующее представление: XCIХ = -10+100-1+10.

Римскими цифрами  пользовались  очень долго.  Еще 200 лет назад в деловых бумагах числа должны были обозначаться римскими цифрами  (считалось, что обычные арабские цифры легко подделать). Римская система  счисления сегодня используется,  в основном,  для наименования знаменательных дат, томов, разделов и глав в книгах.

Алфавитные системы счисления. Более совершенными непозиционными системами счисления были алфавитные системы. К числу таких систем счисления относились греческая, славянская, финикийская и другие. В них числа от 1 до 9, целые количества десятков (от 10 до 90) и целые количества сотен (от 100 до 900) обозначались буквами алфавита.

        В алфавитной системе счисления Древней Греции числа 1, 2, ..., 9 обозначались первыми девятью буквами греческого алфавита, например и т.д. Для обозначения чисел 10, 20, ..., 90 применялись следующие 9 букв (  и т.д.),  а для обозначения чисел 100, 200, ..., 900 — последние 9 букв ( и т.д.). Например, число 141 обозначалось

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

Рис. 1. Древнерусская алфавитная система счисления

В России славянская нумерация сохранилась до конца XVII века. При Петре I возобладала так называемая арабская нумерация, которой мы пользуемся и сейчас. Славянская нумерация сохранилась только в богослужебных книгах.

Непозиционные системы счисления имеют ряд существенных недостатков:

1. Существует постоянная  потребность введения новых знаков для записи больших чисел.

2. Невозможно представлять дробные и отрицательные числа.

3. Сложно выполнять арифметические операции, так как не существует алгоритмов их выполнения.

Позиционные системы счисления

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

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

        Возможно множество позиционных систем,  так как за основание системы счисления можно принять любое число не меньшее 2.  Наименование системы счисления соответствует ее основанию (десятичная, двоичная, восьмеричная, шестнадцатеричная и т. д.). 

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

            В системе счисления с основанием q  (q-ичная  система  счисления) единицами разрядов служат последовательные степени числа q,  иначе говоря, q единиц какого-либо разряда образуют единицу следующего  разряда. Для записи чисел в q-ичной системе счисления требуется q различных цифр (0,1,...,q-1).

            В позиционной системе счисления любое  вещественное  число  в развернутой форме может быть представлено в следующем виде:  

Аq= ± (an-1qn-1+an-2qn-2+...+a0q0+a-1q-1+a-2q-2+...+a-mq-m)        или       Аq = ± aiqi

        Здесь А — само число,

q — основание системы счисления,

ai —цифры, принадлежащие алфавиту данной системы счисления,

n — число целых разрядов числа,

m — число дробных разрядов числа.

        Свернутой формой записи числа называется запись в виде A=an-1an-2...a1a0,a-1...a-m

         Именно такой формой записи чисел мы и пользуемся в повседневной жизни. Иначе свернутую форму записи называют естественной или цифровой.

 Пример 2.1. Десятичное число А10=4718,63 в развернутой форме запишется так:

А10=4·103+7·102+1·101+8·100+6·10-1+3·10-2

Пример 2.2. Двоичная система счисления.

        В двоичной системе счисления основание q=2. В этом случае формула (2.4) принимает вид:

А2= ± (an-12n-1+an-22n-2+...+a020+a-12-1+a-22-2+...+a-m2-m)

Здесь аi — возможные цифры (0, 1).

Итак, двоичное  число  представляет собой цепочку из нулей и единиц. При этом оно имеет достаточно  большое  число  разрядов.  Быстрый рост  числа  разрядов — самый существенный недостаток двоичной системы счисления.

        Записав двоичное число А2=1001,1 в развернутом виде и произведя вычисления, получим это число, выраженное в десятичной системе счисления:

А2=1·23+0·22+0·21+1·20+1·2-1 = 8+1+0,5 = 9,510. 

Пример 2.3. Восьмеричная система счисления.

Основание: q=8.

Алфавит: 0, 1, 2, 3, 4, 5, 6, 7.

Записав восьмеричное число А8=7764,1  в развернутом виде и произведя вычисления, получим это число, выраженное в десятичной системе счисления:

А8=7·83+7·82+6·81+4·80+1·8-1 = 3584 + 448 + 48 + 4 + 0,125 = 4084,12510

Пример 2.4.  Шестнадцатеричная система счисления.

Основание: q=16.

Алфавит: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Здесь только десять цифр из шестнадцати имеют общепринятое  обозначение 0,1, …9. Для записи остальных цифр (10, 11, 12, 13, 14 и 15) обычно используются первые пять букв латинского алфавита.

Таким образом, запись 3АF16 означает:

3АF16 = 3·162+10·161+15·160 = 768+160+15 = 94310.

Пример 2.5. Запишем начало натурального ряда чисел в  десятичной  и  двоичной системах счисления:

Арифметические операции в q – ичных системах счисления.

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

Рассмотрим подробно каждую операцию.

Сложение. Таблица двоичного сложения предельно проста.  Только в одном случае, когда производится сложение 1+1, происходит перенос в старший разряд.

Пример 2.6. Рассмотрим несколько примеров сложения двоичных чисел:

     1001             1101                   11111             1010011,111

   +                     +                     +                       +

     1010               1011                      1                     11001,110

     ------               ------            ---------              --------------

   10011             11000             100000             1101101,101

       Вычитание. При выполнении операции вычитания всегда  из  большего по  абсолютной  величине числа вычитается меньшее и ставится соответствующий знак.  В таблице вычитания 1 с чертой означает заем в  старшем разряде.

Пример 2.7. Рассмотрим несколько примеров вычитания двоичных чисел:

10111001,1 - 10001101,1 = 101100,0

101011111 - 110101101 = -1001110

     10111001,1                     110110101

    -                                       -

     10001101,1                     101011111

    ---------------                    --------------

     00101100,0                     001010110

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

Пример 2.8.  Рассмотрим несколько примеров умножения двоичных чисел:

11001 ×  1101 = 101000101

11001,01 ×  11,01 = 1010010,0001

         11001                        11001,01

      ×   1101                    ×        11,01

        ---------                       -----------

         11001                         1100101

     11001                         1100101

   11001                         1100101

 -------------                  -----------------

 101000101                 1010010,0001

 Вы видите, что умножение сводится к сдвигам множимого и сложениям.

Деление. Операция деления выполняется по алгоритму, подобному алгоритму выполнения операции деления в десятичной  системе  счисления.

Пример 2.9. Рассмотрим пример деления двоичных чисел:

101000101 : 1101 = 11001

       101000101  1101

  -     1101           11001

           1110

          -1101

                1101

               -1101

                      0

        Сложение в других системах счисления. Ниже приведена таблица сложения в восьмеричной системе счисления:

Перевод целых чисел из одной системы счисления в другую.

Можно сформулировать алгоритм перевода целых чисел из системы с основанием p в систему с основанием q:

1. Основание новой системы счисления  выразить  цифрами  исходной системы счисления  и  все  последующие действия производить в исходной системе счисления.

2. Последовательно выполнять деление данного числа  и  получаемых целых частных на основание новой системы счисления до тех пор, пока не получим частное, меньшее делителя.

3. Полученные  остатки,  являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления.

4. Составить число в новой системе счисления, записывая его, начиная с последнего остатка.

Пример 2.10.  Перевести  десятичное число 17310 в восьмеричную систему счисления:

 Получаем:  17310=2558

 Пример 2.11. Перевести десятичное число 17310 в шестнадцатеричную систему счисления:

Получаем: 17310=AD16.

Пример 2.12.  Перевести десятичное число 1110 в двоичную систему счисления. Рассмотренную  выше последовательность действий (алгоритм перевода) удобнее изобразить так:

Получаем: 1110=10112.

 Пример 2.13.  Иногда более удобно записать алгоритм перевода в форме таблицы. Переведем десятичное число 36310  в двоичное число.

Получаем: 36310=1011010112

Перевод дробных чисел из одной системы  счисления  в другую.

Можно сформулировать алгоритм перевода правильной  дроби с основанием p в дробь с основанием q:

1. Основание новой системы счисления  выразить  цифрами  исходной системы счисления  и  все  последующие действия производить в исходной системе счисления.

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

3. Полученные целые части произведений,  являющиеся цифрами числа в новой системе счисления,  привести в соответствие с алфавитом  новой системы счисления.

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

Пример 2.14.  Перевести число 0,6562510 в восьмеричную систему счисления.

Получаем: 0,6562510=0,528

 Пример 2.15.  Перевести число 0,6562510 в  шестнадцатеричную  систему счисления.

Получаем: 0,6562510=0,А81 

 Пример 2.16.  Перевести  десятичную  дробь 0,562510 в двоичную систему счисления.

Получаем: 0,562510=0,10012 

 Пример 2.17. Перевести в двоичную систему счисления десятичную дробь 0.710.

        . . .

        Очевидно, что  этот процесс может продолжаться бесконечно,  давая все новые и новые знаки  в  изображении  двоичного  эквивалента  числа 0,710. Так,  за четыре шага мы получаем число 0,10112, а за семь шагов число 0,10110012,  которое является более точным представлением  числа 0,710 в двоичной системе счисления,  и т.д.  Такой бесконечный процесс обрывают на некотором шаге, когда считают, что получена требуемая точность представления числа.

Перевод произвольных чисел.

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

Пример 2.19. Перевести число 17,2510 в двоичную систему счисления.

Получаем: 17,2510=1001,012

Пример 2.20.  Перевести число 124,2510 в восьмеричную систему.

Получаем: 124,2510=174,28

Перевод чисел из системы счисления с основанием 2 в систему счисления с основанием 2n и обратно.

        Перевод целых чисел. Если основание q-ичной системы счисления является степенью  числа 2, то  перевод  чисел из q-ичной системы счисления в 2-ичную и обратно можно проводить по более простым правилам.

Для того, чтобы целое двоичное число записать в системе счисления с основанием q=2n, нужно:

1. Двоичное число разбить справа налево на группы по n  цифр в каждой.

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

3. Рассмотреть каждую группу как n-разрядное двоичное число и  записать ее соответствующей цифрой в системе счисления с основанием q=2n.

 Пример 2.21.  Число 1011000010001100102 переведем в восьмеричную систему счисления.

        Разбиваем число справа налево на триады и под каждой из них записываем соответствующую восьмеричную цифру:

        Получаем восьмеричное представление исходного числа: 5410628.

Пример 2.22.  Число 10000000001111100001112 переведем в шестнадцатеричную систему счисления.

        Разбиваем число  справа налево на тетрады и под каждой из них записываем соответствующую шестнадцатеричную цифру:

        Получаем шестнадцатеричное    представление    исходного   числа: 200F8716.

Перевод дробных чисел. Для  того,  чтобы  дробное двоичное число записать в системе счисления с основанием q=2n, нужно:

1. Двоичное число разбить слева направо на группы по n  цифр в каждой.

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

3. Рассмотреть каждую группу как n-разрядное двоичное число и  записать ее соответствующей цифрой в системе счисления с основанием q=2n.

 Пример 2.23.  Число  0,101100012 переведем в восьмеричную систему счисления.

        Разбиваем число слева направо на триады и под каждой из них записываем соответствующую восьмеричную цифру:

        Получаем восьмеричное представление исходного числа: 0,5428.

Пример 2.24.  Число  0,1000000000112  переведем  в шестнадцатеричную систему счисления.         Разбиваем число слева направо на тетрады и под каждой из них записываем соответствующую шестнадцатеричную цифру:

        Получаем шестнадцатеричное    представление    исходного   числа: 0,80316

         Перевод произвольных чисел. Для того, чтобы произвольное двоичное число записать в системе счисления с основанием q=2n, нужно:

1. Целую часть данного  двоичного  числа  разбить  справа налево, а дробную — слева направо на группы по n цифр в каждой.

2. Если в последних левой и/или правой группах окажется меньше n разрядов, то их надо дополнить слева и/или справа нулями  до нужного числа разрядов;

3.  Рассмотреть  каждую группу как n-разрядное двоичное число и записать ее соответствующей цифрой в системе счисления с основанием q=2n

Пример 2.25.  Число 111100101,01112 переведем в восьмеричную систему счисления.

        Разбиваем целую и дробную части числа на триады и под каждой из них записываем соответствующую восьмеричную цифру:

        Получаем восьмеричное представление исходного числа: 745,348.

Пример 2.26.  Число  11101001000,110100102 переведем в шестнадцатеричную систему счисления.

        Разбиваем целую и дробную части числа на тетрады  и под каждой из них записываем соответствующую шестнадцатеричную цифру:

        Получаем шестнадцатеричное представление исходного числа: 748,D216.

        Перевод чисел из систем счисления с основанием q=2n в двоичную систему. Для того, чтобы произвольное число, записанное в системе счисления с основанием q=2n, перевести в двоичную систему счисления, нужно каждую цифру этого числа заменить ее n-значным эквивалентом в двоичной системе счисления.

Пример 2.27.  Переведем шестнадцатеричное число 4АС3516 в  двоичную систему счисления.

        В соответствии с алгоритмом:

Получаем: 10010101100001101012.

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

С помощью программы Системы счисления можно посмотреть информацию по каждой системе. Эта программа является обучающей программой по системам счисления и содержит разделы, посвященные различным системам счисления (единичным, древнеегипетской десятичной непозиционной, вавилонской шестнадцатеричной, римской, алфавитным системам, индийской мультипликативной, шестнадцатеричной, десятичной и двоичной)., а также содержит встроенный Калькулятор, который позволяет переводить числа из одной системы счисления в другую.

Глава 3. Представление информации в компьютере.

Представление целых чисел.

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

Для хранения целых неотрицательных чисел отводится одна ячейка памяти (8 бит). Например, число A2 = 101010102  будет хранится в ячейке памяти следующим образом:

Максимальное значение целого неотрицательного числа достигается в случае, когда во всех ячейках хранятся единицы. Для n-разрядного представления оно будет равно:

2n - 1

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

Минимальное число соответствует восьми нулям, хранящимся в восьми ячейках памяти, и равно нулю.

Максимальное число соответствует восьми единицам, хранящимся в ячейках памяти и равно:

A = 1E27 +1E26 +1E25 + 1E24 + 1E23 + 1E22 + 1E21 + 1E20 = 1E28 – 1 = 25510

Диапазон изменения целых неотрицательных чисел чисел от 0 до 255.

Для хранения целых чисел со знаком отводится две ячейки памяти (16 бит), причем старший (левый) разряд отводится под знак числа (если число положительное, то в знаковый разряд записывается 0, если число отрицательное записывается 1).

Представление в компьютере положительных чисел с использованием формата «знак-величина» называется прямым кодом числа. Например, число 200210 = 111110100102 будет представлено в 16-ти разрядном представлении следующим образом:

При представлении целых чисел в n-разрядном представлении со знаком максимальное положительное число (с учетом выделения одного разряда на знак) равно:

A = 2n-1 - 1

Пример 3.2. Определить максимальное положительное число, которое может хранится в оперативной памяти в формате целое  число со знаком.

A10 = 215 – 1 = 3276710 

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

Дополнительный код представляет собой дополнение модуля отрицательного числа А до 0, поэтому в n-разрядной компьютерной арифметике:

2n - |A| + |A| ≡ 0

Это равенство тождественно справедливо, т.к. в компьютерной n-разрядной арифметике 2n ≡ 0. Действительно, двоичная запись такого числа состоит из одной единицы и n нулей, а в n-разрядную ячейку может уместиться только n младших разрядов, т.е. n нулей.

Пример 3.3. Записать дополнительный код отрицательного числа –2002 для 16-ти разрядного компьютерного представления.

Проведем вычисления в соответствии с определением дополнительного кода:

Проведем проверку с использованием десятичной системы счисления. Дополнительный код 6353410 в сумме с модулем отрицательного числа 200210  равен 6553610, т.е. дополнительный код дополняет модуль отрицательного числа до 216 (до нуля 16-ти разрядной компьютерной арифметики).

Для получения дополнительного кода отрицательного числа можно использовать довольно простой алгоритм:

1.        Модуль числа записать прямым кодом в n двоичных разрядах;

2.        Получить обратный код числа, для этого значения всех бит инвертировать (все единицы заменить на нули и все нули заменить на единицы);

3.        К полученному обратному коду прибавить единицу.

Пример 3.4. Записать дополнительный код отрицательного числа –2002 для 16-ти разрядного компьютерного представления с использованием алгоритма.

При n-разрядном представлении отрицательного числа А дополнительным кодом старший разряд выделяется для хранения знака числа (единицы). В остальных разрядах записывается положительное число:

2n-1 - |A|.

Чтобы число было положительным должно выполняться условие:

|A| ≤ 2n-1 

Следовательно, максимальное значение модуля числа А в n-разрядном представлении равно:

|A| = 2n-1 

Тогда, минимальное отрицательное число равно:

A = -2n-1 

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

Максимальное положительное целое число (с учетом выделения одного разряда на знак) равно:

A = 231 – 1 = 2 147 483 64710 

Минимальное отрицательное целое число равно:

A = -231 = -2 147 483 64810

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

Пример 3.6. Выполнить арифметическое действие 300010 - 500010 в 16-ти разрядном компьютерном представлении.

Представим положительное число в прямом, а отрицательное число в дополнительном коде:

Сложим прямой код положительного числа с дополнительным кодом отрицательного числа. Получим результат в дополнительном коде:

Переведем полученный дополнительный код в десятичное число:

1)       Инвертируем дополнительный код: 0000011111001111

2)       Прибавим к полученному коду 1 и получим модуль отрицательного числа:

0000011111001111

                                +  0000000000000001

0000011111010000

3)       Переведем в десятичное число и припишем знак отрицательного числа: -2000.

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

Представление вещественных чисел.

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

Формат чисел с плавающей запятой базируется на экспоненциальной форме записи, в которой может быть представлено любой число. Так число А может быть представлено в виде:                                              A = m×qn

где        m – мантисса числа

        q – основание системы счисления,

        n – порядок числа.

Для однозначности представления чисел c плавающей запятой  используется нормализованная форма, при которой мантисса  отвечает условию:

1/n ≤ |m| < 1.

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

Пример 3.7. Преобразуйте десятичное число 888,888, записанное в естественной форме, в экспоненциальную форму с нормализованной мантиссой.

888,888 = 0,888888×103 

Нормализованная мантисса m = 0,888888, порядок n = 3.

Число в форме с плавающей запятой занимает в  памяти компьютера четыре (число обычной точности)  или восемь байт (число двойной точности). При записи числа с плавающей запятой выделяются разряды для хранения знака мантиссы, знака порядка, порядка и мантиссы.

Диапазон изменения чисел определяется количеством разрядов, отведенных для хранения порядка числа, а точность (количество значащих цифр) определяется количеством разрядов, отведенных для хранения мантиссы.

Пример 3.8. Определить максимальное число и его точность для формата чисел обычной точности, если для хранения порядка и его знака отводится 8 разрядов, а для хранения мантиссы и ее знака 24 разряда.

Максимальное значение порядка числа составит 11111112 = 12710, и, следовательно, максимальное значение числа составит:

2127  = 1,7014118346046923173168730371588×1038 

Точность вычислений определяется количеством разрядов, отведенных для хранения мантиссы чисел. Максимальное значение положительной мантиссы равно:  

223 - 1  ≈ 223  = 2(10х2,3)  ≈ 10002,3  = 10(3х2,3)  ≈ 107 

Таким образом максимальное значение чисел обычной точности с учетом возможной точности вычислений составит 1,701411×1038 (количество значащих цифр десятичного числа в данном случае ограничено 7 разрядами).

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

После выполнения операции выравнивания одинаковые разряды чисел оказываются расположенными в одних и тех же разрядах ячеек памяти. Теперь операции сложения и вычитания чисел сводятся к сложению или вычитанию мантисс.

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

Пример 3.9. Произвести сложение чисел 0,1×23 и 0,1×25 в формате с плавающей запятой.

Произведем выравнивание порядков и сложение мантисс:

             0,001×25 

            +0,100×25

             0,101×25 

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

Пример 3.10. Произвести умножение чисел 0,1×23 и 0,1×25 в формате с плавающей запятой.

После умножения будет получено число 0,01×28, которое после нормализации примет вид  0,1×27.

Кодирование текстовой информации.

           В настоящее время большая часть пользователей при помощи компьютера обрабатывает текстовую информацию, которая состоит из символов: букв, цифр, знаков препинания и др.

           Традиционно для того чтобы закодировать один символ используют количество информации равное 1 байту, т. е. I = 1 байт = 8 бит. При помощи формулы, которая связывает между собой количество возможных событий К и количество информации I, можно вычислить сколько различных символов можно закодировать (считая, что символы - это возможные события):

К = 2I = 28 = 256,

   т. е. для представления текстовой информации можно использовать алфавит мощностью 256 символов.

           Суть кодирования заключается в том, что каждому символу ставят в соответствие двоичный код от 00000000 до 11111111 или соответствующий ему десятичный код от 0 до 255.

           Необходимо помнить, что в настоящее время для кодировки русских букв используют пять различных кодовых таблиц (КОИ - 8, СР1251, СР866, Мас, ISO), причем тексты, закодированные при помощи одной таблицы не будут правильно отображаться в другой кодировке. Наглядно это можно представить в виде фрагмента объединенной таблицы кодировки символов.

           Одному и тому же двоичному коду ставится в соответствие различные символы.

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

           Начиная с 1997 г. последние версии Microsoft Windows&Office поддерживают новую кодировку Unicode, которая на каждый символ отводит по 2 байта, а, поэтому, можно закодировать не 256 символов, а 65536 различных символов.

           Чтобы определить числовой код символа можно или воспользоваться кодовой таблицей, или, работая в текстовом редакторе Word 6.0 / 95. Для этого в меню нужно выбрать пункт "Вставка" - "Символ", после чего на экране появляется диалоговая панель Символ. В диалоговом окне появляется таблица символов для выбранного шрифта. Символы в этой таблице располагаются построчно, последовательно слева направо, начиная с символа Пробел (левый верхний угол) и, кончая, буквой "я" (правый нижний угол).

           Для определения числового кода символа в кодировке Windows (СР1251) нужно при помощи мыши или клавиш управления курсором выбрать нужный символ, затем щелкнуть по кнопке Клавиша. После этого на экране появляется диалоговая панель Настройка, в которой в нижнем левом углу содержится десятичный числовой код выбранного символа.

Пример 3.11.  Два текста содержат одинаковое количество символов. Первый текст записан на русском языке, а второй на языке племени нагури, алфавит которого состоит из 16 символов. Чей текст несет большее количество информации?

 Решение.
I = К * а (информационный объем текста равен произведению числа символов на информационный вес одного символа). Т.к. оба текста имеют одинаковое число символов (К), то разница зависит от информативности одного символа алфавита (а).

2а1 = 32,

т.е. а1 = 5 бит,

2а2 = 16, т.е. а2 = 4 бит.

I1 = К * 5 бит, I2 = К * 4 бит.

Значит, текст, записанный на русском языке в 5/4 раза несет больше информации.

Пример 3.12.  Объем сообщения, содержащего 2048 символов, составил 1/512 часть Мбайта. Определить мощность алфавита.

Решение.
I = 1/512 * 1024 * 1024 * 8 = 16384 бит. - перевели в биты информационный объем сообщения.
а = I / К = 16384 /1024 =16 бит - приходится на один символ алфавита.
216 = 65536 символов - мощность использованного алфавита.
Именно такой алфавит используется в кодировке Unicode, который должен стать международным стандартом для представления символьной информации в компьютере.

Кодирование графической информации.

           В середине 50-х годов для больших ЭВМ, которые применялись в научных и военных исследованиях, впервые в графическом виде было реализовано представление данных. В настоящее время широко используются технологии обработки графической информации с помощью ПК. Графический интерфейс пользователя стал стандартом "де-факто" для ПО разных классов, начиная с операционных систем. Вероятно, это связано со свойством человеческой психики: наглядность способствует более быстрому пониманию. Широкое применение получила специальная область информатики, которая изучает методы и средства создания и обработки изображений с помощью программно-аппаратных вычислительных комплексов, - компьютерная графика. Без нее трудно представить уже не только компьютерный, но и вполне материальный мир, так как визуализация данных применяется во многих сферах человеческой деятельности. В качестве примера можно привести опытно-конструкторские разработки, медицину (компьютерная томография), научные исследования и др.

          Особенно интенсивно технология обработки графической информации с помощью компьютера стала развиваться в 80-х годах. Графическую информацию можно представлять в двух формах: аналоговой или дискретной. Живописное полотно, цвет которого изменяется непрерывно - это пример аналогового представления, а изображение, напечатанное при помощи струйного принтера и состоящее из отдельных точек разного цвета - это дискретное представление. Путем разбиения графического изображения (дискредитации) происходит преобразование графической информации из аналоговой формы в дискретную. При этом производится кодирование - присвоение каждому элементу конкретного значения в форме кода. При кодировании изображения происходит его пространственная дискредитация. Ее можно сравнить с построением изображения из большого количества маленьких цветных фрагментов (метод мозаики). Все изображение разбивается на отдельные точки, каждому элементу ставится в соответствие код его цвета. При этом качество кодирования будет зависеть от следующих параметров: размера точки и количества используемых цветов. Чем меньше размер точки, а, значит, изображение составляется из большего количества точек, тем выше качество кодирования. Чем большее количество цветов используется (т. е. точка изображения может принимать больше возможных состояний), тем больше информации несет каждая точка, а, значит, увеличивается качество кодирования. Создание и хранение графических объектов возможно в нескольких видах - в виде векторного, фрактального или растрового изображения. Отдельным предметом считается 3D (трехмерная) графика, в которой сочетаются векторный и растровый способы формирования изображений. Она изучает методы и приемы построения объемных моделей объектов в виртуальном пространстве. Для каждого вида используется свой способ кодирования графической информации.

         Растровое изображение. 

           При помощи увеличительного стекла можно увидеть, что черно-белое графическое изображение, например из газеты, состоит из мельчайших точек, составляющих определенный узор - растр. Во Франции в 19 веке возникло новое направление в живописи - пуантилизм. Его техника заключалась в том, что на холст рисунок наносился кистью в виде разноцветных точек. Также этот метод издавна применяется в полиграфии для кодирования графической информации. Точность передачи рисунка зависит от количества точек и их размера. После разбиения рисунка на точки, начиная с левого угла, двигаясь по строкам слева направо, можно кодировать цвет каждой точки. Далее одну такую точку будем называть пикселем (происхождение этого слова связано с английской аббревиатурой "picture element" - элемент рисунка). Объем растрового изображения определяется умножением количества пикселей (на информационный объем одной точки, который зависит от количества возможных цветов. Качество изображения определяется разрешающей способностью монитора. Чем она выше, то есть больше количество строк растра и точек в строке, тем выше качество изображения. В современных ПК в основном используют следующие разрешающие способности экрана: 640 на 480, 800 на 600, 1024 на 768 и 1280 на 1024 точки. Так как яркость каждой точки и ее линейные координаты можно выразить с помощью целых чисел, то можно сказать, что этот метод кодирования позволяет использовать двоичный код для того чтобы обрабатывать графические данные.

           Если говорить о черно-белых иллюстрациях, то, если не использовать полутона, то пиксель будет принимать одно из двух состояний: светится (белый) и не светится (черный). А так как информация о цвете пикселя называется кодом пикселя, то для его кодирования достаточно одного бита памяти: 0 - черный, 1 - белый. Если же рассматриваются иллюстрации в виде комбинации точек с 256 градациями серого цвета (а именно такие в настоящее время общеприняты), то достаточно восьмиразрядного двоичного числа для того чтобы закодировать яркость любой точки. В компьютерной графике чрезвычайно важен цвет. Он выступает как средство усиления зрительного впечатления и повышения информационной насыщенности изображения. Как формируется ощущение цвета человеческим мозгом? Это происходит в результате анализа светового потока, попадающего на сетчатку глаза от отражающих или излучающих объектов. Принято считать, что цветовые рецепторы человека, которые еще называют колбочками, подразделяются на три группы, причем каждая может воспринимать всего один цвет - красный, или зеленый, или синий.

         Цветовые модели. 

           Если говорить о кодировании цветных графических изображений, то нужно рассмотреть принцип декомпозиции произвольного цвета на основные составляющие. Применяют несколько систем кодирования: HSB, RGB и CMYK. Первая цветовая модель проста и интуитивно понятна, т. е. удобна для человека, вторая наиболее удобна для компьютера, а последняя модель CMYK-для типографий. Использование этих цветовых моделей связано с тем, что световой поток может формироваться излучениями, представляющими собой комбинацию " чистых" спектральных цветов : красного, зеленого, синего или их производных. Различают аддитивное цветовоспроизведение (характерно для излучающих объектов) и субтрактивное цветовоспроизведение (характерно для отражающих объектов). В качестве примера объекта первого типа можно привести электронно-лучевую трубку монитора, второго типа - полиграфический отпечаток.

   1) Модель HSB характеризуется тремя компонентами: оттенок цвета(Hue), насыщенность цвета (Saturation) и яркость цвета (Brightness). Можно получить большое количество произвольных цветов, регулируя эти компоненты. Эту цветовую модель лучше применять в тех графических редакторах, в которых изображения создают сами, а не обрабатывают уже готовые. Затем созданное свое произведение можно преобразовать в цветовую модель RGB, если ее планируется использовать в качестве экранной иллюстрации, или CMYK, если в качестве печатной, Значение цвета выбирается как вектор, выходящий из центра окружности. Направление вектора задается в угловых градусах и определяет цветовой оттенок. Насыщенность цвета определяется длиной вектора, а яркость цвета задается на отдельной оси, нулевая точка которой имеет черный цвет. Точка в центре соответствует белому (нейтральному) цвету, а точки по периметру - чистым цветам.

   2) Принцип метода RGB заключается в следующем: известно, что любой цвет можно представить в виде комбинации трех цветов: красного (Red, R), зеленого (Green, G), синего (Blue, B). Другие цвета и их оттенки получаются за счет наличия или отсутствия этих составляющих.По первым буквам основных цветов система и получила свое название - RGB. Данная цветовая модель является аддитивной, то есть любой цвет можно получить сочетание основных цветов в различных пропорциях. При наложении одного компонента основного цвета на другой яркость суммарного излучения увеличивается. Если совместить все три компоненты, то получим ахроматический серый цвет, при увеличении яркости которого происходит приближение к белому цвету.

   При 256 градациях тона (каждая точка кодируется 3 байтами) минимальные значения RGB (0,0,0) соответствуют черному цвету, а белому - максимальные с координатами (255, 255, 255). Чем больше значение байта цветовой составляющей, тем этот цвет ярче. Например, темно-синий кодируется тремя байтами ( 0, 0, 128), а ярко-синий (0, 0, 255).

   3) Принцип метода CMYK. Эта цветовая модель используется при подготовке публикаций к печати. Каждому из основных цветов ставится в соответствие дополнительный цвет (дополняющий основной до белого). Получают публикаций к печати. Каждому из основных цветов ставится в соответствие дополнительный цвет (дополняющий основной до белого). Получают дополнительный цвет за счет суммирования пары остальных основных цветов. Значит, дополнительными цветами для красного является голубой (Cyan,C) = зеленый + синий = белый - красный, для зеленого - пурпурный (Magenta, M) = красный + синий = белый - зеленый, для синего - желтый (Yellow, Y) = красный + зеленый = белый - синий. Причем принцип декомпозиции произвольного цвета на составляющие можно применять как для основных, так и для дополнительных, то есть любой цвет можно представить или в виде суммы красной, зеленой, синей составляющей или же в виде суммы голубой, пурупурной, желтой составляющей. В основном такой метод принят в полиграфии. Но там еще используют черный цвет (BlacК, так как буква В уже занята синим цветом, то обозначают буквой K). Это связано с тем, что наложение друг на друга дополнительных цветов не дает чистого черного цвета.

           Различают несколько режимов представления цветной графики:
         а) полноцветный (True Color);

         б) High Color;

         в) индексный.

           При полноцветном режиме для кодирования яркости каждой из составляющих используют по 256 значений (восемь двоичных разрядов), то есть на кодирование цвета одного пикселя (в системе RGB) надо затратить 8*3=24 разряда. Это позволяет однозначно определять 16,5 млн цветов. Это довольно близко к чувствительности человеческого глаза. При кодировании с помощью системы CMYK для представления цветной графики надо иметь 8*4=32 двоичных разряда.

           Режим High Color - это кодирование при помощи 16-разрядных двоичных чисел, то есть уменьшается количестко двоичных разрядов при кодировании каждой точки. Но при этом значительно уменьшается диапазон кодируемых цветов.

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

           Соответствие между количеством отображаемых цветов (К) и количеством бит для их кодировки (а) находиться по формуле:      

К = 2а.

Двоичный код изображения, выводимого на экран, хранится в видеопамяти. Видеопамять - это электронное энергозависимое запоминающее устройство. Размер видеопамяти зависит от разрешающей способности дисплея и количества цветов. Но ее минимальный объем определяется так, чтобы поместился один кадр (одна страница) изображения, т.е. как результат произведения разрешающей способности на размер кода пикселя.

Vmin = M * N * a.

Векторное и фрактальное изображения. 

Векторное изображение - это графический объект, состоящий из элементарных отрезков и дуг. Базовым элементом изоражения является линия. Как и любой объект, она обладает свойствами: формой (прямая, кривая), толщиной., цветом, начертанием (пунктирная, сплошная). Замкнутые линии имеют свойство заполнения (или другими объектами, или выбранным цветом). Все прочие объекты векторной графики составляются из линий. Так как линия описывается математически как единый объект, то и объем данных для отображения объекта средствами векторной графики значительно меньше, чем в растровой графике. Информация о векторном изображении кодируется как обычная буквенно-цифровая и обрабатывается специальными программами.

           К программным средствам создания и обработки векторной графики относятся следующие ГР: CorelDraw, Adobe Illustrator, а также векторизаторы (трассировщики) - специализированные пакеты преобразования растровых изображений в векторные.

           Фрактальная графика основывается на математических вычислениях, как и векторная. Но в отличии от векторной ее базовым элементом является сама математическая формула. Это приводит к тому, что в памяти компьютера не хранится никаких объектов и изображение строится только по уравнениям. При помощи этого способа можно строить простейшие регулярные структуры, а также сложные иллюстрации, которые иммитируют ландшафты.

Пример 3.13. Известно, что видеопамять компьютера имеет объем 512 Кбайт. Разрешающая способность экрана 640 на 200. Сколько страниц экрана одновременно разместится в видеопамяти при палитре

     а) из 8 цветов;  

     б) 16 цветов; 

     в) 256 цветов?

Сколько бит требуется, чтобы закодировать информацию о 130 оттенках?

Нетрудно подсчитать, что 8 (то есть 1 байт), поскольку при помощи 7 бит можно сохранить номер оттенка о 0 до 127, а 8 бит хранят от 0 до 255. Легко видеть, что такой способ кодирования неоптимален: 130 заметно меньше 255. Подумайте, как уплотнить информацию о рисунке при его записи в файл, если известно, что
         а) в рисунке одновременно содержится только 16 цветовых оттенков из 138 возможных;
         б) в рисунке присутствуют все 130 оттенков одновременно, но количество точек, закрашенных разными оттенками, сильно различаются.

   Решение.
а) очевидно, что для хранения информации о 16 оттенках достаточно 4 бита (половина байта). Однако так как эти 16 оттенков выбраны из 130, то они могут иметь номера, не умещающиеся в 4 битах. Поэтому воспользуемся методом палитр. Назначим 16 используемым в нашем рисунке оттенкам свои “локальные” номера от 1 до 15 и закодируем весь рисунок из расчета 2 точки на байт. А затем допишем к этой информации (в конец содержащего ее файла) таблицу соответствия, состоящую из 16 пар байтов с номерами оттенков: 1 байт - наш “локальный” номер в данном рисунке, второй - реальный номер данного оттенка. (когда вместо последнего используется закодированная информация о самом оттенке, например, сведения об яркости свечения “электроннык пушек” Red, Green, Blue электронно-лучевой трубки, то такая таблица и будет представлять собой палитру цветов). Если рисунок достаточно велик, выигрыш в объеме полученного файла будет значительным;

б) попытаемся реализовать простейший алгоритм архивации информации о рисунке. Назначим трем оттенкам, которыми закрашено минимальное количество точек, коды 128 - 130, а остальным оттенкам - коды 1 -127. Будем записывать в файл (котрый в этом случае представлыет собой не последовательность байтов, а сплошной битовый поток) семибитные коды для оттенков с номерами от 1 до 127. Для оставшихся же трех оттенков в битовом потоке будем записывать число-признак - семибитный 0 - и сразу за ним двухбитный “локальный” номер, а в конце файла добавим таблицу соответствия “локальных”и реальных номеров. Так как оттенки с кодами 128 – 130 встречаются редко, то семибитных нулей будет немного.

Заметим, что постановка вопросов в данной задаче не исключает и другие варианты решения, без привязки к цветовому составу изображения - архивацию:
         а) на основе выделения последовательности точек, закрашенных одинаковыми оттенками и замены каждой из этих последовательностей на пару чисел (цвет),(количество) (этот принцип лежит в основе графического формата РСХ);
         б) путем сравнения пиксельных строк (запись номеров оттенков точек первой страницы целиком, а для последующих строк запись номеров оттенков только тех точек, оттенки которых отличаются от отенков точек, стоящих в той же позиции в предыдущей строке, - это основа формата GIF);

         в) с помощью фрактального алгоритма упаковки изображений (формат YPEG). (ИО 6,1999)

Пример 3.14. Определить глубину цвета в графическом режиме True Color, в котором палитра состоит из более чем 4 миллиардов (4 294 967 296) цветов.

Решение: I = log242 949 67 296 = 32 бит.

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

Пример 3.15. Определить объем видеопамяти компьютера, который необходим для реализации графического режима монитора High Color с разрешающей способностью 1024´768 точек и палитрой из 65536 цветов.

Решение: Глубина цвета составляет:  I = log265 536 = 16 бит

Количество точек изображения равно:    1024´768 = 786 432

Требуемый объем видеопамяти равен:    16 бит ´ 786 432 =  12 582 912 бит » 1,2 Мбайта.

Важнейшими характеристиками монитора являются размеры его экрана, которые задаются величиной его диагонали в дюймах (15”, 17”, 21” и т.д.) и размером точки экрана (0,25 мм или 0,28 мм), а разрешающая способность экрана монитора задается количеством точек по вертикали и горизонтали (640´480, 800´600 и т.д.). Следовательно, для каждого монитора существует физически максимально возможная разрешающая способность экрана.

Пример 3.16. Определить максимально возможную разрешающую способность экрана для монитора с диагональю 15” и размером точки экрана 0,28 мм.

Выразим размер диагонали в сантиметрах:  2,54 см ´ 15 = 38,1 см

Определим соотношение между высотой и шириной экрана для режима 1024´768 точек:

768 : 1024 = 0,75

Определим ширину экрана. Пусть ширина экрана равна L, тогда высота равна 0,75L. По теореме Пифагора имеем:

L2 + (0,75L)2 = 38,12

1,5625L2 = 1451,61

L2  » 929

L »  30,5 см

Количество точек по ширине экрана равно:   305 мм : 0,28 мм = 1089

Максимально возможным разрешением экрана монитора является 1024´768.

Кодирование звуковой информации.

Мир наполнен самыми разнообразными звуками: тиканье часов и гул моторов, завывание ветра и шелест листьев, пение птиц и голоса людей. О том, как рождаются звуки и что они собой представляют люди начали догадываться очень давно. Еще древнегреческий философ и ученый - энциклопедист Аристотель, исходя из наблюдений, объяснял природу звука, полагая, что звучащее тело создает попеременное сжатие и разрежение воздуха. Так, колеблющаяся струна то разряжает, то уплотняет воздух, а из-за упругости воздуха эти чередующиеся воздействия передаются дальше в пространство - от слоя к слою, возникают упругие волны. Достигая нашего уха, они воздействуют на барабанные перепонки и вызывают ощущение звука.

           На слух человек воспринимает упругие волны, имеющие частоту где-то в пределах от 16 Гц до 20 кГц (1 Гц - 1 колебание в секунду). В соответствии с этим упругие волны в любой среде, частоты которых лежат в указанных пределах, называют звуковыми волнами или просто звуком. В учении о звуке важны такие понятия как тон и тембр звука. Всякий реальный звук, будь то игра музыкальных инструментов или голос человека, - это своеобразная смесь многих гармонических колебаний с определенным набором частот.

           Колебание, которое имеет наиболее низкую частоту, называют основным тоном, другие - обертонами. 

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

           Музыкальный звук можно характеризовать тремя качествами: тембром, т. е. окраской звука, которая зависит от формы колебаний, высотой, определяющейся числом колебаний в секунду (частотой), и громкостью, зависящей от интенсивности колебаний.

           Компьютер широко применяют в настоящее время в различных сферах. Не стала исключением и обработка звуковой информации, музыка. До 1983 года все записи музыки выходили на виниловых пластинках и компакт-кассетах. В настоящее время широкое распространение получили компакт-диски. Если имеется компьютер, на котором установлена студийная звуковая плата, с подключенными к ней MIDI-клавиатурой и микрофоном, то можно работать со специализированным музыкальным программным обеспечением.

           Условно его можно разбить на несколько видов:

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

 и другие.

           К первой группе относятся все служебные программы операционной системы. Так, например, win 95 и 98 имеют свои собственные программы микшеры и утилиты для воспроизведения/записи звука, проигрывания компакт-дисков и стандартных MIDI - файлов. Установив звуковую плату можно при помощи этих программ проверить ее работоспособность. Например, программа Фонограф предназначена для работы с wave-файлами (файлы звукозаписи в формате Windows). Эти файлы имеют расширение .WAV . Эта программа предоставляет возможность воспроизводить, записывать и редактировать звукозапись приемами, аналогичными приемам работы с магнитофоном. Желательно для работы с Фонографом подключить микрофон к компьютеру. Если необходимо сделать звукозапись, то нужно определиться с качеством звука, так как именно от нее зависит продолжительность звукозаписи. Возможная продолжительность звучания тем меньше, чем выше качество записи. При среднем качестве записи можно удовлетворительно записывать речь, создавая файлы продолжительностью звучания до 60 секунд. Примерно 6 секунд будет продолжительность записи, имеющая качество музыкального компакт - диска.

           А как же происходит кодирование звука? С самого детства мы сталкиваемся с записями музыки на разных носителях: грампластинках, кассетах, компакт-дисках и т.д. В настоящее время существует два основных способах записи звука: аналоговый и цифровой. Но для того чтобы записать звук на какой-нибудь носитель его нужно преобразовать в электрический сигнал.

           Это делается с помощью микрофона. Самые простые микрофоны имеют мембрану, которая колеблется под воздействием звуковых волн. К мембране присоединена катушка, перемещающаяся синхронно с мембраной в магнитном поле. В катушке возникает переменный электрический ток. Изменения напряжения тока точно отражают звуковые волны.

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

           Звуковую информацию можно представить в дискретной или аналоговой форме. Их отличие в том, что при дискретном представлении информации физическая величина изменяется скачкообразно («лесенкой»), принимая конечное множество значений. Если же информацию представить в аналоговой форме, то физическая величина может принимать бесконечное количество значений, непрерывно изменяющихся.

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

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

           На мультимедийных звуковых картах можно найти аналоговые микрофонный предусилитель и микшер.

   Цифро-аналоговое и аналого-цифровое преобразование звуковой информации. 

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

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

           В упрощенном виде принцип работы АЦП заключается в следующем: он измеряет через определенные промежутки времени амплитуду сигнала и передает дальше, уже по цифровому тракту, последовательность чисел, несущих информацию об изменениях амплитуды.

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

Семпл - это промежуток времени между двумя измерениями амплитуды аналогового сигнала .

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

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

Параметры семплирования

           Важными параметрами семплирования являются частота и разрядность.
   

Частота - количество измерений амплитуды аналогового сигнала в секунду.

           Если частота семплирования не будет более чем в два раза превышать частоту верхней границы звукового диапазона, то на высоких частотах будут происходить потери.         Это объясняет то, что стандартная частота для звукового компакт-диска - это частота 44.1 кГц. Так как диапазон колебаний звуковых волн находится в пределах от 20 Гц до 20 кГц, то количество измерений сигнала в секунду должно быть больше, чем количество колебаний за тот же промежуток времени. Если же частота дискредитации значительно ниже частоты звуковой волны, то амплитуда сигнала успевает несколько раз измениться за время между измерениями, а это приводит к тому, что цифровой отпечаток несет хаотичный набор данных. При цифро-аналоговом преобразовании такой семпл не передает основной сигнал, а только выдает шум.

           В новом формате компакт-дисков Audio DVD за одну секунду сигнал измеряется 96 000 раз, т.е. применяют частоту семплирования 96 кГц. Для экономии места на жестком диске в мультимедийных приложениях довольно часто применяют меньшие частоты: 11, 22, 32 кГц. Это приводит к уменьшению слышимого диапазона частот, а, значит, происходит сильное искажение того, что слышно.

           Если в виде графика представить один и тот же звук высотой 1 кГц (нота до седьмой октавы фортепиано примерно соответствует этой частоте), но семплированный с разной частотой , то будут видны различия. Одно деление на горизонтальной оси , которая показывает время, соответствует 10 семплам. Масштаб взят одинаковый см. приложения рисунок 1.13). Можно видеть, что на частоте 11 кГц примерно пять колебаний звуковой волны приходится на каждые 50 семплов, то есть один период синусоиды отображается всего при помощи 10 значений. Это довольно неточная передача. В то же время, если рассматривать частоту оцифровки 44 кГц, то на каждый период синусоиды приходится уже почти 50 семплов. Это позволяет получить сигнал хорошего качества.

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

           Для кодирования значения амплитуды используют принцип двоичного кодирования. Звуковой сигнал должен быть представленным в виде последовательности электрических импульсов (двоичных нулей и единиц). Обычно используют 8, 16-битное или 20-битное представление значений амплитуды. При двоичном кодировании непрерывного звукового сигнала его заменяют последовательностью дискретных уровней сигнала. От частоты дискредитации (количества измерений уровня сигнала в единицу времени) зависит качество кодирования. С увеличением частоты дискредитации увеличивается точность двоичного представления информации. При частоте 8 кГц (количество измерений в секунду 8000) качество семплированного звукового сигнала соответствует качеству радиотрансляции, а при частоте 48 кГц (количество измерений в секунду 48000) - качеству звучания аудио- CD.

           Если использовать 8-битное кодирование, то можно достичь точность изменения амплитуды аналогового сигнала до 1/256 от динамического диапазона цифрового устройства (28 = 256).

           Если использовать 16-битное кодирование для представления значений амплитуды звукового сигнала, то точность измерения возрастет в 256 раз.

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

           Вспомним формулу К = 2a . Здесь К - количество всевозможных звуков (количество различных уровней сигнала или состояний), которые можно получить при помощи кодирования звука а битами В настоящее время появился новый бытовой цифровой формат Audio DVD, который использует разрядность 24 бита и частоту семплирования 96 кГц. С его помощью можно избежать выше рассмотренного недостатка 16-битного кодирования.

           На современные цифровые звуковые устройства устанавливаются 20-битные преобразователи. Звук так и остается 16-битным, преобразователи повышенной разрядности устанавливают для улучшения качества записи на низких уровнях. Их принцип работы заключается в следующем: исходный аналоговый сигнал оцифровывается с разрядностью 20 бит. Затем цифровой сигнальный процессор DSP  понижает его разрядность до 16 бит. При этом используется специальный алгоритм вычислений, при помощи которого можно снизить искажения низкоуровневых сигналов. Обратный процесс наблюдается при цифро-аналоговом преобразовании: разрядность повышается с 16 до 20 бит при использовании специального алгоритма, который позволяет более точно определять значения амплитуды. То есть звук остается 16-разрядным, но имеется общее улучшение качества звучания.

Пример 3.17.  Подсчитать, сколько места будет занимать одна минута цифрового звука на жестком диске или любом другом цифровом носителе, записанного с частотой
      а) 44.1 кГц;
      б) 11 кГц;
      в) 22 кГц;
      г) 32 кГц
и разрядностью 16 бит.

Решение.
а) Если записывают моносигнал с частотой 44.1 кГц, разрядностью 16 бит (2 байта), то каждую минуту аналого-цифровой преобразователь будет выдавать 441000 * 2 * 60 = 529000 байт (примерно 5 Мб) данных об амплитуде аналогового сигнала, который в компьютере записываются на жесткий диск.  Если записывают стереосигнал, то 1058000 байт (около 10 Мб)

б) для частот 11, 22, 32 кГц расчеты производятся аналогично.

Пример 3.18.  Какой информационный объем имеет моноаудиофайл, длительность звучания которого 1 секунда, при среднем качестве звука (16 бит, 24 кГц)?

Решение.
16 бит * 24000 = 384000 бит = 48000 байт = 47 кБайт

Пример 3.19.  Рассчитайте объем стереоаудиофайла длительностью 20 секунд при 20-битном кодировании и частоте дискредитации 44.1 кГц.

Решение.
20 бит * 20 * 44100 * 2 = 35280000 бит = 4410000 байт = 4.41 Мб

Пример 3.20. Определить количество уровней звукового сигнала при использовании устаревших 8-битных звуковых карт.

 Решение.    К = 28 = 256.

Пример 3.21. Оцените информационный объем высокачественного стереоаудиофайла длительностью звучания 1 минута, если "глубина" кодирования 16 бит, а частота дискретизации 48 кГц.

Информационный объем звукового файла длительностью в 1 секунду равен:

16 бит ´ 48 000 ´ 2 = 1 536 000 бит = 187,5 Кбайт

Информационный объем  звукового файла длительностью 1 минута равен:

187,5 Кбайт/с ´ 60 с » 11 Мбайт

Самостоятельная работа ( а) - первый вариант, б) - второй).

1. Привести пример
      а) аналогового способа представления звуковой информации;
      б) дискретного способа представления звуковой информации.

2. Что называется
      а) частотой дискредитации (семплирования);
      б) семплом.

3. Опишите
      а) в чем заключается принцип двоичного кодирования звука;
      б) от каких параметров зависит качество двоичного кодирования звука.

Хранение информации.

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

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

Пример 3.22. Какие физические воздействия (магнитные поля, нагревание, удары, загрязнения) могут привести к потере информации:

а) на гибких магнитных дисках;

б) на жестких магнитных дисках;

в) на оптических дисках.  

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

Пример 3.23. Определить объем генетической информации  молекулы ДНК человека, которая состоит из около 6 миллиардов нуклеотидов четырех типов (A, G, T, C), которые являются знаками генетического алфавита.

 Мощность генетического алфавита равна четырем, следовательно, каждый знак (нуклеотид) несет количество информации, которое можно определить по формуле 2.2:

I = log24 = 2 бита

Объем генетической информации в ДНК человека составляет:

2 бита ´ 6 000 000 000 » 11,2 Гбайта.

Пример 3.24. Какое количество ячеек оперативной памяти будет занято словом «информатика», записанным в формате Unicode.

Оперативная память компьютера состоит из ячеек, объем которых равен 1 байту.

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

Пример 3.25. Какое максимальное количество страниц текста, содержащего 60 символов в строке и 40 строк на странице, может содержать текстовый файл без символов форматирования (формат TXT), сохраненный в кодировке Windows на гибком магнитном диске.

На гибком магнитном диске формата 3,5” минимальным адресуемым элементом является сектор емкостью 512 байт. Всего таких секторов 2880, из них для хранения данных отводится 2847 секторов, один сектор (1-ый) отводится для размещения загрузчика операционной системы и 32 сектора отводится для хранения каталога диска и таблицы размещения файлов FAT.

Информационный объем гибкого диска, предназначенный для хранения данных, составляет:  512 байт ´ 2847 = 1423,5 Кбайт

Информационный объем страницы составляет:  1 байт ´ 60 ´ 40 = 2400 байт » 2,34 Кбайта

Максимальное количество страниц в текстовом файле, размещенном на гибком магнитном диске, составляет:   1423,5 Кбайт : 2,34 Кбайт » 608

Пример 3.26. Какой информационный объем будет занимать  текстовый файл, содержащий слово «информатика», сохраненный в кодировке Windows на гибком магнитном диске формата 3,5”, на жестком диске 50 Гбайт с FAT16 и с FAT32?

Минимальным адресуемым элементом жесткого диска является кластер, размер которого зависит от типа используемой таблицы размещения файлов FAT и емкости жесткого диска. Таблица FAT16 позволяет адресовать 216 = 65536 кластеров, что приводит к большим размерам кластеров на жестких дисках большой емкости и нерациональному использованию дискового пространства.

Таблица FAT32 логически разбивает жесткий диск на кластеры, содержащие по восемь секторов. Таким образом, независимо от информационной емкости жесткого диска размер кластера составляет 4 Кбайта.

Информационный объем текста равен:    1 байт ´ 11 = 11 байт

На гибком диске этот файл будет занимать один сектор, т.е. 512 байт.

На жестком диске с FAT16 файл будет занимать один кластер, объем которого равен:

50 Гбайт : 65536 = 800 Кбайт.

На жестком диске с FAT32 файл будет занимать один кластер, объем которого равен 4 Кбайта.

Глава 4.   Алгебра логики.

Понятие высказывания. Логические операции.

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

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

Понятие. Понятие - это форма мышления, отражающая наиболее существенные свойства  предмета, отличающие его от других предметов. В структуре каждого понятия нужно различать две стороны: содержание и объем. Содержание понятия составляет совокупность существенных признаков предмета. Чтобы раскрыть содержание понятия, следует выделить признаки, необходимые и достаточные для выделения данного предмета по отношению к другим предметам.

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

Между множествами (объемами понятий) могут быть различные виды отношений:

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

     пересечение, когда объемы понятий частично совпадают;

     подчинения, когда объем одного понятия полностью входит в объем другого и т.д.

Для наглядной геометрической иллюстрации объемов понятий и соотношений между ними используются диаграммы Эйлера-Венна. Если имеются какие-либо понятия A, B, C и т.д., то объем каждого понятия (множество) можно представить в виде круга, а отношения между этими объемами (множествами) в виде пересекающихся кругов.

Пример 4.1. Отобразить с помощью диаграммы Эйлера-Венна соотношение между объемами понятий натуральные числа и четные числа.

Объем понятия натуральные числа включает в себя множество целых положительных чисел А, а объем понятия четные числа включает в себя множество отрицательных и положительных четных чисел В. Эти множества пересекаются, т.к. включают в себя множество положительных четных чисел С.

Совокупность всех существующих множеств образует всеобщее универсальное множество 1, которое позволяет отобразить множество логически противоположное к заданному. Так, если задано множество А, то существует множество НЕ А, которое объединяет все объекты, невходящие во множество А. Множество НЕ А дополняет множество А до универсального множества 1.

Пример 4.2. Отобразить с помощью диаграммы Эйлера-Венна множество натуральных чисел А и множество НЕ А.

На диаграммы Эйлера-Венна универсальное множество 1 изображается в виде прямоугольника, множество А в форме круга, а множество НЕ А в форме прямоугольник минус круг.

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

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

            Обоснование истинности или ложности простых высказываний решается вне алгебры  логики.  Например,  истинность  или  ложность  высказывания: "Сумма углов треугольника равна 180 градусов" устанавливается геометрией, причем — в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского — ложным.

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

          Высказывание называется простым, если никакая его часть сама не является высказыванием. Высказывание, состоящее из простых высказываний, называются составным (сложным). 

          Высказывания имеют определенную логическую форму. Понятие о предмете мысли называется субъектом и обозначается буквой S, а понятие о свойствах и отношениях предмета мысли называется предикатом и обозначается буквой P. Оба эти понятия -  субъект и предикат называются   терминами суждения. Отношения   между   субъектом  и  предикатом    выражается связкой  «есть», «не есть», «является», «состоит» и т.д.    

Таким образом, каждое высказывание состоит из трех элементов  - субъекта, предиката и связки (двух терминов  и  связки).  Состав суждения можно выразить общей формулой «S есть "» или «S не есть P».

Пример 4.3. Определить, что в суждении «Компьютер состоит из процессора, памяти и внешних устройств» является субъектом, предикатом и связкой.

«Компьютер» - субъект, «процессора, памяти и внешних  устройств» - предикат, «состоит» - связка.

Предикат. В современной логике предикат рассматривается как функциональная зависимость. В общем случае предикат от n переменных (от n неопределенных понятий) выражается формулой:

                Р (х1,х2,...,хn ), где n S 0

При n = 1, когда один из терминов является неопределенным понятием, мы имеем  предикат первого порядка, например, «х – человек».

При n = 2, когда два термина неопределены, мы имеем предикат второго порядка, например, «х любит y».

При n = 3, когда неопределенны три термина, мы имеем предикат третьего порядка, например,   «z - сын x и y».

Пример 4.4. В вышеописанных предикатах заменить неопределенные термины на конкретные понятия.

            Преобразуем предикаты в высказывания  путем  подстановки вместо переменных соответствующих понятий: x = «Сократ», y = «Ксантиппа», z = «Софрониск»:

        «Сократ – человек»;

               «Ксантиппа любит Сократа»

               «Софрониск - сын Сократа и Ксантиппы».

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

Умозаключения  бывают дедуктивные, индуктивные и по аналогии.      В дедуктивных умозаключениях рассуждения ведутся от общего к частному. Например, из двух суждений: «Все металлы  электропроводны» и «Ртуть является металлом» путем умозаключения можно сделать вывод, что: «Ртуть электропроводна».

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

         Умозаключение по аналогии представляет собой движение мысли от общности одних свойств и отношений у сравниваемых  предметов или процессов к общности других свойств и отношений. Например, химический состав Солнца и Земли сходен по  многим  показателям, поэтому, когда на Солнце обнаружили неизвестный еще на Земле химический элемент гелий, то по аналогии заключили: такой  элемент есть и на Земле.

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

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

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

Простые высказывания  в алгебре логики обозначаются  заглавными  латинскими буквами:

А = {Аристотель - основоположник логики}

В = {На яблонях растут бананы}.

Истинному высказыванию ставится в соответствие 1, ложному — 0. Таким образом, А = 1, В = 0.

Составные высказывания на естественном языке образуются с помощью союзов, которые в алгебре высказываний заменяются на логические операции. Логические операции задаются таблицами истинности и могут быть графически проиллюстрированы с помощью диаграмм Эйлера-Венна.  

Логическая операция КОНЪЮНКЦИЯ (логическое умножение):

  в естественном языке соответствует союзу и;

  в алгебре высказываний обозначение &;

  в языках программирования обозначение And.

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

В алгебре множеств конъюнкции соответствует операция пересечения множеств, т.е. множеству получившемуся в результате умножения множеств А и В соответствует множество, состоящее из элементов, принадлежащих одновременно двум множествам.

Логическая операция ДИЗЪЮНКЦИЯ (логическое сложение):

 в естественном языке соответствует союзу или; 

  обозначение  ;

  в языках программирования обозначение Or.

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

В алгебре множеств дизъюнкции соответствует операция объединения множеств, т.е. множеству получившемуся в результате сложения множеств А и В соответствует множество, состоящее из элементов, принадлежащих либо множеству А, либо множеству В.

Логическая операция ИНВЕРСИЯ (отрицание):

  в естественном языке соответствует словам неверно, что... и частице не;

  обозначение ; 

  в языках программирования обозначение Not;

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

В алгебре множеств логическому отрицанию соответствует операция дополнения до универсального множества, т.е. множеству получившемуся в результате отрицания множества А соответствует множество , дополняющее его до универсального множества.

Логическая операция ИМПЛИКАЦИЯ (логическое следование):

   в естественном языке соответствует обороту  если ..., то ...;

     обозначение   . 

Импликация - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.

Логическая операция ЭКВИВАЛЕНЦИЯ (равнозначность): 

    в естественном языке соответствует оборотам речи тогда и только тогда; в том и только в том случае;

     обозначения   , ~ .

Эквиваленция – это логическая операция,  ставящая  в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны. Таблица истинности эквиваленции:

Логические операции имеют следующий приоритет: действия в скобках, инверсия, &,  

Пример 4.5. Определите истинность составного высказывания: ( & )  (C D), состоящего из простых высказываний:

А = {Принтер – устройство вывода информации},

В = {Процессор – устройство хранения информации},

С = {Монитор – устройство вывода информации},

D = {Клавиатура – устройство обработки информации}.

Сначала на основании знания устройства компьютера устанавливаем истинность простых высказываний:   А = 1, В = 0, С = 1, D = 0.

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

( & ) (1 0) = (0&1)  (1 0) = 0 Составное высказывание ложно.

Пример 4.6. Какие из высказываний А, В, С должны быть истинны и какие ложны, чтобы было ложно логическое выражение  ((A В) & В  С.

      Импликация ложна на единственном наборе логических значений (1, 0).  Значит, ((A В)&В) = 1, С = 0.

      Конъюнкция истинна на единственном наборе логических значений (1, 1).  Значит, (A  В) = 1 и В = 1.

     Дизъюнкции истинна при наборах логических значений  (0,  1) и (1, 1).

     Следовательно, существуют два набора логических значений, удовлетворяющих условию задачи:  (А = 0, В = 1, С = 0) и (А = 1, В = 1, С = 0).  

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

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

Алгоритм построения  таблицы  истинности:

1)       подсчитать количество переменных n в логическом выражении;

2)       определить число строк в таблице, которое равно m = 2n;

3)       подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно  количеству переменных  плюс  количество операций;

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

5)       заполнить столбцы входных переменных наборами значений;

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

Наборы входных переменных, во избежание ошибок, рекомендуют перечислять следующим образом:

а)       разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю единицами;

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

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

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

Количество логических переменных 3, следовательно, количество строк в таблице истинности должно быть 23 = 8.

Количество логических операций в формуле 5, следовательно количество столбцов в таблице истинности должно быть 3 + 5 = 8.

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

Логической (булевой) функцией называют функцию F(Х1, Х2, ..., Хn), аргументы которой Х1, Х2, ..., Хn (независимые переменные) и сама функция (зависимая переменная) принимают значения 0 или 1.

        Таблицу, показывающую, какие значения принимает логическая функция при всех сочетаниях значений ее аргументов, называют таблицей истинности логической функции. Таблица истинности логической функции n аргументов содержит 2n строк,  n столбцов значений аргументов и 1  столбец значений функции.

        Логические функции могут быть заданы табличным способом или аналитически — в виде соответствующих формул.

        Если логическая функция представлена с помощью дизъюнкций, конъюнкций и инверсий, то такая форма представления называется нормальной.

        Существует 16 различных логических функций от двух переменных.

Таблица Логические функции двух переменных

        Пример 4.8. По имеющимся таблицам истинности выразите через базовые логические функции (конъюнкцию, дизъюнкцию и отрицание) следующие функции:

а) F9(X, Y)

б) F15(X, Y)

        Из таблицы истинности видно, что F9(X, Y) =  (отрицание дизъюнкции).

        Из таблицы истинности видно, что F15(X, Y) =  (отрицание конъюнкции).

Логические законы и правила преобразования логических выражений.

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

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

1. Закон двойного отрицания:

А = .

        Двойное отрицание исключает отрицание.

2. Переместительный (коммутативный) закон:

        — для логического сложения:

А  B = B  A;

        — для логического умножения:

A&B = B&A.

        Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

        В обычной алгебре a + b = b + a,         a b = b  a.

3. Сочетательный (ассоциативный)  закон:

        — для логического сложения:

(A  B)  C = A (B  C);

        — для логического умножения:

(A&B)&C = A&(B&C).

        При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

        В обычной алгебре:

(a + b) + c = a + (b + c) = a + b + c,

а  (bc) = a (b  c) = a  b c.

4. Распределительный (дистрибутивный) закон:

        — для логического сложения:

(A  B)&C  = (A&C)  (B&C);

        — для логического умножения:

(A&B) C = (A  C)&(B  C).

        Определяет правило выноса общего высказывания за скобку.

        В обычной алгебре:

(a + b)  c = a  c + b  c.

5. Закон общей инверсии (законы де Моргана):

        — для логического сложения

 = & ;

        — для логического умножения:

 = 

6. Закон идемпотентности ( от латинских слов idem — тот же самый и potens —сильный; дословно — равносильный):

        — для логического сложения:

A  A = A;

        — для логического умножения:

A&A = A.

        Закон означает отсутствие показателей степени.

7. Законы исключения констант:

        — для логического сложения:

A 1 = 1,      A  0 = A;

        — для логического умножения:

A&1 = A,     A&0 = 0.

8. Закон противоречия:

A& = 0.

        Невозможно, чтобы противоречащие высказывания были одновременно истинными.

9. Закон исключения третьего:

A  = 1.

        Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано.

10. Закон поглощения:

        — для логического сложения:

A  (A&B) = A;

        — для логического умножения:

A&(A  B) = A.

11. Закон исключения (склеивания):

        — для логического сложения:

(A&B)  ( &B) = B;

        — для логического умножения:

(A B)&(  B) = B.

12. Закон контрапозиции (правило перевертывания):

(A Û  B) = (BÛ  A).

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

Пример 4.9. Найдите X, если  = В.

Для преобразования левой части равенства последовательно воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:

( & )( &A)

Согласно распределительному закону для логического сложения:

&(  A)

Согласно закону исключения третьего и закона исключения констант:

&1 =

Полученную левую часть приравняем правой:

= В 

        Окончательно получим, что   X =  .

Пример 4.10. Упростите логическое выражение (A  B  C)&

Правильность упрощения проверьте с помощью таблиц истинности для исходного и полученного логического выражения.

Согласно закону общей инверсии для логического сложения (первому закону Моргана) и закону двойного отрицания:

(A B C)& = (AB  C)&(  

Согласно распределительному (дистрибутивному) закону для логического сложения:

(A  B C)&( &B& ) = (A& )  (B& )  (C& )  (A&B)  (B&B)  (C&B)  (A& )  (B& ) (C& )

Согласно закона противоречия:

 (A& ) = 0; (C& ) = 0

Согласно закона идемпотентности

(B&B) = B

Подставляем значения и, используя переместительный (коммутативный) закон и группируя слагаемые, получаем:

0 (A&B) ( &B) B  (C&B)  ( &B)  (C& )  (A& )  0

Согласно закона исключения (склеивания)

(A&B)  ( &B) = B 

(C&B)  ( &B) = B 

Подставляем значения и получаем:

0 B B  B  (C& )  (A& )  0

Согласно закона исключения констант для логического сложения и закона идемпотентности:

  0 B  0  B  B = B 

Подставляем значения и получаем:

B  (C& )  (A& )

Согласно распределительному (дистрибутивному) закону для логического умножения:

 (C& )  (A& ) = (C A)&(C  )&( A)&(  )

Согласно закона исключения третьего:

(C  ) = 1

(  A) = 1

Подставляем значения и окончательно получаем:

B& & .

Логические основы компьютера

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

          Ниже приведены условные обозначения (схемы) базовых логических элементов, реализующих логическое умножение (конъюнктор), логическое сложение (дизъюнктор) и отрицание (инвертор).

Рис.. Конъюнктор, дизъюнктор и инвертор

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

 Пример 4.11.   По заданной логической функции F(A, B) = B&  &A построить логическую схему.

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

Пример 4.12. Логическая схема имеет два входа X и Y. Определить логические функции F1(X,Y) и F2(X,Y), которые реализуются на ее двух выходах.  

            Функция F1(X,Y) реализуется на выходе первого конъюнктора, т.е. F1(X,Y) = X&Y.

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

            На другой вход второго конъюнктора подается сигнал XÚY с дизъюнктора, следовательно, функция F2(X,Y) = & (XÚY).

            Рассмотрим схему сложения двух n-разрядных двоичных чисел. При сложении цифр i-го разряда складываются аi  и bi,  а также pi-1 — перенос из i-1разряда. Результатом будет si – сумма и pi — перенос в старший разряд. Таким образом, одноразрядный двоичный сумматор — это устройство с тремя входами и двумя выходами.

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

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

            Самый простой триггер — RS-триггер. Он состоит из двух элементов ИЛИ-НЕ (смотри задание 3.34), входы и выходы которых соединены кольцом: выход первого соединен со входом второго и выход второго – со входом первого. Триггер имеет два входа S (от англ. set – установка) и R (от англ. reset – сброс) и два выхода Q (прямой) и (инверсный).

  Рис.. Логическая схема RS-триггера

Пример 4.14. Построить таблицу истинности для RS-триггера.

            Если на входы поступают сигналы R = 0 и S = 0, то триггер находится в режиме хранения, на выходах Q и   сохраняются установленные ранее значения.

            Если на установочный вход S поступает на короткое время сигнал 1, то  триггер переходит в состояние 1 и после того, как сигнал на входе S станет равен 0, триггер будет сохранять это состояние, т.е. будет хранить 1.

            При подаче 1 на вход R триггер перейдет в состояние 0.

            Подача на оба входа S и R логической единицы может привести к неоднозначному результату, поэтому такая комбинация входных сигналов запрещена.

Приложение 1.

Задачи на расчет количества информации

Карточка №1

1. Сколько памяти необходимо для хранения экрана стандартного VGA (640x480, 256)?

2. Сколько дискет объемом 1.44 Мб необходимо для сохранения информации с винчестера объемом 1 Гб.

3. Перевести 100000000 бит в Гб

4. Какое количество вопросов нужно задать, чтобы наверняка угадать загаданного ученика нашей школы (800 учащихся)

5.Сколько различных цветов может содержать рисунок 10х10 точек точек при размере 200 байт.

Карточка №2

1.Сколько памяти необходимо для хранения рисунка размером 320х200 точек при четырех цветах?

2.Сколько времени  необходимо для передачи 300Кб информации по модему со скоростью 14400 бит/c

3. Перевести 3Мб в биты.

4. Какое количество вопросов нужно задать, чтобы наверняка угадать загаданного ученика вашего класса.

5. Каков размер квадратного черно-белого рисунка, если он занимает 2Кб?

Карточка №3

1.Сколько памяти необходимо для хранения черно-белой фотографии размером 1024х768 точек?

2.Сколько дисков ZIP-Drive объемом  250 Мб необходимо для сохранения информации с винчестера объемом 10 Гб.

3. Перевести 3 Гб в килобайты

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

5. Какова скорость передачи в локальной сети, если 10 Гб передаются за 17 секунд?

Карточка №4

1. Сколько цветов содержит рисунок объемом 64Кб размером 32х32

2. Во сколько раз емкость дискеты 1.44 М больше емкости дискеты старого поколения 360 Кб.

3. Перевести 5000000Кб в одном Гб

4. Какое количество вопросов нужно задать, чтобы наверняка угадать одно число из 1000?

5. Во сколько раз по объему памяти размер полноэкранного изображения в режиме CGA (320x200, 4) меньше полноэкранного изображения в режиме VGA (640х480, 256)

Карточка №5

1.Сколько страниц машинописного текста (60 символов, 40 строк) содержится в текстовом файле объемом 500K

2.Сколько дискет по 1.44M необходимо для сохранения всей информации с винчестера объемом 20М.

3. Перевести 6M в байты

4. Какое количество информации содержится в этом вопросе.

5. Каков объем несжатого немого тридцатисекундного видеофайла 320х200, 256 цветов.

Литература.

Н.Угринович. Информатика и информационные технологии. Учебное пособие для 10-11 классов. М.:Лаборатория базовых знаний АО «московские учебники», 2001 г. и послед.издания.

Информатика. Задачник – практикум в 2т. / Под ред. И.Г.Семакина, Е.К. Хеннера. М.:Бином. Лаборатория Знаний, 2002.

Н.Угринович,  Л.Босова, Н.Михайлова. Практикум по информатике и информационным технологиям. М.:Бином. Лаборатория Знаний, 2002.