И. Г. Семакин

Тею. Шеина

иноорммип

БАЗОВЫЙ УРОВЕНЬ

ЕИ3ДАТЕльство

Б НОМ

И. Г. Семакин, Е. К. Хеннер,

Т. Ю. Шеина иноорммип

БАЗОВЫЙ УРОВЕНЬ

Учебник для 10 класса

4-е издание

Рекомендовано

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

Москва

БИНОМ. Лаборатория знаний

2015

удк 004.9 ББК 32.97 сзо

Семакин И. Г.

СЗО Информатика. Базовый уровень учебник для 10 класса / И. Г, Семакин, Е. К. Хеннер, Т. Ю. Шеина. — 4-е изд. — М. : БИНОМ. Лаборатория знаний, 2015. — 264 с. : ил.

rsBN 978-5-9963-1930-5

Учебник предназначен для изучения курса информатики на базовом уровне в 10 классах общеобразовательных учреждений. Содержание учебника опирается на изученный в основной школе (в 7—9 классах) курс информатики. В учебнике рассматриваются теоретические основы информатики: понятие информации, информационные процессы, измерение информации, кодирование и обработка информации в компьютере. Излагаются принципы структурной методики программирования, язык программирования Паскаль. В состав учебника входит практикум, структура которого соответствует содержанию теоретического раздела учебника.

Учебник входит в учебно-методический комплект, включающий в себя также учебник для 11 класса, методическое пособие для учителя, электронное приложение.

Соответствует Федеральному государственному образовательному стандарту (ФГОС) среднего (полного) общего образования (2012 г.).

удк 004.9 ББК 32.97

Учебное изДание

Семакин Игорь Геннадьевич

Хеннер Евгений Карлович Шеина Татьяна Юрьевна

ИНФОРМАТИКА.

БАЗОВЫЙ УРОВЕНЬ

Учебник для 10 класса

Ведущий редактор О. А. Полежаева. Редактор Е. В. Баклашова Ведущий методист И. Л. Сретенская

Художественное оформление: С. Инфантэ, И. Е. Марев

Художественный редактор Н. А. Новак. Иллюстрации: Я. В. Соловцова

Технический редактор Е. В. Денюкова. Корректор Е. Н. Клитина Компьютерная верстка: С. А. Янковая, В. А. Носенко

Подписано в печать 13.11.14. Формат 70х 100/16.

Усл. печ. л. 21,45. Тираж 25 ООО экз. Заказ № 36960.

Издательство «БИНОМ. Лаборатория знаний»

125167, Москва, проезд Аэропорта, д. З. Телефон: (499) 157-5272 e-mail: binom@Lbz.ru, http://www.Lbz.ru, http://e-umk.Lbz.ru, http://metodist.Lbz.ru

При участии ООО Агентство печати «Столица» www.apstolica.ru; e-mail: apstolica@bk.ru

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

410004, г. Саратов, ул. Чернышевского, 59. www.sarpk.ru

         rsBN 978-5-9963-1930-5                     ф) БИНОМ. Лаборатория знаний, 2015

Оглавление

Введение5

Глава 1. Информация11

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

Предоставление информации, языки, кодирование . . 15 Измерение информации. Алфавитный подход. 21 Измерение информации. Содержательный подход .. 26

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

Глава 2. Информационные процессы .53

S 7. Хранение информации .	. 53
S 8. Передача информации	. 59
S 9. Обработка информации и алгоритмы	. 64
S 10. Автоматическая обработка информации .	. 69
S 11. Информационные процессы в компьютере .	. 74

Глава З. Программирование обработки информации86

S 12. Алгоритмы и величины .. 86

S 13. Структура алгоритмов. 92

S 14. Паскаль— язык структурного программирования . . . . 99 S 15. Элементы языка Паскаль и типы данных. 105 S 16. Операции, функции, выражения110

S 17. Оператор присваивания, ввод и вывод данных .116

S 18. Логические величины, операции, выражения. .123

Программирование ветвлений         S 20.Пример поэтапной разработки программы	. 132
решения задачи	. 136
S 21.Программирование циклов	. 142
S 22.Вложенные и итерационные циклы	. 150
S 23.Вспомогательные алгоритмы и подпрограммы .	. 155
24.Массивы	. 163

S 19.

S 25.Организация ввода и вывода данных

с использованием файлов. 169

S 26.Типовые задачи обработки массивов .. 175

S 27.Символьный тип данных181

S 28.Строки символов185

S 29.Комбинированный тип данных . . . . . . . .190

Практикум197

Практические работы к главе 1 «Информация»197 Практические работы к главе 2 «Информационные процессы ». 215 Практические работы к главе З «Программирование обработки информации »231

Ответы к заданиям практических работ . .263

Введение

Что изучается в курсе информатики для 10—11 классов

Изучение любого школьного предмета можно сравнить со строительством дома. Только этот дом складывается не из кирпичей и бетонных плит, а из знаний и умений. Строительство дома начинается с фундамента. Очень важно, чтобы фундамент был прочным, потому что на него опирается всё остальное сооружение. Фундаментом для курса «Информатика 10—11» являются знания и умения, которые вы получили, изучая курс информатики в основной школе в 7—9 классах. Вам уже не требуется объяснять, что такое компьютер и как он работает; с какой информацией может работать компьютер; что такое программа и программное обеспечение компьютера; что такое информационные технологии. В курсе информатики основной школы вы получили представление о том, в каком виде хранится информация в памяти компьютера, что такое алгоритм, информационная модель. Вы научились обращаться с клавиатурой, мышью, дисками, принтером; работать в среде операционной системы; получили основные навыки работы с текстовыми и графическими редакторами, с базами данных и электронными таблицами. Все эти знания и навыки вам будут необходимы при изучении курса «Информатика 10-11».

Термин «информатика» может употребляться в двух смыслах:

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

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

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

В соответствии с современным пониманием, в информатике можно выделить четыре части:

1)  теоретическая информатика;

2)  средства информатизации;

З) информационные технологии; 4) социальная информатика.

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

Введение

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

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

Предметная область современной информатики очень велика и разнообразна. Как известно, нельзя объять необъятное. И наш курс затронет лишь часть тем и задач информатики. Вопросы,

которые мы с вами будем изучать, относятся к четырем важнейшим понятиям информатики:

1)  информационные процессы;

2)  информационные системы; З) информационные модели;

4) информационные технологии.

Правила техники безопасности и гигиены при работе на персональном компьютере

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

Введение

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

•    вскрывать корпус компьютера, не отключенного от электрической сети;

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

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

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

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

Введение

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

Обсудим некоторые проблемы в этой сфере детальнее.

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

Вредное влияние на зрение, оказываемое монитором, можно уменьшить как за счет высокого качества монитора, так и путем периодического выполнения несложных упражнений для глаз. Монитор должен удовлетворять международным стандартам безопасности, что фиксируется в сопроводительной документации. На него не должны падать блики от источников света; расстояние от экрана монитора до глаз пользователя должно составлять от 50 до 70 см. Не надо стремиться отодвинуть монитор как можно дальше, опасаясь вредных излучений, потому что для глаза важен также угол обзора наиболее характерных объектов. Оптимально размещение монитора на расстоянии примерно полутора размеров диагонали экрана. Важным параметром является частота кадров — она должна быть не менее 85 Гц. Периодически, почувствовав утомление зрения, необходимо сделать перерыв, отвести взгляд от экрана и сфокусировать его на удаленных предметах. Вредное влияние на зрение оказывает и недостаточная освещенность как помещения в целом, так и рабочего места в частности.

э.

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

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

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

В работе с книгой вам помогут навигационные значки:

важное утверждение или определение.

— вопросы и задания к параграфу.

— задания для подготовки к итоговой аттестации.

— практические работы на компьютере.

Введение

— К каждой главе учебника рекомендуется электронный образовательный ресурс (ЭОР) с сайта Федерального центра образовательных ресурсов (ФЦИОР): http://fcior.edu.ru Доступ к ЭОР из каталога ФЦИОР:

http://fcior.edu.ru/catalog/meta/4/mc/disciplineYo 2000/ mi/4.06/p/page.html, где ресурсы размещены в алфавитном порядке, согласно названиям учебных тем.

 Проектное или исследовательское задание.

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

 подготовить набор полезных ссылок с использованием м^теЬ-ресурсов;  подготовить небольшое выступление с использованием презентации (5—7 мин);  оформить доклад и поместить его на сайт школьной конференции;  подтвердить полученные результаты расчетами или графиками (диаграммами);  подготовить видеоролик;  разместить материалы проекта (исследования) в коллекции обучающих модулей по предмету на сайте школы.

Глава 1

Информация

5 1

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

Наверное, самый сложный вопрос в информатике — это «Что такое информация?». На него нет однозначного ответа. Смысл этого понятия зависит от контекста (содержания разговора, текста), в котором оно употребляется.

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

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

«информация» отождествляется с понятием «данные».

В Толковом словаре В. И. Даля нет слова «информация». Термин «информация» начал широко употребляться с середины ХХ века. В наибольшей степени понятие информации обязано своим распространением двум научным направлениям: теории связи и кибернетике. Автор теории связи Клод Шеннон, анализируя технические системы связи: телеграф, телефон, радио, рассматривал их как системы переДачи информации. В таких системах информация передается в виде последовательностей сигналов: электрических или электромагнитных. Развитие теории связи послужило созданию теории информации, решающей проблему измерения информации.

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

Информация

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

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

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

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

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

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

13

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

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

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

Информация

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

Система основных понятий

Философия	Атрибутивная концепция: информация — всеобщее свойство (атрибут) материи
	Функциональная концепция: информация и информационные процессы присущи только живой природе, являются ее функцией
	Антропоцентрическая концепция: информация и информационные процессы присущи только человеку
Теория информации	Результат развития теории связи (К. Шеннон)	Информация содержание, заложенное в знаковые (сигнальные) последовательности
Кибернетика	Исследует информаци- онные процессы в системах управления (Н. Винер)	Информация — содержание сигналов, передаваемых по каналам связи в системах управления
Нейрофизиология	Изучает информационные процессы в механизмах нервной деятельности животного и человека	Информация содержание сигналов электрохимической природы, передающихся по нервным волокнам организма
Генетика	Изучает механизмы наследственности, пользуется понятием «наследственная информация »	Информация — содержание генетического кода — структуры молекул ДНК, входящих в состав клетки живого организма

Вопросы и задания

1. Какие существуют основные философские концепции информации?

2. Какая, с вашей точки зрения, концепция является наиболее верной?

З. Благодаря развитию каких наук понятие информации стало широко употребляемым?

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

5.  Что такое наследственная информация?

6.  К какой философской концепции, на ваш взгляд, ближе употребление понятия информации в генетике?

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

8.  Согласны ли вы, что понятие информации имеет контекстный смысл? Если да, то покажите это на примерах.

52

Представление информации, языки, кодирование

Представление информации, языки, кодирование

Из курса основной школы вам известно:

•   Историческое развитие человека, формирование человеческого общества связано с развитием речи, с появлением и распространением языков. Язык это знаковая система для представления и передачи информации.

•   Люди сохраняют свои знания в записях на различных носителях. Благодаря этому знания передаются не только в пространстве, но и во времени — от поколения к поколению,

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

Письменность и кодирование информации

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

Процесс чтения текста — это обратный по отношению к письму процесс, при котором письменный текст преобразуется в устную речь. Чтение можно назвать декодированием письменного текста. Схематически эти два процесса изображены на рис. 1.1.

Устная речь

Рис. 1.1. Схема передачи информации с помощью письменности

Схема на рис. 1.1 типична для всех процессов, связанных с передачей информации.

Информация

Цели и способы кодирования

Теперь обратим внимание на то, что может существовать много способов кодирования одного и того же текста на одном и том же языке. Например, русский текст мы привыкли записывать с помощью русского алфавита. Но то же самое можно сделать, используя латинский алфавит. Иногда так приходится поступать, отправляя SMS по мобильному телефону, на котором нет русских букв, или электронное письмо на русском языке за границу, если у адресата нет русифицированного программного обеспечения. Например, фразу «Здравствуй, дорогой Саша!» приходится писать так: «Zdravstvui, dorogoi Sasha!».

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

Посмотрите на текст стенограммы на рис. 1.2. Там написано следующее: «Говорить умеют все люди на свете. Даже у самых примитивных племен есть речь. Язык — это нечто всеобщее и самое  человеческое, что есть на свете».

Можно придумать и другие спо- Рис. 1.2. Стенограмма собы кодирования.

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

Представление информации, языки, кодирование

Еще одно важное обстоятельство: выбор способа коДирования информации может быть связан с предполагаемым способом ее обработки. Обсудим это на примере представления чисел — количественной информации. Используя русский алфавит, можно записать число «тридцать пять». Используя же алфавит арабской десятичной системы счисления, пишем: 35. Пусть вам надо произвести вычисления. Скажите, какая запись удобнее для выполнения расчетов: «тридцать пять умножить на сто двадцать семь» или «35 х 127»? Очевидно, что для перемножения многозначных чисел вы будете пользоваться второй записью.

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

Широко используемыми в информатике формальными языками являются языки программирования.

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

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

История технических способов кодирования информации

Информация

С появлением технических средств хранения и передачи информации возникли новые идеи и приемы кодирования. Первым техническим средством передачи информации на расстояние стал телеграф, изобретенный в 1837 году американцем Сэмюэлем Морзе. Телеграфное сообщение — это последовательность электрических сигналов, передаваемая от одного телеграфного аппарата по проводам к другому телеграфному аппарату. Эти технические обстоятельства привели Морзе к идее использования всего двух видов сигналов короткого и длинного для кодирования сообщения, передаваемого

Сэмюэль Финли	по линиям телеграфной связи.
Бриз Морзе	Такой способ кодирования получил на-
(1791-1872), США	звание азбуки Морзе. В ней каждая буква

алфавита кодируется последовательностью коротких сигналов (точек) и длинных сигналов (тире). Буквы отделяются друг от друга паузами — отсутствием сигналов.

В таблице на рис. 1.3 показана азбука Морзе применительно к русскому алфавиту. Специальных знаков препинания в ней нет.

Их обычно записывают словами: «тчк» — точка, «зпт» — запятая

Самым знаменитым телеграфным сообщением является сигнал бедствия «SOS» (Save 0ur Souls — спасите наши души). Вот как он выглядит в коде азбуки Морзе:

Три точки обозначают букву S, три тире — букву О. Две паузы отделяют буквы друг от друга.

	й.———
		ф
		х
з			Я.—

Рис. 1.3. Кодовая таблица азбуки Морзе

Характерной особенностью азбуки Морзе является переменная длина кода разных букв, поэтому код Морзе называют неравномерным кодом. Буквы, которые встречаются в тексте чаще, имеют более короткий код, чем редкие буквы. Например, код буквы «Е» — одна точка, а код буквы «Ъ» состоит из шести знаков. Зачем так сделано? Чтобы сократить длину всего сообщения. Но из-за переменной длины кода букв возникает проблема отделения букв друг от друга в тексте. Поэтому приходится для разделения использовать паузу (пропуск). Следовательно, телеграфный алфавит Морзе является троичным, так как в нем используется три

Представление информации, языки, кодирование

знака: точка, тире, пропуск.

Равномерный телеграфный код был изобретен французом Жаном Морисом Бодо в конце XIX века. В нем использовалось всего два вида сигналов. Неважно, как их назвать: точка и тире, плюс и минус, ноль и единица. Это два отличающихся друг от друга электрических сигнала.

В коде Бодо длина кодов всех символов алфавита одинакова и равна пяти. В таком случае не возникает проблемы отделения

букв друг от друга: каждая пятерка сигна-	Жан Морис Эмиль
лов — это знак текста.	Бодо (1845-1903),

Франция

Информация

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

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

Система основных понятий

Представление информации
Языки представления информации
Естественные: русский, китайский, английский и др.			Формальные: язык математики, нотная грамота, языки программирования и др.
Кодирование
Цели коДирования
Засекречивание информации	Быстрый способ записи	Передача по техническим каналам связи		Выполнение математических вычислений
Шифрование	Стенография	Телеграфный код		Системы счисления
Алгоритмы криптографии	Один знак — слово или сочетание букв	код Морзе: неравномерный, троичный код	Код Бодо: равномерный, двоичный код	Для человека: десятичная с. с.	Для КОМпьютера: двоичная с. с.

Вопросы и задания

1. Чем отличаются естественные языки от формальных?

2. Как вы думаете, латынь — это естественный или формальный язык?

З. С каким формальным языком программирования вы знакомы? Для чего он предназначен?

4.  Что такое кодирование и декодирование?

5.  От чего может зависеть способ кодирования?

6.  В чем преимущество кода Бодо по сравнению с кодом Морзе?

7.  В чем преимущество кода Морзе по сравнению с кодом Бодо?

Измерение информации. Алфавитный подход

Измерение информации. Алфавитный подход

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

Алфавитный подход к измерению информации применяется в цифровых (компьютерных) системах хранения и передачи информации. В этих системах используется двоичный способ кодирования информации. При алфавитном подходе для определения количества информации имеет значение лишь размер (объем) хранимого и передаваемого кода. Алфавитный подход еще называют объемным подходом. Из курса информатики 7—9 классов вы знаете, что если с помощью Ёразрядного двоичного кода можно закодировать алфавит, состоящий из лт символов (где лг — целая степень двойки), то эти величины связаны между собой по формуле: 2i=N.

Число лт называется мощностью алфавита.

Если, например, i = 2, то можно построить 4 двухразрядные комбинации из нулей и единиц, т. е. закодировать 4 символа. При i = З существует 8 трехразрядных комбинаций нулей и единиц (кодируется 8 символов):

i=2:	ОО	01	10	11
i=3:	000	001	010	011	100	101	110	111

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

Поскольку 32 = 2 ⁵ , все символы можно закодировать всевозможными пятиразрядными двоичными кодами от 00000 до

Информация

аппаратах, появившихся еще в XIX веке. Телеграфный аппарат при вводе переводил английский текст в двоичный код, длина которого в 5 раз больше, чем длина исходного текста.

о В двоичном коде каждая двоичная цифра несет одну единицу информации, которая называется 1 бит.

Бит является основной единицей измерения информации.

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

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

Алфавит русского языка включает 33 буквы. Если к нему добавить еще пробел и пять знаков препинания, то получится набор из 39 символов. Для двоичного кодирования символов такого алфавита пятиразрядного кода уже недостаточно. Нужен как минимум 6-разрядный код. Поскольку 2 ⁶ = 64, остается еще резерв для 25 символов (64 — 39 = 25). Его можно использовать для кодирования цифр, всевозможных скобок, знаков математических операций и других символов, встречающихся в русском тексте. Следовательно, информационный вес символа в расширенном русском алфавите будет равен 6 битам. А текст из 1000 символов будет иметь объем 6000 битов.

Итак, если i информационный вес символа алфавита, а К — количество символов в тексте, записанном с помощью этого алфавита, то информационный объем I текста выражается формулой:

I = К х i (битов).

Измерение информации. Алфавитный подход

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

Для определения информационного веса	А. Н. Колмогоров (1903-1987),
символа полезно знать ряд целых степеней двойки. Вот как он выглядит в диапазоне от	Россия

2 ¹ до 2 ¹⁰ :

i	1	2	з	4	5	6	7	8	9	10
	2	4	8	16	32	64	128	256	512	1024

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

Пример. Определим информационный вес символа алфавита, включающего в себя все строчные и прописные русские буквы (66); цифры (10); знаки препинания, скобки, кавычки (10). Всего получается 86 символов.

Поскольку 2⁶ < 86 < 2 ⁷ , информационный вес символов данного алфавита равен 7 битам. Это означает, что все 86 символов можно закодировать семиразрядными двоичными кодами.

Для двоичного представления текстов в компьютере чаще всего применяется восьмиразрядный код. С помощью восьмиразрядного кода можно закодировать алфавит из 256 символов, поскольку 256 = 2 ⁸ . В стандартную кодовую таблицу (например, используемую в ОС Windows таблицу ANSI) помещаются все необходимые символы: английские и русские буквы — прописные и строчные, цифры, знаки препинания, знаки арифметических операций, всевозможные скобки и пр.

Более крупной, чем бит, единицей измерения информации является байт: 1 байт = 8 битов.

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

Информация

Одна страница текста на листе формата А4 кегля 12 с одинарным интервалом между строками в компьютерном представлении будет иметь объем 4000 байтов, так как на ней помещается примерно 4000 знаков.

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

1 Кб (килобайт) = 2 ¹⁰ байтов = 1024 байта;

                                  1 Мб (мегабайт) = 2 ¹⁰ Кб         = 1024 Кб;

1 Гб (гигабайт) = 2 ¹⁰ Мб      = 1024 Мб; 1 Тб (терабайт) = 2 ¹⁰ Гб = 1024 Гб.

Объем той же страницы текста будет равен приблизительно 3,9 Кб. А книга из 500 таких страниц займет в памяти компьютера примерно 1,9 Мб.

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

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

Измерение информации. Алфавитный подход

25

Система основных понятий

Измерение информации. Алфавитный (объемный) подход
Применяется в цифровых системах хранения и передачи информации
Объем информации равен Длине двоичного коДа Основная единица: 1 бит — один разряд двоичного кода
Информационный вес символа (i битов) алфавита мощностью лт определяется из уравнения: 2i = М, где М — ближайшая к лт сверху целая степень двойки			Информационный объем I текста, содержащего К символов: I = К • i битов, где i — информационный вес одного символа
Производные единицы
Байт 1 байт = 8 битов	Килобайт (Кб) 1024 байта	Мегабайт (Мб) 1 мб = 1024 Кб		Гигабайт (Гб) 1024 мб	Терабайт (Тб) 1 Тб = 1024 Мб

Вопросы и задания

1. Есть ли связь между алфавитным подходом к измерению информации и содержанием информации?

2. В чем можно измерить объем письменного или печатного текста? З. Оцените объем одной страницы данного учебника в байтах.

4.     Что такое бит с позиции алфавитного подхода к измерению информации?

5.     Как определяется информационный объем текста по А. Н. Колмогорову?

6.     Какой информационный вес имеет каждая буква русского алфавита?

7.     Какие единицы используются для измерения объема информации на компьютерных носителях?

8.     Сообщение, записанное буквами из 64-символьного алфавита, содержит 100 символов. Какой объем информации оно несет?

9.     Сколько символов содержит сообщение, записанное с помощью 16-символьного алфавита, если его объем составляет 1/16 Мб?

10. Сообщение занимает 2 страницы и содержит 1/16 Кб информации. На каждой странице 256 символов. Какова мощность используемого алфавита?

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

Измерение информации. Содержательный подход

Неопределенность знания и количество информации

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

Информация

Чем больше первоначальная неопределенность знания, тем больше информации несет сообщение, снимающее эту неопреДеленность.

Приведем примеры, иллюстрирующие данное утверждение.

Ситуация 1. В ваш класс назначен новый учитель информатики; на вопрос «Это мужчина или женщина?» вам ответили: « Мужчина».

Ситуация 2. На чемпионате страны по футболу играли команды «Динамо» и «Зенит». Из спортивных новостей по радио вы узнаете, что игра закончилась победой «Зенита».

Ситуация З. На выборах мэра города было представлено четыре кандидата. После подведения итогов голосования вы узнали, что избран Н. Н. Никитин.

Вопрос: в какой из трех ситуаций полученное сообщение несет больше информации?

Неопределенность знания — это количество возможных вариантов ответа на интересовавший вас вопрос. Еще можно сказать: возможных исходов события. Здесь событие — например, выборы мэра; исход — выбор, например, Н. Н. Никитина.

В первой ситуации 2 варианта ответа: мужчина, женщина; во второй ситуации З варианта: выиграл «Зенит», ничья, выиграло «Динамо»; в третьей ситуации — 4 варианта: 4 кандидата на пост мэра.

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

В 40-х годах ХХ века проблема измерения информации была решена американским ученым Клодом Шенноном         основателем теории информации. Согласно Шеннону, информация — это снятая неопределенность знания человека об исходе какого-то события.

В теории информации единица измерения	Клод Элвуд Шеннон
информации определяется следующим образом.	(1916-2001)

27

Измерение информации. Содержательный подход

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

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

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

Рассмотрим еще один пример.

Ученик написал контрольную по информатике и спрашивает учителя о полученной оценке. Оценка может оказаться любой: от 2 до 5. На что учитель отвечает: «Угадай оценку за два вопроса, ответом на которые может быть только ” да“ или ”нет” Подумав, ученик задал первый вопрос: «Оценка выше тройки?». «Да», ответил учитель. Второй вопрос: «Это пятерка?». «Нет», — ответил учитель. Ученик понял, что он получил четверку. Какая бы ни была оценка, таким способом она будет угадана!

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

2	з	4	5
		4	5
		4

Первоначальные варианты:

Варианты, оставшиеся после 1-го вопроса:

(1 бит)

Вариант, оставшийся после 2-го вопроса: (+ 1 бит)

Узнав оценку (одну из четырех возможных), ученик получил 2 бита информации.

Рассмотрим еще один частный пример, а затем выведем общее правило.

Вы едете на электропоезде, в котором 8 вагонов, а на вокзале вас встречает товарищ. Товарищ позвонил вам по мобильному телефону и спросил, в каком вагоне вы едете. Вы предлагаете угадать номер вагона, задав наименьшее количество вопросов, ответами на которые могут быть только слова «да» или «нет».

Немного подумав, товарищ стал спрашивать:

— Номер вагона больше четырех?

Информация

— да.

— Номер вагона больше шести?

— Нет.

— Это шестой вагон?

— Нет.

— Ну теперь все ясно! Ты едешь в пятом вагоне!

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

1 2 3 4 5						7	8
				5		7	8
				5

Первоначальные варианты:

После 1-го вопроса (1 бит):

После 2-го вопроса (+ 1 бит):

После 3-го вопроса (+ 1 бит):

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

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

Заметим, что решение подобных проблем методом половинного деления наиболее рационально. Таким способом всегда можно угадать, например, любой из восьми вариантов за З вопроса. Если бы поиск производился последовательным перебором: «Ты едешь в первом вагоне?» «Нет», «Во втором вагоне?» «Нет» и т. д., то про пятый вагон вы смогли бы узнать после пяти вопросов, а про восьмой — после восьми.

«Главная формула» информатики

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

Тогда полученные нами результаты описываются следующими формулировками:

•    сообщение об одном из двух равновероятных исходов некоторого события несет 1 бит информации;  сообщение об одном из четырех равновероятных исходов некоторого события несет 2 бита информации;

•    сообщение об одном из восьми равновероятных исходов некоторого события несет 3 бита информации.

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

В примере с учителем: л^т = 2, i = 1 бит; в примере с оценками: л^т = 4, i = 2 бита; в примере с вагонами:      8, i = 3 бита.

Нетрудно заметить, что связь между этими величинами выраэкается следующей формулой:

2i=N.

Действительно: 2 ¹ = 2 ; 2² = 4 ; 2 ³ = 8.

С полученной формулой вы уже знакомы из курса информатики для 7 класса и еще не однажды с ней встретитесь. Значение этой формулы столь велико, что мы назвали ее главной формулой информатики. Если величина лт известна, а i неизвестно, то данная формула становится уравнением для определения i. В математике такое уравнение называется показательным уравнением,

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

2ⁱ = 16.

Поскольку 16 = 2⁴ , то i = 4 бита.

Информация

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

2i=N.

Пример. В кинозале 16 рядов, в каждом ряду 32 места. Какое количество информации несет сообщение о том, что вам купили билет на 12-й ряд, 10-е место?

Решение задачи: в кинозале всего 16 • 32 = 512 мест. Сообщение о купленном билете однозначно определяет выбор одного из этих мест. Из уравнения 2 ⁱ = 512 = 2 ⁹ получаем: i = 9 битов.

Но эту же задачу можно решать иначе. Сообщение о номере ряда несет 4 бита информации, так как 2 ⁴ = 16. Сообщение о номере места несет 5 битов информации, так как 2 ⁵ = 32. В целом сообщение про ряд и место несет: 4 + 5 = 9 битов информации.

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

Сделаем одно важное замечание. С формулой 2ⁱ = л^т мы уже встречались, обсуждая алфавитный подход к измерению информации (см. S 3). В этом случае лт рассматривалось как мощность алфавита, а i — как информационный вес каждого символа алфавита. Если допустить, что все символы алфавита появляются в тексте с одинаковой частотой, т. е. равновероятно, то информационный вес символа i тождественен количеству информации в сообщении о появлении любого символа в тексте. При этом л^т неопределенность знания о том, какой именно символ алфавита должен стоять в данной позиции текста. Данный факт демонстрирует связь между алфавитным и содержательным подходами к измерению информации.

Формула Хартли

Измерение информации. Содержательный подход

Если значение лг равно целой степени двойки (4, 8, 16, 32, 64 и т. д.), то показательное уравнение легко решить в уме, поскольку i будет целым числом. А чему равно количество информации в сообщении о результате матча «Динамо»—«Зенит»? В этой ситуации лт = З. Можно догадаться, что решение уравнения

будет дробным числом, лежащим между 1 и 2, поскольку 2 ¹ = 2 З, а 2 ² = 4 > З. А как точнее узнать это число?

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

i = log2 N.

Читается это так: «логарифм от лт по основанию 2». Смысл очень простой: логарифм по основанию 2 от лт — это степень, в которую нужно возвести 2, чтобы получить N. Например, вычисление уже известных вам значений можно представить так:

log22 = 1, log2 4 = 2, 10g28 = З.

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

1		i (битов)
2	з
1		i (битов)
2	з	1 ,584962501

Рис. 1.4. Определение количества информации в электронных таблицах с помощью функции логарифма

В табличном процессоре Microsoft Excel функция логарифма имеет следующий вид: LOG(apryмент; основание). Аргумент — значение лт находится в ячейке А2, а основание логарифма равно 2. В результате получаем с точностью до девяти знаков после запятой:

i = log23 = 1,584962501 (бита).

Формула для измерения количества инфор-

Информация

Ральф Хартли мации: log2N была предложена американским (1888-1970) ученым Ральфом Хартли — одним из основоположников теории информации.

формула Хартли:

i = logaN

Здесь i — количество информации, содержащееся в сообщении об одном из равновероятных исходов события.

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

Измерение информации. Содержательный подход

Система основных понятий

Измерение информации. Содержательный подход
Измеряется количество информации в сообщении об исходе некоторого события
Равновероятные исходы: никакой результат не имеет преимущества перед другими
Неопределенность знания — количество возможных исходов события (вариантов сообщения) — лт	Количество информации в сообщении об одном исходе события — i битов
Частный случай: два равновероятных результата события
	i 1 бит
1 бит — количество информации в сообщении об одном из двух равновероятных результатов некоторого события
Формула Хартли: i = log2 лт

Вопросы и задания

1. Что такое неопределенность знания об исходе некоторого события?

2. Как определяется единица измерения количества информации в рамках содержательного подхода?

З. Придумайте несколько ситуаций, при которых сообщение несет 1 бит информации.

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

5.  Сколько битов информации несет сообщение о том, что из колоды в 32 карты достали «даму пик»?

б. При угадывании методом половинного деления целого числа из диапазона от 1 до был получен 1 байт информации. Чему равно N?

7. Проводятся две лотереи: «4 из 32» и «5 из 64». Сообщение о результатах какой из лотерей несет больше информации?

8. Используя формулу Хартли и электронные таблицы, определите количество информации в сообщениях о равновероятных событиях:

а) на шестигранном игральном кубике выпала цифра 3;

б) в следующем году ремонт в школе начнется в феврале;

в) я приобрел абонемент в бассейн на среду;

г) из 30 учеников класса дежурить в школьной столовой назначили Дениса Скворцова.

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

Представление чисел в компьютере

Главные правила представления данных в компьютере

Информация

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

Рис. 1.5. Образ компьютерной памяти

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

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

Правило ЛЕ 2: представление Данных в компьютере дискретно.

Правило Л) З: множество представимых в памяти компьютера величин ограничено и конечно.

Представление чисел

Сначала поясним на образном примере, что такое дискретНОСТЬ.

Представление чисел в компьютере

35

Дискретное множество состоит из отделенных друг от друга элементов. Например, песок дискретен, поскольку он состоит из отдельных песчинок. А вода или масло непрерывны (в рамках наших ощущений, поскольку отдельные молекулы мы всё равно ощутить не можем). Этот пример нужен нам только для аналогии. Здесь мы не станем углубляться в изучение материального мира, а вернемся к предмету изучения информатики — информации.

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

В математике ряд натуральных чисел бесконечен и не ограничен. С появлением в математике понятия отрицательного числа (Р. Декарт, XVII век в Европе; в Индии значительно раньше) оказалось, что множество целых чисел не ограничено как «справа», так и «слева». Покажем это на числовой оси (рис. 1.6), символы оо обозначают бесконечность.

Рис. 1.6. Математическое множество целых чисел на числовой оси

Из сказанного следует вывод: множество целых чисел в математике Дискретно и не ограничено. Отметим еще один факт: разность соседних чисел натурального ряда (данного и предыдущего) всегда равна единице. Эту величину назовем шагом числовой последовательности.

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

Самое большое по абсолютной величине (модулю) отрицательное число:

Информация

Аналогично дело обстоит и в компьютере.

Целые числа в компьютере

Правило 4: в памяти компьютера числа хранятся в двоичной системе счисления*. С двоичной системой счисления вы знакомы из курса информатики 7—9 классов. Например, если под целое число выделяется ячейка памяти размером в 16 битов, то самое большое целое положительное число будет таким:

В десятичной системе счисления оно равно: 2 ¹⁵ -1 = 32 767.

Конечно, и «внутри калькулятора» числа представляются в двоичном виде. Однако мы в это вдаваться не будем, рассмотрев лишь внешнее представление. Пример с калькулятором нам нужен был только для иллюстрации проблемы ограниченности.

Здесь первый бит играет роль знака числа. Ноль — признак положительного числа. Самое большое по модулю отрицательное число равно —32 768. Напомним (это было в курсе информатики основной школы), как получить его внутреннее представление:

1) перевести число 32 768 в двоичную систему счисления; это легко, поскольку 32 768 2 ¹⁵ :

1000000000000000;

2) инвертировать этот двоичный код, т. е. заменить нули на единицы, а единицы — на нули:

Представление чисел в компьютере

37

З) прибавить единицу к этому двоичному числу (складывать надо по правилам двоичной арифметики), в результате получим:

Единица в первом бите обозначает знак «минус». Не нужно думать, что полученный код — это «минус ноль». Этот код представляет число —32 768. Таковы правила машинного представления целых чисел. Данное представление называется дополнительным кодом.

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

1],

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

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

В десятичной системе это 2 ¹⁶ — 1 65 535, примерно в два раза больше по модулю, чем в представлении со знаком.

Из всего сказанного делаем вывод: целые числа в памяти компьютера это Дискретное, ограниченное и конечное множество.

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

Информация

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

Рис. 1.7. Представление о множестве целых чисел в математике и в информатике

Вещественные числа в компьютере

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

Как мы говорили выше, числа в компьютере (в том числе и вещественные) представлены в двоичной системе счисления. Покажем, что множество вещественных чисел в компьютере дис-

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

Снова для примера возьмем калькулятор с десятиразрядным индикаторным табло. Экспериментально докажем дискретность представления вещественных чисел. Выполним на калькуляторе деление 1 на 3. Из математики вам известно, что 1/3 — это рациональная дробь, представление которой в виде десятичной дроби содержит бесконечное количество цифр: 0,3333333333... (3 в периоде). На табло калькулятора вы увидите:

Первый разряд зарезервирован под знак числа. После запятой сохраняется 8 цифр, а остальные не вмещаются в разрядную сетку (так это обычно называют). Значит, это не точное значение, равное 1/3, а его «урезанное» значение.

Представление чисел в компьютере

Следующее по величине число, которое помещается в разрядную сетку:

Оно бОЛЬШе предыдущего на 0,00000001. Это шаг числовой последовательности. Следовательно, два рассмотренных числа разделены между собой конечным отрезком. Очевидно, что предыдущее число такое:

Оно тоже отделено от своего «соседа справа» по числовой оси шагом 0,00000001. Отсюда делаем вывод: множество вещественных чисел, преДставимых в калькуляторе, Дискретно, поскольку числа отделены друг от друга конечными отрезками.

А теперь выясним вот что: будет ли шаг в последовательности вещественных чисел на калькуляторе постоянной величиной (как у целых чисел)?

Вычислим выражение 100000/3. Получим:

Это число в 100 ООО раз больше предыдущего и, очевидно, тоже приближенное. Легко понять, что следующее вещественное число, которое можно получить на табло калькулятора, будет больше данного на 0,0001. Шаг стал гораздо больше.

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

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

Числовая ось

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

Информация

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

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

Самое большое число у разных калькуляторов может оказаться разным. У самого простого это будет то же число, что мы получали раньше: 999999999. Если прибавить к нему единицу, то калькулятор выдаст сообщение об ошибке. А на другом, более «умном» и дорогом, калькуляторе прибавление единицы приведет к такому результату:

Данную запись на табло надо понимать так: 1 • 10⁹ .

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

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

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

Но и для формата с плавающей запятой тоже есть максимальное число. В нашем «подопытном» калькуляторе это число:

Представление чисел в компьютере

То есть 99999 • 10⁹⁹ . Самое большое по модулю отрицательное значение —99999 • 10⁹⁹ . Данные числа являются целыми, но именно они ограничивают представление любых чисел (целых и вещественных) в калькуляторе.

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

Рассмотрим пример: пусть под всё число в компьютере выделяется 8 байтов — 64 бита, из них под порядок — 2 байта, под мантиссу — 6 байтов. Тогда диапазон вещественных чисел, в переводе в десятичную систему счисления, оказывается следующим:

                                                        324                     ³⁰⁸

- 1,7-10).

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

Информация

Рис. 1.9. Представление о множестве вещественных чисел в математике и в информатике

Система основных понятий

Целые числа		Вещественные числа
В математике: - десятичное представление; - множество: дискретно, бесконечно, не ограничено	В компьютере (информатике): - двоичное представление; - множество: дискретно, конечно, ограничено	В математике: - десятичное представление; - множество: непрерывно, бесконечно, не ограничено	В компьютере (информатике): - двоичное представление; - множество: дискретно, конечно, ограничено
Представление целых чисел в компьютере		Представление вещественных чисел в компьютере
Со знаком (положительные и отрицательные	Без знака (положительные)	МХ2Р М — двоичная мантисса, Р — двоичный целый порядок
Диапазон: 2N-l , 2N-1-1]	Диапазон: [0, 2Nl	Диапазон ограничен максимальными значениями МиР
Формат с фиксированной запятой		Формат с плавающей запятой

Вопросы и задания

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

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

З. Получите внутреннее представление числа 157 в 8-разрядной ячейке памяти в формате со знаком.

4.  Получите внутреннее представление числа —157 в 8-разрядной ячейке памяти в формате со знаком.

5.  Почему множество действительных (вещественных) чисел, представимых в памяти компьютера, дискретно, конечно и ограничено?

6.  На какие две части делится число в формате с плавающей запятой?

56

Представление текста, изображения и звука

Представление текста, изображения и звука в компьютере

В этом параграфе обсудим способы компьютерного кодирования текстовой, графической и звуковой информации. С текстовой и графической информацией конструкторы «научили» работать ЭВМ, начиная с третьего поколения (1970-е годы). А работу со звуком «освоили» лишь машины четвертого поколения, современные персональные компьютеры. С этого момента началось распространение технологии мультимедиа.

Что принципиально нового появлялось в устройстве компьютеров с освоением ими новых видов информации? Главным образом, это периферийные устройства для ввода и вывода текстов, графики, видео, звука. Процессор же и оперативная память по своим функциям изменились мало. Существенно возросло их быстродействие, объем памяти. Но как это было на первых поколениях ЭВМ, так и осталось на современных ПК — основным навыком процессора в обработке данных является умение выполнять вычисления с двоичными числами. Обработка текста, графики и звука представляет собой тоже обработку числовых данных. Если сказать еще точнее, то это обработка целых чисел. По этой причине компьютерные технологии называют цифровыми технологиями.

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

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

Текстовая информация

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

Информация

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

Рис. 1.10. Байтовая организация памяти

Модель представления текста в памяти весьма проста. За каждой буквой алфавита, цифрой, знаком препинания и иным общепринятым при записи текста символом закрепляется определенный двоичный код, длина которого фиксирована. В популярных системах кодировки (Windows-1251, k018 и др.) каждый символ заменяется на 8-разряДное целое положительное Двоичное число; оно хранится в одном байте памяти. Это число является порядковым номером символа в кодовой таблице. Согласно главной формуле информатики, определяем, что размер алфавита, который можно закодировать, равен: 2 ⁸ — 256. Этого количества вполне достаточно для размещения двух алфавитов естественных языков (английского и русского) и всех необходимых дополнительных символов.

Поскольку в мире много языков и много алфавитов, постепенно совершается переход на международную систему кодировки Unicode, в которой используются многобайтовые коды. Например, если код символа занимает 2 байта, то с его помощью можно закодировать 2 ¹⁶ 65 536 различных символов.

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

Представление текста, изображения и звука

45

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

Графическая информация

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

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

Дискретное представление изображения. Изображение на экране монитора дискретно. Оно составляется из отдельных точек, которые называются пикселями (picture elements — элементы рисунка). Это связано с техническими особенностями устройства экрана, независимо от его физической реализации, будь то монитор на электронно-лучевой трубке, жидкокристаллический или плазменный. Эти «точки» столь близки друг другу, что глаз не различает промежутков между ними, поэтому изображение воспринимается как непрерывное, сплошное. Если выводимое из

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

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

Качество изображения зависит не только от размера растра, но и от размера экрана монитора, который обычно характеризуется длиной диагонали. Существует параметр разрешения экрана. Этот параметр измеряется в точках на дюйм (по-английски dots per inch — dpi). У монитора с диагональю 15 дюймов размер изображения на экране составляет примерно 28 х 21 см² . Зная, что в одном дюйме 25,4 мм, можно рассчитать, что при работе монитора в режиме 800 х 600 пикселей разрешение экранного изображения равно 72 dpi.

Информация

При печати на бумаге разрешение должно быть намного выше. Полиграфическая печать полноцветного изображения требует разрешения 200—300 dpi. Стандартный фотоснимок размером 10 х 15 см² должен содержать примерно 1000 х 1500 пикселей.

Дискретное представление цвета. Восстановим ваши знания о кодировании цвета, полученные из курса информатики основной школы. Основное правило звучит так: любой цвет точки на экране компьютера получается путем смешивания трех базовых цветов: красного, зеленого, синего. Этот принцип называется цветовой моделью RGB (Red, Green, Blue).

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

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

Пусть, например, размер кода цвета пикселя равен 8 битам

1 баиту. Между базовыми цветами они могут быть распределены так:

к

к

з

з

2 бита — под красный цвет, З бита — под зеленый и З бита — под синий.

Интенсивность красного цвета может принимать 2 ² 4 значения, интенсивности зеленого и синего цветов — по 2 ³ = 8 значений. Полное число цветов, которые кодируются 8-разрядными кодами, равно: 4 • 8 • 8 = 256 = 28. Снова работает главная формула информатики.

Из описанного правила, в частности, следует:

Красный		Зеленый			Синий

— код черного цвета

— код белого цвета

— код бледно-серого цвета — код ярко-зеленого цвета

— код бледно-зеленого цвета

Представление текста, изображения и звука

Обобщение этих частных примеров приводит к следующему правилу. Если размер кода цвета равен Ь битов, то количество цветов (размер палитры) вычисляется по формуле:

Величину Ь в компьютерной графике называют битовой глубиной цвета.

Еще один пример. Битовая глубина цвета равна 24. Размер палитры будет равен:

к- 2 ²⁴ = 16 777216.

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

Цвет, который мы видим на листе бумаги, — это отражение белого (солнечного) света. Нанесенная на бумагу краска поглощает часть палитры, составляющей белый цвет, а другую часть отраэкает. Таким образом, нужный цвет на бумаге получают путем «вычитания» из белого света «ненужных красок». Поэтому в цветной полиграфии действует не правило сложения цветов (как на экране компьютера), а правило вычитания. Мы не будем углубляться в механизм такого способа цветообразования. Расшифруем лишь аббревиатуру СМУК: Суап — голубой, Magenta пурпурный, Yellow — желтый, black — черный.

Растровая и векторная графика

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

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

Информация

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

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

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

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

Графическая информация сохраняется в файлах на диске. Существуют разнообразные форматы графических файлов. Они делятся на растровые и векторные. Растровые графические файлы (форматы JPEG, ВМР, TIFF и другие) хранят информацию о цвете каждого пикселя изображения на экране. В графических файлах векторного формата (например, WMF, CGM) содержатся описания графических примитивов, составляющих рисунок.

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

Представление текста, изображения и звука

Звуковая информация

Принципы дискретизации звука («оцифровки» звука) отражены на рис. 1.11.

Рис. 1.11. Оцифровка звука

(у — интенсивность (уровень) звукового сигнала, t — время)

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

Промежуток времени между двумя измерениями называется периодом измерений — т с. Обратная величина называется частотой дискретизации — 1/т (герц). Чем выше частота измерений, тем выше качество цифрового звука.

Результаты таких измерений представляются целыми положительными числами с конечным количеством разрядов. Вы уже знаете, что в таком случае получается дискретное конечное множество значений в ограниченном диапазоне. Размер этого диапазона зависит от разрядности ячейки — регистра памяти звуковой карты. Снова работает формула 2ⁱ, где i — разрядность регистра. Число i называют также разрядностью дискретизации. Записанные данные сохраняются в файлах специальных звуковых форматов.

Информация

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

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

Для сохранения звука без потерь используется универсальный звуковой формат файлов WAV. Наиболее известный формат «сжатого» звука (с потерями) — МРЗ. Он обеспечивает сжатие данных в 10 раз и более.

Представление текста, изображения и звука

Система основных понятий

Текст		Графика			Звук
Таблицы кодировки		Дискретность изображения	Дискретность цвета		Дискретные измерения звукового сигнала
8-разрядные	16-разрядная	Растр сетка пикселей	Модели цвета		Частота дискретизации	Разрядность дискретизации
ASCII, ков и др.	Unicode	размер растра, dpi — разрешение	RGB Излучаемый свет	СМУК Отражаемый свет	1 [период (герц)	i — разрядность, ЛТ — количество уровней измерения звука

Вопросы и задания

1.     Когда компьютеры начали работать с текстом, с графикой, со звуком?

2.     Что такое таблица кодировки? Какие существуют таблицы кодировКИ?

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

4.     Что такое модель цвета RGB?

5.     Напишите 8-разрядный код ярко-синего цвета, ярко-желтого (смесь красного с зеленым), бледно-желтого.

6.     Почему в полиграфии не используется модель RGB?

7.     что такое смук?

8.     Какое устройство в компьютере производит оцифровку вводимого звукового сигнала?

9.     Как (качественно) качество цифрового звука зависит от частоты дискретизации и разрядности дискретизации?

10. Чем удобен формат МРЗ?

ЭОР к главе 1 на сайте ФЦИОР (http://fcior.edu.ru)

•    Аппаратное и программное обеспечение для представления звука

Информация

www

•   

Аппаратное и программное обеспечение для представления изображения

•    Единицы измерения информации

•    Представление текста в различных кодировках

•    Числа в памяти ЭВМ. Средства обработки числовой информации

 Числа с фиксированной и плавающей запятой

•    Число и его компьютерный код

Глава 2 Информационные процессы

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

Из курса основной школы вам известно:

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

Рассмотрим способы хранения информации более подробно.

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

Носитель — это материальная среда, используемая для записи и хранения информации.

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

Использование бумажных носителей информации

Носителем, имеющим наиболее массовое употребление, до сих пор остается бумага. Изобретенная во П веке н. э. в Китае бумага служит людям уже 19 столетий.

Для сопоставления объемов информации на разных носителях будем пользоваться единицей байтом, считая, что один знак текста «весит» 1 байт. Нетрудно подсчитать информационный объем книги, содержащей ЗОО страниц с размером текста на странице примерно 2000 символов. Текст такой книги имеет объем примерно 600 ООО байтов, или 586 Кб. Средняя школьная библиотека, фонд которой составляют 5000 томов, имеет информационный объем приблизительно 2861 Мб = 2,8 Гб.

Информационные процессы

Что касается долговечности хранения документов, книг и прочей бумажной продукции, то она очень сильно зависит от качества бумаги, красителей, используемых при записи текста, условий хранения. Интересно, что до середины XIX века (с этого времени для производства бумаги начали использовать древесину) бумага делалась из хлопка и текстильных отходов — тряпья. Чернилами служили натуральные красители. Качество рукописных документов того времени было довольно высоким, и они могли храниться тысячи лет. С переходом на древесную основу, с распространением машинописи и средств копирования, с началом использования синтетических красителей срок хранения печатных документов снизился до 200—300 лет.

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

Использование магнитных носителей информации

В XIX веке была изобретена магнитная запись. Первоначально она использовалась только для сохранения звука. Самым первым носителем магнитной записи была стальная проволока диаметром до 1 мм. В начале ХХ столетия для этих целей использовалась также стальная катаная лента. Тогда же (в 1906 г.) был выдан и первый патент на магнитный диск. Качественные характеристики всех этих носителей были весьма низкими. Достаточно сказать, что для производства 14-часовой магнитной записи устных докладов на Международном конгрессе в Копенгагене в 1908 г. потребовалось 2500 км, или около 100 кг проволоки.

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

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

На ЭВМ первого и второго поколений магнитная лента использовалась как единственный вид сменного носителя для устройств внешней памяти. Любая компьютерная информация на любом носителе хранится в двоичном (цифровом) виде. Поэтому независимо от вида информации: текст это, или изображение, или звук — ее объем можно измерить в битах и байтах. На одну катушку с магнитной лентой, использовавшейся в лентопротяжных устройствах первых ЭВМ, помещалось приблизительно 500 Кб информации.

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

На первых ПК использовались гибкие магнитные диски (флоппи-диски) — сменные носители информации с небольшим объемом памяти — до 2 Мб. Начиная с 1980-х годов, в ПК начали использоваться встроенные в системный блок накопители на

жестких магнитных дисках, или НЖМД (англ. НТ) — Hard Disk Drive). Их еще называют винчестерскими дисками.

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

Информационная емкость современных винчестерских дисков измеряется в терабайтах.

Оптические диски и флеш-память

:

Информационные процессы

Применение оптического, или лазерного, способа записи информации начинается в 1980-х годах. Его появление связано с изобретением квантового генератора — лазера, источника очень тонкого (толщина порядка микрона) луча высокой энергии. Луч способен выжигать на поверхности плавкого материала двоичный код данных с очень высокой плотностью. Считывание происходит в результате отражения от такой «перфорированной» поверхности лазерного луча с меньшей энергией («холодного» луча). Первоначально на ПК вошли в употребление оптические компактдиски — CD, информационная емкость которых составляет от 190 Мб до 700 Мб.

Во второй половине 1990-х годов появились цифровые универсальные видеодиски DVD (Digital Versatile Disk) с большой емкостью, измеряемой в гигабайтах (до 17 Гб). Увеличение их емкости по сравнению с CD связано с использованием лазерного луча меньшего диаметра, а также двухслойной и двусторонней записи. Вспомните пример со школьной библиотекой. Весь ее книжный фонд можно разместить на одном DVD.

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

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

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

57

В качестве внешнего носителя для компьютера широкое распространение получили так называемые флеш-брелоки (их называют в просторечии «флешки»), выпуск которых начался в 2001 году. Большой объем информации, компактность, высокая скорость чтения/записи, удобство в использовании основные достоинства этих устройств. Флеш-брелок подключается к USB-rropTY компьютера и позволяет скачивать данные со скоростью около 10 Мб в секунду.

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

Информационные процессы

Система основных понятий

Носители информации
Нецифровые	Цифровые (компьютерные)
Исторические: камень, дерево, папирус, пергамент , шелк и др. Современные: бумага	Магнитные			Оптические		Флеш-носители
	Ленты	Диски	Карты	СЛ)	DVD	Флеш- карты	Флешбрелоки
	Факторы качества носителей
	Вместимость — плотность хранения дан- ных, объем данных			Надежность хранения — максимальное время сохранности данных, зависимость от условий хранения
	Наибольшей вместимостью и надежностью на сегодня обладают оптические носители СГ) и DVD
	Перспективные виды носителей: носители на базе нанотехнологий

Вопросы и задания

1.     Какая, с вашей точки зрения, сохраняемая информация имеет наибольшее значение для всего человечества, для отдельного человека?

2.     Назовите известные вам крупные хранилища информации.

3.     Можно ли человека назвать носителем информации?

4.     Где и когда появилась бумага?

5.     Когда была изобретена магнитная запись? Какими магнитными носителями вы пользуетесь или пользовались?

6.     Какое техническое изобретение позволило создать оптические носители информации? Назовите типы оптических носителей.

7.     Назовите сравнительные преимущества и недостатки магнитных и оптических носителей.

8.     Что означает свойство носителя «только для чтения»?

9.     Какими устройствами, в которых используются флеш-карты, вы пользуетесь? Какой у них информационный объем?

10.Какие перспективы, с точки зрения хранения информации, открывают нанотехнологии?

Передача информации

Из курса основной школы вам известно:

     Распространение информации происходит в процессе ее передачи.

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

В этом параграфе более подробно будут рассмотрены технические системы передачи информации.

Передача информации

В S 2 уже говорилось о том, что первой в истории технической системой передачи информации стал телеграф. В 1876 году американец Александр Белл изобрел телефон. На основании открытия немецким физиком Генрихом Герцем электромагнитных волн (1886 год), А. С. Попов в России в 1895 году и почти одновременно с ним в 1896 году Г. Маркони в Италии изобрели радио. Телевидение и Интернет появились в ХХ веке.

Модель передачи информации К. Шеннона

Все перечисленные способы информационной связи основаны на передаче на расстояние физического (электрического или электромагнитного) сигнала и подчиняются некоторым общим законам. Исследованием этих законов занимается теория связи, возникшая в 1920-х годах. Математический аппарат теории связи — математическую теорию связи разработал американский ученый Клод Шеннон.

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

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

Рис. 2.1. Модель передачи информации по техническим каналам связи

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

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

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

Информационные процессы

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

Пропускная способность канала и скорость передачи информации

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

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

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

•    телефонные линии;

•    электрическая кабельная связь;

•    оптоволоконная кабельная связь;  радиосвязь.

Пропускная способность телефонных линий — десятки и сотни Кбит/с; пропускная способность оптоволоконных линий и линий радиосвязи измеряется десятками и сотнями Мбит/с.

Передача информации

Скорость передачи информации связана не только с пропускной способностью канала связи. Представьте себе, что текст на русском языке, содержащий 1000 знаков, передается с использованием двоичного кодирования. В первом случае используется телеграфная 5-разрядная кодировка. Во втором случае компьютерная 8-разрядная кодировка. Тогда длина кода сообщения в первом случае составит 5000 битов, во втором случае — 8000 битов. При передаче по одному и тому же каналу второе сообщение будет передаваться дольше в 1,6 раза (8000/5000). Отсюда, казалось бы, следует вывод: длину кода сообщения нужно делать минимально возможной.

Однако существует другая проблема, которая на рис. 2.1 отмечена словом «шум».

Шум, защита от шума

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

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

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

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

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

Информационные процессы

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

Большой вклад в научную теорию связи внес известный советский ученый Владимир Александрович Котельников. В 1940— 1950-х

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

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

Владимир	рая передается вместе с данным блоком.
Александрович	В месте приема заново вычисляется конт-
Котельников	рольная сумма принятого блока и, если она
(1908-2005), Россия	не совпадает с первоначальной суммой, пере-

дача данного блока повторяется. Так проис-

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

Передача информации

Система основных понятий

Передача информации в технических системах связи
Модель К. Шеннона
Процедура кодирования	Процесс передачи по каналу связи		Процедура декодирования
	Пропускная способность канала	Воздействие шумов на канал связи
Защита информации от потерь при воздействии шума
Кодирование с оптимальноизбыточным кодом	Частичная потеря избыточной информации при передаче		Полное восстановление исходного сообщения

Вопросы и задания

1. Для чего нужна процедура кодирования передаваемой информации?

2. Что такое декодирование? Каким должен быть его результат?

З. Каким техническим средством связи вы чаще всего пользуетесь? Замечали ли вы при этом факты потери информации?

4.  Назовите устройства кодирования и декодирования при использовании радиосвязи.

5.  Что такое шум по отношению к системам передачи данных?

б. Какие существуют способы борьбы с шумом?

7.  Пропускная способность канала связи 100 Мбит/с. Уровень шума пренебрежимо мал (например, оптоволоконная линия). Определите, за какое время по каналу будет передан текст, информационный объем которого составляет 100 Кб.

8.  Пропускная способность канала связи 10 Мбит/с. Канал подвержен воздействию шума, поэтому избыточность кода передачи составляет 20 ⁰/0. Определите, за сколько времени по каналу будет передан текст, информационный объем которого составляет 100 Кб.

59

Обработка информации и алгоритмы

Из курса основной школы вам известно:

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

Варианты обработки информации

Информационные процессы

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

Можно привести множество примеров, иллюстрирующих схему на рис. 2.2.

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

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

Третий пример: работник библиотеки составляет картотеку книжного фонда. На каждую книгу заполняется карточка, на которой указываются все параметры книги: автор, название, год издания, объем и пр. Из карточек формируется каталог библиотеки, где эти карточки располагаются в строгом порядке. Например, в алфавитном каталоге карточки располагаются в алфавитном порядке фамилий авторов.

Обработка информации и алгоритмы

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

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

1)  получение новой информации, новых сведений;

2)  изменение формы представления информации; 3) систематизация, структурирование данных; 4) поиск информации.

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

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

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

Об алгоритмах

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

Информационные процессы

Из курса информатики основной школы вы знаете, что слово «алгоритм» произошло от имени выдающегося математика средневекового Востока Мухаммеда аль-Хорезми, описавшего еще в IX веке правила выполнения вычислений с многозначными десятичными числами. Правила сложения, вычитания, умножения столбиком, деления «уголком», которым Аль-Хорезми вас учили в младших классах, — это алгоритмы (780-850 гг. н. э.) аль-Хорезми.

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

1. Если числа не равны, то большее из них заменить на разность большего и меньшего из чисел.

2. Если два числа равны, то за НОД принять любое из них, иначе перейти к выполнению пункта 1.

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

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

Алгоритмические машины и свойства алгоритмов

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

Английский ученый Алан Тьюринг предложил модель такого исполнителя, получившую название «машина Тьюринга». По замыслу Тьюринга, его «машина» является универсальным исполнителем обработки любых символьных последовательностей в любом алфавите. Практически одновременно с Тьюрингом (1936—1937 гг.) другую модель алгоритмической машины описал Эмиль Пост. Машина Поста работает с двоичным алфавитом и не-

сколько проще в своем «устройстве». Можно	Алан Тьюринг
сказать, что машина Поста является частным	(1912-1954),
случаем машины Тьюринга. Однако именно	Англия

Обработка информации и алгоритмы

67

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

На основании моделей Тьюринга, Поста и некоторых других ученые пришли к выводу о существовании алгоритмически неразрешимых задач.

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

Совокупность всех команД языка исполнителя называется системой команД исполнителя алгоритмов — СКИ.

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

Алгоритм управления такой машиной должен обладать следующими свойствами;

•    дискретностью (каждый шаг алгоритма выполняется отдельно от других);

•    понятностью (в алгоритме используются только команды из ски);

•    точностью (каждая команда определяет однозначное действие исполнителя);

•    конечностью (за конечное число шагов алгоритма получается искомый результат).

Информационные процессы

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

Система основных понятий

Виды обработки информации
Получение новой информации (новых данных)	Изменение формы представления информации	Структурирование данных	Поиск данных
Исполнитель обработки
Человек		Автомат (машина)
Алгоритм обработки — формализованные правила, определяющие последовательность шагов обработки информации
Алгоритмическая машина автоматический исполнитель обработки знаковых последовательностей
Модели алгоритмических машин в теории алгоритмов
Машина Тьюринга		Машина Поста
Свойства алгоритма
Дискретность: каждый шаг алгоритма выполняется отдельно от других	Понятность: в алгоритме используются только команды из СКИ	Точность: каждая команда определяет однозначное действие исполнителя	Конечность: за конечное число шагов алгоритма получается искомый результат

Вопросы и задания

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

2.  Если вы решаете задачу по математике или физике и при этом используете калькулятор, то какова ваша функция в этом процессе и какова функция калькулятора?

3.  Используя алгоритм Евклида, найдите НОД для чисел 114 и 66. Сколько шагов алгоритма при этом вам пришлось выполнить?

4.  Какие проблемы решает теория алгоритмов?

5.  Почему калькулятор нельзя назвать алгоритмической машиной, а компьютер можно?

6.  Придумайте минимально необходимую систему команд для кассового аппарата, который подсчитывает стоимость покупок и сумму сдачи покупателю. Опишите алгоритм управления работой такого авто-

мата.

Автоматическая обработка информации

510

69

5 10

Автоматическая обработка информации

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

Договоримся о терминологии: под словом «программа» мы всегда будем понимать алгоритм, записанный по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя.

Опишем архитектуру машины Поста

(рис, 2.3). Имеется бесконечная информаци-	Эмиль Пост
онная лента, разделенная на позиции	(1897-1954),
клетки. В каждой клетке может либо стоять	США

метка (некоторый знак), либо отсутствовать (пусто).

Рис. 2.3. Модель машины Поста

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

Каретка является еще и процессором машины. С ее помощью машина может:

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

Информационные процессы

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

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

Теперь рассмотрим систему команд машины Поста (табл. 2.1). Запись всякой команды начинается с ее порядкового номера в программе — п. Затем следует код операции и после него — номер следующей выполняемой команды программы — т.

Рассмотрим пример программы решения задачи на машине Поста. Исходное состояние показано на рис. 2.3. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. Программа приведена в табл. 2.2.

Таблица 2.1. Система команд машины Поста

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

Автоматическая обработка информации

5 10

Таблица 2.2. Программа для машины Поста

Команда	Действие
1	Стирание метки; переход к следующей команде
2	Сдвиг вправо на один шаг
3 ? 2 4	Если клетка пустая, то переход к команде 2, иначе к команде 4
4	Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы)
5 v 6	Запись метки в пустую клетку
	Остановка машины

В процессе выполнения приведенной программы многократно повторяется выполнение команд с номерами 2 и З. Такая ситуация называется циклом. Напомним, что цикл относится к числу основных алгоритмических структур вместе со следованием и ветвлением.

А теперь научим машину Поста играть в интеллектуальную игру, которая называется «Игра Баше»: Опишем правила игры.

Играют двое. Перед ними 21 (или 16, или 11 и т. д.) фишка. Игроки берут фишки по очереди. За один ход можно взять от 1 до 4 фишек. Проигрывает тот, кто забирает последнюю фишку.

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

Информационные процессы

Роль фишек на информационной ленте машины Поста будут выполнять метки (знаки). Машина играет с человеком. Человеку предоставляется возможность стирать метки (брать фишки) первым. Машина будет вступать в игру второй. Исходная обстановка: на ленте массив из 21 клетки содержит метки. Каретка установлена на крайней слева клетке этого массива. Стирать метки можно только подряд. Выигрышным результатом должна быть одна оставшаяся метка перед очередным ходом человека.

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

Программа управления машиной Поста в игре Баше против человека приведена в табл. 2.3.

Таблица 2.3. Программа игры Баше

Команда		Действие
1 ? 2,1		Машина ждет появления пустой клетки над кареткой. После очередного хода человека машина делает свой ход. Если человек видит всего одну метку на ленте, он прекращает игру, признав свое поражение
		Эта серия команд выведет каретку на пятую (десятую, пятнадцатую и т. д.) позицию. Какой бы ход ни сделал соперник, в ней обязательно будет стоять метка
4
5
6	7	Стирается метка в текущей клетке
		Шаг влево
8 ? 96		Если клетка не пустая, то возврат к команде б
9		Каретка перемещается к первой помеченной клетке. После этого машина возвращается к команде 1 и ждет хода человека (или признания им своего поражения)
10 ? 9,1

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

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

1) информация представлена в формализованном виде в конечном алфавите некоторой знаковой системы;

Автоматическая обработка информации

5 10

2)

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

З) реализовано программное управление работой исполнителя.

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

Система основных понятий

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

Вопросы и задания

1. На информационной ленте машины Поста расположен массив из меток. Каретка находится под крайней левой меткой. Какое состояние установится на ленте после выполнения следующей программы?

2 1 3

4 ? 5,2

7 !

2. На информационной ленте на некотором расстоянии справа от каретки, стоящей под пустой клеткой, находится непрерывный массив меток. Требуется присоединить к правому концу массива одну метку.

З. На ленте расположен массив из 2n — 1 меток. Составить программу отыскания средней метки и стирания ее.

Информационные процессы

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

5 1 1

Информационные процессы в компьютере

Из курса основной школы вам известно:

      Компьютер (ЭВМ) — автоматическое, программно-управляемое устройство для работы с информацией.

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

      В 1946 году Джоном фон Нейманом были сформулированы основные принципы устройства ЭВМ, которые называют фон-неймановской архитектурой.

      Современный компьютер представляет собой единство аппаратуры (hardware) и программного обеспечения (software).

Серийное производство электронных вычислительных машин (ЭВМ) начинается в разных странах в 1950-х годах. Историю развития ЭВМ принято делить на поколения. Переход от одного поколения к другому связан со сменой элементной базы, на которой создавались машины, с изменением архитектуры ЭВМ, с развити-

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

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

В основе архитектуры ЭВМ разных поколений лежат принципы Джона фон Неймана. Однако в процессе развития происходят некоторые отклонения от фон-неймановской архитектуры.

Однопроцессорная архитектура ЭВМ

Информационные процессы в компьютере

Элементной базой ЭВМ первого поколения (1950-е годы) были электронные лампы, а ЭВМ второго поколения (1960-е годы) создавались на базе полупроводниковых элементов. Однако их архитектура была схожей. Она в наибольшей степени соответствовала принципам фон Неймана. В этих машинах один процессор управлял работой всех устройств: внутренней и внешней памяти, устройств ввода и вывода, как показано на рис. 2.4.

Рис. 2.4. Структура однопроцессорной ЭВМ. Сплошные стрелки — передача данных, пунктирные стрелки — управляющее воздействие

Согласно принципам фон Неймана, исполняемая программа хранится во внутренней памяти — в оперативном запоминающем устройстве (ОЗУ). Там же находятся данные, с которыми работает программа. Каждая команда программы и каждая величина (элемент данных) занимают определенные ячейки памяти, как пока-

	Внутренняя память
	Номер ячейки	Содержимое ячейки
Программа	1
	2
		Команда УГОР
Данные		Величина 1
		Величина 2

Рис. 2.5. Размещение в ОЗУ программы и данных

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

Информационные процессы

Среди команд программы существуют команды обработки данных и команды обращения к внешним устройствам. Команды обработки данных выполняет сам процессор с помощью входящего в него арифметико-логического устройства — АЛУ, и этот процесс происходит сравнительно быстро. А команды управления внешними устройствами выполняются самими этими устройствами: устройствами ввода/вывода, внешней памятью. Время выполнения этих команд во много раз больше, чем время выполнения команд обработки данных. При однопроцессорной архитектуре ЭВМ, показанной на рис. 2.4, процессор, отдав команду внешнему устройству, ожидает завершения ее выполнения. При большом числе обращений к внешним устройствам может оказаться, что 66.льшую часть времени выполнения программы процессор «простаивает» и, следовательно, его КПД оказывается низким. Быстродействие ЭВМ с такой архитектурой находилось в пределах 10—20 тысяч операций в секунду (оп./с).

Использование периферийных процессоров

Информационные процессы в компьютере

Следующим шагом в развитии архитектуры ЭВМ стал отказ от однопроцессорного устройства. Уже на последних моделях машин второго поколения, помимо центрального процессора (ЦП), выполнявшего обработку данных, присутствовали периферийные процессори, которые назывались каналами ввода/вывода (рис. 2.6). Их задача состояла в автономном управлении устройствами ввода/вывода и внешней памяти, что освобождало от этой работы центральный процессор. В результате КПД центрального процессора существенно возрос. Быстродействие некоторых моделей машин с такой архитектурой составляло от 1 до З млн оп./с.

Рис. 2.6. Структура ЭВМ с одним центральным процессором и периферийными процессорами управления внешними устройствами (треугольники)

На всех моделях ЭВМ третьего поколения, которые создавались на базе интегральных схем (1970—80-е годы), использовалась архитектура с одним центральным процессором и периферийными процессорами внешних устройств. Такая многопроцессорная архитектура позволяла реализовать мультипрограммный режим работы: пока одна программа занята вводом/выводом данных, которым управляет периферийный процессор, другая программа занимает центральный процессор, выполняя вычисления. Благодаря совершенствованию элементной базы и других аппаратных средств на некоторых моделях ЭВМ третьего поколения достигалось быстродействие до 10 млн оп./с.

Для разделения ресурсов ЭВМ между несколькими выполняемыми программами потребовалось создание специального программного обеспечения: операционной системы (ОС). К разделяемым ресурсам, прежде всего, относятся время работы центрального процессора и оперативная память. Задача ОС состоит в том, чтобы разные программы, выполняемые одновременно на ЭВМ, «не мешали» друг другу и чтобы КПД центрального процессора был максимальным, иначе говоря, чтобы ЦП не «простаивал». ОС берет на себя также заботу об очередности использования несколькими программами общих внешних устройств: внешней памяти, устройств ввода/вывода.

Архитектура персонального компьютера

Информационные процессы

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

Рис. 2.7. Архитектура персонального компьютера (сплошные стрелки — направление потоков информации, пунктирные — направление управляющих сигналов, К — контроллер)

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

Системная шина состоит из трех частей:  шина данных (для передачи данных);

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

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

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

Информационные процессы в компьютере

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

Архитектура ненеймановских вычислительных систем

Несмотря на стремительно нарастающую производительность ЭВМ, которая каждые 4—5 лет по важнейшим показателям практически удваивается, всегда есть классы задач, для которых никакой производительности не хватает. Укажем некоторые из них.

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

2. Поиск информации в гигантских базах данных, в информационном пространстве Интернета.

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

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

Чтобы стало понятнее, зачем компьютеру несколько процессоров, обсудим алгоритм решения простейшей математической задачи. Есть массив из 100 чисел: ат, а,2, ... , % 00. Требуется найти их сумму.

Информационные процессы

Нет ничего проще! И на компьютере, и без него мы, скорее всего, поступим так: сложим первые два числа, как-то обозначим их сумму (например, S), затем прибавим к ней третье, и будем делать это еще 98 раз. Это пример последовательного вычислительного процесса. Его блок-схема приведена на рис. 2.8.

Рис. 2.8. Алгоритм решения задачи последовательного сложения массива чисел

Поскольку у человека нет второй головы, иначе эту задачу в одиночку не решить. Но представим, что мы решаем ее не в одиночку, а всем классом (25 человек). Тогда возникает возможность совсем иной последовательности действий.

1. Объединим числа в пары — по два на каждого (итого распределили 50 чисел); например, ученик 1 берет себе 01 и 02 , ученик № 2 аз и а4 , и т. д.

2. Даем команду «складывай!» — и каждый складывает свои числа. З. Даем команду «записывай!» и каждый записывает мелом на классной доске свой результат.

4.  Поскольку у нас осталось еще 50 необработанных чисел (а51, , ато), повторяем пункты 1—3. После этого имеем на доске 50 чисел b1 а1 + а,д, , b50 = 099 + 0100 — результаты парных сложений.

5.  Объединим в пары числа bi и повторим выполнение пунктов

Информационные процессы в компьютере

Продолжаем этот процесс (2—5) до тех пор, пока не останется одно число — искомая сумма.

Первое впечатление, что очень сложно, гораздо сложнее, чем алгоритм на рис. 2.8. Если бы мы захотели записать этот алгоритм в виде блок-схемы, то нам бы пришлось кроме описания порядка и объектов действий сделать то, что мы никогда при записи алгоритмов не делали, предусмотреть синхронизацию параллельных процессов по времени. Например, выполнение команд 2 и З должно завершиться всеми участниками вычислений до того, как они будут продолжены (до перехода к п. 4), иначе даже при решении этой простой задачи наступит хаос.

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

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

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

Вернемся, однако, к описанной выше последовательности действий — в ней еще есть источники проблем. Представим себе, что в схеме на рис. 2.7 мы дорисовали еще 24 центральных процессора, соединенных с шиной. При реализации в таком компьютере команды З произойдет одновременное обращение 25 процессоров к системной шине для пересылки результатов сложения в оперативную память. Но поскольку шина одна, числа по ней могут пересылаться только по одному! Значит, для выполнения команды З придется организовать очередь на передачу чисел в память. Тут же возникает вопрос: не сведет ли к нулю эта очередь все преимущества от параллельности выполнения операций на шаге 2? А если преимущества останутся, то насколько они велики? Окупятся ли расходы на 24 дополнительных процессора?

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

Информационные процессы

Как видите, всё это очень непросто! Обсуждаемые изменения в устройстве компьютера приводят к «ненеймановским» архитектурам. Изобретателям таких систем приходится искать компромисс между возрастающей сложностью (и, как следствие, — стоимостью) и ускорением их работы.

Варианты реализации ненеймановских вычислительных систем

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

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

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

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

Информационные процессы в компьютере

83

Один из самых мощных в мире суперкомпьютеров под названием «Ломоносов» (рис. 2.9) произведен в России и работает в Московском государственном университете. Его быстродействие составляет более ста триллионов операций в секунду.

Рис. 2.9. Суперкомпьютер «Ломоносов» (МГУ им. М. В. Ломоносова)

Информационные процессы

Система основных понятий

Информационные процессы в компьютере
Эволюция поколений ЭВМ
	1 1950-е годы	2 1960-е годы	з 1970-е годы	4 (ПК, суперЭВМ) Начиная с 1970-х
Элементная база	Электронные лампы	Транзисторы	Интегральные схемы (ИС) и большие интегральные схемы (БИС)	БИС, СБИС (сверхбольшие ИС), микропроцессоры
Максимальное быстродействие (оп./с)	10—20 тыс.	100 тыс. — З млн	10 млн	109-1012
	новская однопроцессорная	ская однопроцессорная . Появление периферийных процессоров	процессор + каналы ввода/вывода. Шинная архитектура	векторные, матричные, многопроцессорные, мультикомпьютерные системы
Ненеймановские вычислительные системы Ведущий принцип: отказ от последовательного выполнения операций
Техническое решение		Программное решение
Мультипроцессорные системы — суперкомпьютеры; мультикомпьютерные системы (кластеры)		Параллельное программирование: выделение в программе нескольких одновременно выполняемых действий (распараллеливание)

Вопросы и задания

1. Расскажите о смене элементной базы компьютеров, происходившей при переходе от одного поколения к другому. Как при этом менялись основные характеристики ЭВМ?

2. В чем состоял отход от архитектуры фон Неймана на ЭВМ второго и третьего поколений?

З. Что позволило реализовать мультипрограммный режим работы на ЭВМ третьего поколения?

4.      Чем принципиально отличается архитектура ПК от классической архитектуры компьютеров первых поколений?

5.      Какие функции выполняют контроллеры внешних устройств на ПК?

6.      В чем состоит принцип открытости архитектуры ПК?

7.      Какие функции выполняли первые операционные системы?

8.      Для каких классов задач нужны сверхпроизводительные вычислительные системы?

9.      Что такое параллельные вычисления?

Информационные процессы в компьютере

85

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

11.  Чем отличаются мультикомпьютерные системы от мультипроцессорных? По какому принципу работают суперкомпьютеры?

www

ЭОР к главе 2 на сайте ФЦИОР (http://fcior.edu.ru)

     Архитектура компьютера

     Архитектура машин пятого поколения

     Внутренняя память компьютера. Внешняя память компьютера. Типы накопителей информации

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

     Понятие алгоритма

     Принцип открытой архитектуры

     Принципы и системы передачи информации

     Принципы и системы передачи информации. Вычисление объема информации при передаче. Практическая работа

Глава З

Программирование обработки информации

Основы алгоритмизации и программирования вы изучали в курсе информатики основной школы.

Вы уже знакомы со следующими понятиями:

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

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

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

512

Алгоритмы и величины

Этапы решения задачи на компьютере

Работа по решению любой задачи с использованием компьютера делится на следующие этапы:

1. Постановка задачи.

О 2. Формализация задачи.

3.  Построение алгоритма.

4.  Составление программы на языке программирования.

5.  Отладка и тестирование программы.

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

Часто эту последовательность называют технологической цепочкой решения заДачи на компьютере. Непосредственно к программированию в этом списке относятся пункты З, 4, 5.

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

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

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

Алгоритмы и величины

5 12

87

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

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

 уметь строить алгоритмы;  знать языки программирования;  уметь работать в соответствующей системе программирования.

Основой программистской грамотности является развитое алгоритмическое мышление.

Понятие алгоритма

Одним из фундаментальных понятий в информатике является понятие алгоритма. Сам термин «алгоритм» пришел из математики. Это слово происходит от «Algorithmi» — латинского написания имени Мухамеда аль-Хорезми (787—850 гг.), выдающегося математика средневекового Востока. В XII веке был осуществлен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение «столбиком», деление «уголком» многозначных чисел вот первые алгоритмы в математике. Правила алгебраических преобразований, вычисление корней уравнений также можно отнести к математическим алгоритмам.

В наше время понятие алгоритма трактуется шире. Алгоритм — это послеДовательность команД управления каким-либо исполнителем. В школьном курсе информатики с понятием алгоритма, с методами построения алгоритмов ученики впервые знакомятся на примерах учебных исполнителей: Робота, Черепашки, Чертежника и др. В нашем учебнике для 9 класса описан графический исполнитель — ГРИС. Эти исполнители ничего не вычисляют. Они создают рисунки на экране, перемещаются в лабиринтах, перетаскивают предметы с места на место. Таких исполнителей принято называть исполнителями, работающими в обстановке.

Программирование обработки информации

В разделе информатики под названием «Программирование» изучаются методы программного управления работой компьютера. Следовательно, в качестве исполнителя выступает компьютер. Он работает с величинами — различными информационными объектами: числами, символами, кодами и пр. Поэтому алгоритмы, предназначенные для управления компьютером, принято называть алгоритмами работы с величинами.

Данные и величины

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

Рис. 3.1. Уровни данных относительно программы

Например, при решении квадратного уравнения: ах² + bx + + с О исходными данными являются коэффициенты а, Ь, с; результатами корни уравнения хт, х2; промежуточными данными — дискриминант уравнения: D = b² — 4ас.

Для успешного освоения программирования необходимо усвоить следующее правило: всякая величина занимает свое определенное место в памяти компьютера. Иногда говорят ячейку памяти. Хотя термин «ячейка», с точки зрения архитектуры современных компьютеров, несколько устарел, однако в учебных целях его удобно использовать.

У всякой величины имеются три основных свойства: имя, значение и тип. На уровне команд процессора величина идентифицируется адресом ячейки памяти, в которой она хранится. В алгоритмах и языках программирования величины делятся на константы и переменные. Константа — неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.7, 'k', true. Переменные величины могут изменять свои значения в ходе выполнения программы и представляются символическими именами — идентификаторами, например: Х, S2, cod15. Любая константа или переменная занимают ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.

Алгоритмы и величины

5 12

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

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

Типы констант определяются по контексту (т. е. по форме записи в тексте), а типы переменных устанавливаются в описаниях переменных.

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

Компьютер — исполнитель алгоритмов. Как известно, всякий алгоритм (программа) составляется для конкретного исполнителя, в рамках его системы команд. О каком же исполнителе идет

Программирование обработки информации

Таблица 3.1

	Значения	Операции	Внутреннее едставление
Целый	Целые положительные и отрицательные числа в некотором диапазоне. Примеры: 23, -12, 387	Арифметические операции с целыми числами: +, —, *, целочисленное деление и остаток от деления. Операции отношений >, = и др.)	Формат с фиксированной запятой
Вещественный	Любые (целые и дробные) числа в некотором диапазоне. Примеры: 2.5, -0.01, 45.0, 3.6 109	Арифметические операции: -е, Операции отношений	Формат с плавающей запятой
Логический	true (истина) false (ложь)	Логические операЦИИ: И (and), ИЛИ (от), НЕ (not). Операции отношений	1 бит: 1 — true; О — false
Символь-	Любые символы компьютерного алфавита. Примеры: 'а' ,	Операции отношений	Коды таблицы символьной кодировки. 1 символ — 1 байт

речь в теме «Программирование обработки информации»? Ответ очевиден: исполнителем является компьютер. Точнее говоря, исполнителем является комплекс: компьютер + система программирования (СП). Программист составляет программу на том языке, на который ориентирована СП. Схематически это изображено на рис. 3.2, где ВХОДнЫМ языком исполнителя является язык программирования Паскаль.

Рис. 3.2. Взаимодействие программиста с компьютером

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

•      присваивания;

•      ввода;

•      вывода;

Алгоритмы и величины

5 12

•     

обращения к вспомогательному алгоритму (подпрограмме);  цикла;  ветвления.

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

Система основных понятий

Этапы решения задачи на компьютере 1.   Постановка задачи. 2.   Формализация задачи. З. Построение алгоритма. 4.  Составление программы на языке программирования. 5.  Отладка и тестирование программы. 6.  Проведение расчетов и анализ полученных результатов
Компьютер + система программирования = исполнитель алгоритмов обработки данных
Система команд исполнителя	Классификация данных
- присваивание; - ввод; - вывод; - ветвление; - цикл; - обращение к подпрограмме	По отношению к алгоритму: -  исходные; -  промежуточные ; -  итоговые (результаты)	По значениям: -  константы; -  переменные	По типам: -  целые; -  вещественные; -  логические; -  символьные	По струк- - простые; - структурированные

Вопросы и задания

1.  Перечислите и охарактеризуйте этапы решения задач на компьютере.

2.  Дайте определение алгоритма.

3.  Что такое «система команд исполнителя алгоритмов» (СКИ)?

4.  Какими возможностями обладает компьютер как исполнитель алгоритмов?

5.  Назовите команды, входящие в СКИ компьютера, из которых составляется любая программа обработки данных.

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

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

513

Структура алгоритмов

Базовые алгоритмические структуры

Программирование обработки информации

программированием.	Эдсгер В.
С базовыми алгоритмическими структурами	Дейкстра
вы познакомились, изучая информатику в 9 клас-	(1930-2002)

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

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

Следование это линейная последовательность действий (рис. 3.3).

Рис. 3.3. Структура «следование»

В программе на Паскале серия — это либо один отдельный оператор, либо составной оператор: последовательность операторов, заключенная в операторные скобки. Например, в языке Паскаль операторными скобками являются служебные слова Begin и End.

Ветвление — алгоритмическая альтернатива. Управление передается одному из двух блоков в зависимости от истинности или ложности условия. Затем происходит выход на общее продолжение. Вот как изображается ветвление на блок-схеме и АЯ (рис. 3.4).

если <условие> то «(серия 1> иначе <серия 2> все

Рис. 3.4. Структура «ветвление»

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

Неполная форма ветвления имеет место, когда на ветви «нет» пусто (рис. 3.5).

93

если <условие> то <серия> все

Рис. 3.5. Неполное ветвление

Цикл — повторение некоторой группы действий по условию. Различают два типа цикла. Первый — цикл с предусловием: цикл-пока (рис. 3.6).

если <условие>

<серия> все

Рис. 3.6. Структура «цикл-пока»

Пока условие истинно, выполняется серия, образующая тело цикла.

Второй тип циклической структуры — цикл с постусловием: цикл-до (рис. 3.7).

повторить

<серия> до «(условие

Рис. 3.7. Структура «ЦИКЛ-до»

Здесь тело цикла предшествует условию цикла. Тело цикла повторяет свое выполнение, если условие ложно. Повторение прекращается, когда условие становится истинным.

Программирование обработки информации

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

Иногда в литературе структурное программирование называют программированием без СОТО — оператора безусловного перехода. Действительно, при таком подходе нет места безусловному переходу. Неоправданное использование в программе оператора (ЮТО лишает ее структурности, а значит, всех связанных с этим положительных свойств: прозрачности и надежности алгоритма. Хотя во всех процедурных языках программирования этот оператор присутствует, однако, с точки зрения структурного подхода, его употребления следует избегать.

Комбинации базовых структур

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

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

Структурный подход требует соблюдения стандарта в изображении блок-схем алгоритмов. Чертить их нужно так, как это делалось во всех приведенных примерах. Каждая базовая структура должна иметь один вход и один выход. Нестандартно изображенная блок-схема плохо читается, теряется наглядность алгоритма. Несколько примеров структурных блок-схем алгоритмов приведены на рис. 3.8 (вместо «да», «нет» здесь использованы знаки «+» и «—», У — <условие>, С — <серия>).

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

1. Вложенные ветвления. Глубина вложенности равна единице.

Структура алгоритмов

S 13

2.

Цикл с вложенным ветвлением.

З. Вложенные циклы-пока. Глубина вложенности — 1.

4. Ветвление с вложенной последовательностью ветвлений на положительной ветви и с вложенным циклом-пока на отрицательной ветви.

5. Следование ветвления и цикла-до.

6. Вложенные циклы. Внешний  цикл-пока, внутренний цикл-до.

Наглядность структуре описания алгоритма на АЯ придает структуризация внешнего виДа текста. Основной используемый для этого прием — сдвиги строк, которые должны подчиняться следующим правилам:

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

•    вложенная конструкция записывается смещенной по строке на несколько позиций вправо относительно внешней для нее конструкции.

Программирование обработки информации

Рис. 3.8. Структурные схемы алгоритмов

Для приведенных на рис. АЯ должна быть следующей:

1. если <У1> то если <УЗ> то <С1> все иначе если <У2> то иначе <СЗ>

все

з.

пока <У1> пока <У2>

5.

если <У1> то <С1> иначе <С2> все повторять

до

3.8 блок-схем структура текста на

Структура алгоритмов

5 13

97

2. пока <У1> нц если <У2> то <С1> иначе <С2>

4. если <У1> то если <У2> то <С1> иначе <С2> все если <УЗ> то <СЗ> иначе <С4> все иначе пока <У4>

кц все

6.

пока <У1> нц повторять

до кц

Такой же способ структуризации используется и в текстах программ (например, на Паскале).

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

Программирование обработки информации

Система основных понятий

Структуры алгоритмов и программ
Базовые алгоритмические структуры
Следование	Ветвление
Линейная последовательность действий	Выбор одной из двух се- рий действий с выходом на общее продолжение	Повторение серии действий по условию. Цикл с предусловием, цикл с постусловием
Комбинации базовых структур: последовательность, вложенность
Структурный алгоритм (программа): построенный из базовых алгоритмических структур, не содержащий команды безусловного перехода (GOT0)
Структурирование текста на Алгоритмическом языке и на языках программирования: использование сдвигов строк для вложенных конструкций

Вопросы и задания

О 1. Перечислите основные базовые алгоритмические структуры и покажите способы их отображения на блок-схемах и в АЖ О 2. Какой алгоритм называется структурным?

З. Нарисуйте блок-схемы и напишите на АЯ два варианта алгоритма решения задачи: выбрать из двух числовых величин наибольшее значение. Первый вариант с полным ветвлением, второй вариант — с неполным ветвлением.

4.  Нарисуйте блок-схемы и напишите на АЯ два варианта алгоритма решения задачи: выбрать из трех числовых величин наименьшее значение. Первый вариант с вложенными ветвлениями, второй вариант — с последовательными ветвлениями.

5.  Для данного натурального числа л^т требуется вычислить сумму: 1 + 1/2 + 1/3 + ... + 1/N. Постройте блок-схемы и напишите на АЯ два варианта алгоритма: с циклом-до и с циклом-пока.

6.  Какую структуру будет иметь алгоритм решения следующей задачи? Дано целое положительное число N. Если ЛУ — четное, то вычислить М— 1 - 2 . • N. Если лг нечетное, то вычислить сумму:

Составьте блок-схему алгоритма решения и опишите его на АЖ

S 14

Паскаль — язык структурного программирования

Программирование для ЭВМ — процесс создания программ управления работой компьютера.

Эволюция программирования

Паскаль — язык структурного программирования

S 14

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

	Адрес команды	Код операции	1-й адрес	2-й адрес	3-й адрес
Шестнадцатеричный код	28	02	со
Двоичный код	0010 1000	0000 0010	1100 0000	1100 0100	1101 1000

Такая команда называется трехадресной. Код 0216 относится к команде сложения. 1-й и 2-й адреса — это адреса ячеек ОЗУ, в которых хранятся слагаемые, 3-й адрес — адрес ячейки, куда заносится сумма. Сама команда хранится в ячейке ОЗУ с адресом 2816.

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

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

ADD а, Ь, с

Программирование обработки информации

Слово АШ) обозначает команду «сложить», а и Ь — имена переменных-слагаемых, с — переменная, куда помещается результат.

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

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

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

Языки программирования высокого уровня. Следующим этапом развития программирования стало создание языков программирования высокого уровня — ЯПВУ. Примеры ЯПВУ: Паскаль, Бейсик, Фортран, Си, Java и др. Все названные ЯПВУ относятся к так называемой процедурной парадигме программирования. Поэтому их называют процеДурнылш языками программирования. Программы на таких языках представляют собой последовательности команд, описывающих действия (процедуры) компьютера по обработке информации. Существуют другие парадигмы программирования. Относящиеся к ним языки называют Декларативными языками программирования (Пролог, Лисп и др.). Однако мы их рассматривать не будем.

Для каждого языка существует машинно-независимый стандарт- Возможность программирования на данном ЯПВУ зависит от наличия на вашем компьютере транслятора с этого языка. Трансляторы для каждого типа компьютера создают системные программисты.

Паскаль — язык структурного программирования

S 14

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

с : =a+b (на Паскале); с=а+Ь (на Фортране, Бейсике, Си).

Освоить программирование на языке высокого уровня гораздо проще, чем на ассемблере. Поэтому с появлением ЯПВУ значительно возросло число прикладных программистов, расширилось применение ЭВМ во многих областях.

Большое количество языков программирования появилось в 1960—1970-х годах. В 1965 году в Дартмутском университете был разработан язык Бейсик. По замыслу авторов это простой, легко изучаемый язык, предназначенный для программирования несложных расчетных задач. Наибольшее распространение Бейсик получил с появлением микроЭВМ и персональных компьютеров.

История Паскаля

Язык программирования Паскаль был создан швейцарским профессором Никлаусом Виртом в 1969 году как язык для обучения студентов структурной методике программирования. Язык получил свое название в честь Блеза Паскаля, изобретателя первого вычислительного механического устройства. Позднее фирма Borland International, Inc (США) разработала систему программирования Турбо Паскаль для персональных компьютеров, которая вышла за рамки учебного применения и стала использоваться для научных и производственных целей. В Турбо Паскаль были внесены некоторые дополнения к базовому стандарту Паскаля, описанному Н. Виртом. Со временем язык развивался. Начиная с версии 5.5, в Турбо Паскаль вводятся средства поддержки объектноориентированного программирования (ООП). В дальнейшем это привело к созданию 0bject Pascal языка с возможностями  объектно-ориентированного программирования. В начале 1990-х годов объединение элементов ООП в Паскале с визуальной технологией программирования привело к созданию системы программирования Delphi.

Структура процедурных языков программирования высокого уровня

Программирование обработки информации

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

Рис. 3.9. Структура процедурного ЯПВУ

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

Соблюдение правил в языке программирования должно быть более строгим, чем в разговорном языке. Человеческая речь содержит значительное количество избыточной информации. Не расслышав какое-то слово, можно понять смысл фразы в целом. Слушающий или читающий человек может додумать, дополнить, исправить ошибки в воспринимаемом тексте. Компьютер же — томат, воспринимающий всё буквально. В текстах программ нет избыточности, компьютер сам не исправит даже очевидной (с точки зрения человека) ошибки. Он может лишь указать на место, которое «не понял», и вывести замечание о предполагаемом характере ошибки. Исправить же ошибку должен программист.

Структура программы на Паскале

Паскаль — язык структурного программирования

5 14

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

Program <имя программы> ; ЬаЬе1 <раздел меток> ;

Const <раздел констант>; Туре <раздел типоо ;

Var <раздел переменных> ;

Procedure (Function) <раздел подпрограмм> ; Begin

<раздел операторов> End.

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

В Турбо Паскале, в отличие от базового стандарта Паскаля, возможно:

 отсутствие заголовка программы;  разделы Const, Туре, Var, Label могут следовать друг за другом в любом порядке и повторяться в разделе описаний сколько угодно раз.

Программирование обработки информации

Система основных понятий

Паскаль— язык структурного программирования
Эволюция программирования
Программирование в машинных кодах (начало 1950-х годов)	Машинно-ориентиро- ванные языки програм- мирования: автокоды, ассемблеры (2-я поло- вина 1950-х годов и позже)	Машинно-независимые языки программирования высокого уровня ЯПВУ (1960-е годы и позже)
Структура процедурного
Элементы языка: алфа- вит, служебные слова и др.	Организация действий над данными: ввод/вы- вод, операции, опера- торы	Организация данных: типы и структуры данных
Паскаль — процедурный язык структурного программирования. Этапы развития: стандартный Паскаль (Н. Вирт), Турбо Паскаль, 0bject Pascal, Delphi
Структура программы на Паскале
Заголовок программы	Раздел описаний	Раздел операторов

Вопросы и задания

1.  В каком виде составлялись программы для первых компьютеров?

2.  Чем отличались программы на автокодах (ассемблерах) от программ в машинных кодах?

З. Почему ЯПВУ являются машинно-независимыми языками программирования?

4.  Что такое трансляция?

5.  В какой парадигме программирования реализован язык Паскаль?

6.  Что входит в структуру любого процедурного ЯПВУ?

7.  Из каких основных разделов состоит программа на Паскале?

S 15 Элементы языка Паскаль и типы данных

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

Латинские буквы: от А до Z (заглавные) и от а до z (строчные).

Цифры: О, 1, 2, З, 4, 5, 6, 7, 8, 9.

Специальные символы: + —— * / < > [ ] •

Следующие комбинации специальных символов являются едиными символами (их нельзя разделять пробелами):

знак присваивания; меньше или равно; больше или равно;

(* *) ограничители комментариев (наряду с { }); не равно;

) эквивалент [ 1.

Пробелы — символ пробела (код ASCII 32) и все управляющие символы кода ASCII (от О до 31).

Элементы языка Паскаль и типы данных

5 15

105

Служебные слова. К спецсимволам относятся и служебные слова, смысл которых определен однозначно. Служебные слова не могут быть использованы для других целей. С точки зрения языка, они являются едиными элементами алфавита. Вот некоторые служебные слова: Program, Var, array, If, Do, Hhile и др.

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

4 любой текст, не содержащий символ ”фигурная скобка ”

(* любой текст, не содержащий символы “ звездочка, круглая скобка”*)

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

Концепция типов данных в Паскале

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

Программирование обработки информации

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

Рис. 3.10. Система типов данных Паскаля

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

В стандартном Паскале Вирта отсутствовал строковый тип. Он был внесен в Турбо Паскаль. Кроме того, в Турбо Паскале целые и вещественные — это группы типов. В старших версиях Турбо Паскаля появился процедурный тип и тип «объект».

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

Таблица 3.2. Типы данных

Имя типа	Длина в байтах	Диапазон (множество) значений	Десятичных цифр в мантиссе
		Целочисленные типы
integer	2	-32768..32767
byte	1	0..255
word	2	0..65535
shortint	1	-128..127
10ngint	4	-2147483648..2147483647
		Вещественные типы
rea1	6	2,9 • 10-39 -1,7 • 1038	11-12
sing1e	4	1,5  • 1038	7-8
doub1e	8	5 10-324 -1,7 • 10	15-16
extended	10	—4932 3,4 • 10      -1,1 • 104932	19-20
		Логический тип
Ьоо1еап	1	True, False
		Символьный тип
char	1	Все символы 8-разрядной кодировки

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

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

         Туре Опля типа>             «список значений>)

Определенное таким образом имя типа затем используется для описания переменных. Например:

Туре Gaz

Meta1           (Ее, со, на, си, zn) ; var G1, G2, (33: Gaz,•

Met1, Met2: Meta1;

Day: (Sun, Моп, Тие, Wed, Thu, Fri, Sat) ;

Здесь Gaz и Metal имена перечислимых типов, которые ставятся в соответствие переменным (71, G2, G3 и Met1, Met2. Переменной Day назначается перечислимый тип, которому не присвоено имени.

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

Перечислимый тип — упорядоченное множество. Его элементы пронумерованы, начиная от О в порядке следования в описании.

В программе, в которой присутствует данное выше описание переменной Ту, возможен такой фрагмент:

Программирование обработки информации

If Day=Sun Then Write ( ' Ура! Сегодня выходной! ) ;

Ограниченный тип задается как упорядоченное ограниченное подмножество некоторого порядкового типа:

<константа 1>. . <константа 2>

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

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

им

          Туре Number s  1. .31;

                   A1f   'A' . . 'Z'

Var Data: Numbers;

Ви Куа : A1f ;

Структурные типы. Особенностью Паскаля является то, что в нем структуры данных рассматриваются как типы — структур-

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

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

Элементы языка Паскаль и типы даННЫХ

5 15

Система основных понятий

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

Вопросы и задания

1. Входят ли в алфавит Паскаля русские буквы? Для чего их можно использовать?

2. Что такое идентификатор? Каковы правила задания идентификаторов?

З. Чем различаются разные типы данных из группы целочисленных типов?

4.  Чем различаются разные типы данных из группы вещественных типов?

5.  В чем разница между простыми и структурными типами?

6.  Что такое перечислимый и ограниченный типы данных?

5 16

Операции, функции, выражения

Арифметические операции

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

Программирование обработки информации

Операции над данными бывают унарными (применимые к одному операнду) и бинарными (применимые к двум операндам). Унарная арифметическая операция в Паскале одна. Это операция изменения знака. Ее формат:

—<величина>

Бинарные арифметические операции стандартного Паскаля описаны в табл. 3.3. В ней символ «1» обозначает целые типы, символ «R» — вещественные типы.

Таблица 3.3. Бинарные операции Паскаля

Знак	Выражение	Типы операндов	результата	Операция
	А+В			Сложение
	А-В		1	Вычитание
	А*В			Умножение
	мв			Вещественное деление
div	А div В			Целочисленное деление
mod	А mod В			Остаток от целочисленного деления

Стандартные функции и процедуры

В Паскале существует большое количество стандартных функций и процедур, к которым программист может обращаться в своих программах. Наиболее часто используются математические функции, например: sqrt (х) — квадратный корень, abs (х) абсолютная величина, sin (х) и др. Часто используемые стандартные процедуры: Read ( ) — процедура ввода, Write ( ... ) — процедура вывода данных.

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

Таблица 3.4 содержит описания стандартных математических функций Паскаля.

Операции, функции, выражения

S 16

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

Uses <имя модуля>

Для управления символьным выводом на экран используется стандартный модуль CRT. К программе он подключается командой:

Uses CRT

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

Арифметические выражения

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

Например, рассмотрим математическое выражение:

0,2с — ln(x — у)

Программирование обработки информации

Таблица 3.4. Стандартные математические функции Паскаля

Обращение	аргумента	результата
			число п = 3,1415926536Е+ОО
abs (х)			Модуль аргумента
arctan (х)			Арктангенс (в радианах)
cos (х)			Косинус (в радианах)
ехр (х)			ех — экспонента
frac (х)			Дробная часть х
int (х)			Целая часть х
			Натуральный логарифм
random			Псевдослучайное число в интервале
random (х)			Псевдослучайное число в интервале
round (х)			Округление до ближайшего целого
sin (х)			Синус (в радианах)
sqr (х)			Квадрат х
sqrt (х)			Корень квадратный
trunc (х)			Ближайшее целое, не превышающее х по модулю

На Паскале оно выглядит так:

(2*A+Sqrt (0 .5*sin (Х+У) ) ) / (Х-У) )

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

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

2. Не допускаются два следующих подряд знака операций.

(Нельзя: А+—В; можно: А+ (—B)

З. Операции с более высоким приоритетом выполняются раньше операций с меньшим приоритетом. Порядок убывания приоритетов:

вычисление функции; унарная операция смены знака (—); * , / , div, mod;

4.  Несколько записанных подряд операций одинакового приоритета выполняются последовательно слева направо.

5.  Часть выражения, заключенная в скобки, вычисляется в первую очередь. (Например, в выражении (А+В) * (C—D) умножение производится после сложения и вычитания.)

Операции, функции, выражения

S 16

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

Пример. Цифрами сверху указан порядок выполнения операций:

           1         7 4 5 3                             12 11 10 8          9

(1+у) * (2*x+sqrt (у) — (Х+У) ) / (у+1/ (sqr (х) —4) )

Данное арифметическое выражение (на Паскале) соответствует следующему математическому выражению:

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

а) если у — целое положительное значение, то его степень вычисляется через умножение; например х³ —» х*х*х; большие степени следует вычислять умножением в цикле;

б) если у — целое отрицательное число, то степень вычисляется так: ху = (1/X)lyl; а при у = О: х^о 1.

в) если у — вещественное значение, не равное нулю, то используется следующая математическая формула: Х ^У = е Паскале получим арифметическое выражение:

ехр (У*1п (х) )

Очевидно, что в этом случае не допускается нулевое или отрицательное значение х. Для целого у такого ограничения нет.

Пример

1

На Паскале это выражение выглядит так:

ехр (1/3*1п (А+1) )

Программирование обработки информации

Выражение имеет целочисленный тип, если в результате его вычисления получается величина целочисленного типа. Выражение имеет вещественный тип, если результатом его вычисления является вещественная величина.

Система основных понятий

Операции, функции, выражения

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

Тип результата операции зависит от типа операндов (табл. 3.3)

Возведение в степень (ХУ): при целом у реализуется через умножение, при вещественном у реализуется так: ехр (y*ln (х) )

Стандартные функции и процедуры описаны в модулях, подключаемых к программе. Модуль S У STEM подключается по умолчанию

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

Вопросы и задания

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

      а) а + bx + cyz;        б) [(ах — + — Ф, в)

                х + у 02                          ⁴ а +3—р;                            е) 1+2 + Щ / 1+ 2

       г)                         д) 10                                                                     

З + ху

2. Запишите математические выражения, соответствующие следующим выражениям на Паскале:

а) (p+q) / (r+s) —p*q/ (r*s) ;

б) 1E3+beta/ (x—gamma*de1ta) ;

в) a/b* (c+d) — (а—Ь) /b/c+1E—8.

Операции, функции, выражения

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

         а) (1 + х)²; б) 467 ; в) cos²x²;       г) log2—•, д) arcsin х; е)

2

р + sin² л

                                                                   10⁷ + ln4!           cos2 + lctgy|

4.  Вычислите значения выражений:

а) trunc (б. 9)	е) round (6.2)
б) trunc (6 . 2)	ж) 20 mod 6
в) 20 div б	з) 2 mod 5
г) 2 div 5	и) 3*7 div 2 mod 7/3 — trunc (sin (1) )

д) round (6. 9)

5.  Определите типы выражений:

                     в) sqr (4)                   д) sin (О)

      б) 20/4                г) sqrt (16)              е) trunc (—3 . 14)

5 17

Оператор присваивания, ввод и вывод данных

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

1) оператор присваивания;

2) оператор ввода;

З) передача значения через параметры подпрограммы.

Оператор присваивания имеет следующий формат:

<переменная> : =<выражение>

Программирование обработки информации

Например:

1) x:=2*a+sqrt (Ь) ;

2) Ь: = (х>у) and             ;

Сначала вычисляется выражение, затем полученное значение присваивается переменной. В первом примере приведен арифметический оператор присваивания. Здесь х переменная вещественного типа. Во втором примере — логический оператор присваивания. Здесь Ь — переменная типа Воо1еап.

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

Ввод и вывод данных

Под вводом понимается передача данных с внешнего устройства компьютера в оперативную память. При выводе данные передаются из оперативной памяти на внешнее устройство (рис. 3.11).

ОЗУ		Внешние устройства
	Вывод (Write)
	Ввод (Read)

Рис. 3.11. Ввод и вывод

Операция ввода называется чтением и выполняется с помощью оператора Read. Вывод называется записью, и для его выполнения используется оператор Write.

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

Оператор присваивания, ввод и вывод данных

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

Устройства ввода с клавиатуры и вывода на экран монитора являются однофайловыми устройствами. Считается, что с клавиатурой связан один системный файл с именем INPUT. Поэтому ввод с клавиатуры равнозначен чтению из файла INPUT. С монитором связан системный файл, который называется OUTPUT. Вывод на экран — это запись данных в файл OUTPUT .

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

Read «список ввода>)

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

Например:

Read (а, Ь, с, д)

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

Пример:

                      Var Т: Rea1; д: Integer;             К: Char ;

Begin

Read(T, З, К) ;

Набираем на клавиатуре:

253.98 100 G [Enterl

Программирование обработки информации

Если в программе имеется несколько подряд идущих операторов Read, то данные для них можно вводить последовательно (на экране отражаются в одной строке) и лишь в конце ввода нужно нажать клавишу Enter. Пример:

Var А, В: Integer;

                           С, D: Rea1;

Begin

                           Read(A, В) ;         Read (С, D) ;

Набираем на клавиатуре и видим на экране:

18758 34 2.62Е-О2 1.54Е+О1 [Enter]

Другой вариант оператора ввода с клавиатуры имеет вид:

ReadLn «список ввода>)

Здесь слово «ReadLn» означает read line «читать строку». Нажатие клавиши Enter в процессе ввода вырабатывает признак «конец строки», и данные при выполнении следующего оператора ввода будут отражаться на экране с начала новой строки. Если в предыдущем примере заменить операторы Read на ReadLn:

ReadLn (А, В) ; ReadLn (С, D) ;

то ввод значений будет происходить из двух строк, отраженных на экране:

18758 34 [Enter]

2. 62Е-О2 1.54Е+О1 [Enter]

Вывод на экран производится по оператору обращения к стандартной процедуре:

Write «список вывода>)

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

         Например: Write ( Сумма ' ,     

Если, например, А 5 и В = 7, то на экране получим:

Сумма 5+7=12

Оператор присваивания, ввод и вывод данных

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

Второй вариант процедуры вывода на экран:

WriteLn «список вывода>)

Write line — «писать строку». Его действие отличается от оператора Write тем, что после вывода последнего в списке значения происходит перевод курсора к началу следующей строки. Оператор WriteLn, записанный без параметров, вызывает перевод строки.

В списке вывода могут присутствовать указатели форматов вывода (форматы). Формат определяет представление выводимого значения на экране. Формат отделяется от соответствующего ему элемента двоеточием. Если указатель формата отсутствует, то машина выводит значение по определенному правилу, предусмотренному по умолчанию.

Линейная программа. Следование — простейшая алгоритмическая структура. Программа, реализующая следование, называется линейной программой. В линейной программе могут присутствовать только операторы присваивания, ввода, вывода и обращения к процедурам. Заметим, что операторы Read и Write являются обращениями к стандартным процедурам Паскаля.

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

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

Program Mu1tiply ;

Var А, В, АВ: integer;

Begin

                        Write ('А=             ReadLn (А) ;

                       Write ( '                 ReadLn (В) ;

Write (А,    в, End.

Программирование обработки информации

Тестирование этой программы отразится на экране следующим образом. А- 13 в— 28

Числа 13 и 28 вводятся пользователем с клавиатуры, всё остальное автоматически выводится по программе.

Пример 2. Дано натуральное трехзначное число. Требуется вычислить сумму его цифр. Например, если дано число 325, то в результате должно получиться: З + 2 + 5 == 10.

Сначала составим программу, а потом ее прокомментируем.

Program SumCifr ;

Var Х, „Бит: integer;

Begin

                       Write ( Введите трехзначное число              ReadLn (Х) ;

Бит :

Sum : =Sum + Х mod 10; div 10;

Sum:=Sum + Х mod

Х:=Х div 10;

Sum : =Sum + Х;

Write ( Сумма цифр       Sum) End.

В этой программе использованы две операции целочисленной арифметики: div — целочисленное деление и mod — остаток от целочисленного деления (см. табл. 3.3). Остаток от деления на 10 (mod) выделяет младшую цифру числа, а целочисленное деление на 10 (div) отбрасывает младшую цифру.

Оператор присваивания, ввод и вывод данных

5 17

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

	Команда			Х	S um
1	read1n (Х)			325
2	Sum :
З	Sum : =Sum	mod 10			5
4	div 10			32
5	Бит : =Sum	mod 10			7
6	div 10			з
7					10
8	Write ( Сумма	цифр =	Бит)		10

Выполнение программы на компБютере приводит к такому же результату.

Заметим, что эту задачу можно решить с помощью всего одного оператора присваивания:

Sum:=X mod 10 + Х div 10 mod 10 + Х div 100

Проверьте самостоятельно.

Программирование обработки информации

Система основных понятий

Оператор присваивания: «(переменная> : =<выражение> Тип переменной и выражения должны совпадать. Исключение: вещественной переменной можно присваивать значение целого выражения

Ввод — передача данных с внешнего устройства в ОЗУ

Ввод с клавиатуры: Read «список ввода» или ReadLn «список ввод»)

Вывод — передача данных из ОЗУ на внешнее устройство

Вывод на экран: Write «список вывода>) или WriteLn «список вывода>)

Линейная программа состоит из операторов ввода, вывода, присваивания и обращения к процедурам

Вопросы и задания

1. Назовите последовательность действий при выполнении оператора присваивания.

2. Сформулируйте правило соответствия типов для оператора присваивания. Какое существует исключение из этого правила?

3, Если у — вещественная переменная, а п — целая, то какие из следующих операторов присваивания правильные, а какие — нет?

                       а) у : =п+1                                              div 2

                                б) п : =у—1                                                              div 2

                       г) у: =trunc (у)                     з) n:=sqr (sqrt (п) )

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

5.  Напишите оператор присваивания, в результате выполнения которого целочисленной переменной h присвоится значение цифры, стоящей в разряде сотен в записи положительного целого числа К (например, если 28 796, то 7).

6.  Напишите линейную программу, в результате выполнения которой в целочисленной переменной S получится перевернутое целое четырехзначное число К. Например: если 1357, то S = 7531.

7.  Напишите линейную программу перевода любого целого четырехзначного двоичного числа в десятичную систему счисления. Например, дано число в двоичной системе счисления: 11012. Перевод в десятичную систему выполняется так: 1 • 2³ + 1 • 2 ² + О • 2 ¹ + 1 = 13.

S 18 Логические величины, операции, выражения

Логические величины, операции, выражения

5 18

123

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

К числу основных понятий логики относятся: высказывание, логическая величина, логические операции, логические выражения и формулы.

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

Например, высказывание «На улице идет дождь» будет истинным или ложным в зависимости от состояния погоды в данный момент. Истинность высказывания «Значение А больше, чем В», записанного в форме неравенства: А > В, будет зависеть от значений переменных А и В.

Логические величины понятия, выражаемые словами: ИСТИНА, ЛОЖЬ (true, false). Следовательно, истинность высказываний выражается через логические величины.

Логическая константа: ИСТИНА или ЛОЖЬ.

Логическая переменная: символически обозначенная логическая величина. Следовательно, если известно, что А, В, Х, У

и др. — переменные логические величины, то, значит, они могут принимать значения только ИСТИНА или ЛОЖЬ.

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

Логические операции

Конъюнкция (логическое умножение). В русском языке она выражается союзом И. В математической логике используются знаки & или л. Конъюнкция — двухместная операция; записывается в виде: А & В. Значением такого выражения будет ЛОЖЬ, если значение хотя бы одного из операндов ложно.

Дизъюнкция (логическое сложение). В русском языке этой связке соответствует союз ИЛИ. В математической логике она обозначается знаком м. Дизъюнкция двухместная операция; записывается в виде: А v В. Значением такого выражения будет ИСТИНА, если значение хотя бы одного из операндов истинно.

Программирование обработки информации

Отрицание. В русском языке этой связке соответствует частица НЕ (в некоторых высказываниях применяется оборот «неверно, что ... Отрицание — унарная (одноместная) операция; записывается в виде: А или А.

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

			А&В	АМ В
и	и	л	и	и
и	л	л	л	и
л	и	и	л	и
л	л	и	л	л

Логическая формула формула, содержащая лишь логические величины и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА или ЛОЖЬ.

Последовательность выполнения операций в логических формулах определяется старшинством операций. В порядке убывания старшинства логические операции расположены так: отрицание, конъюнкция, ДИЗЪЮНКЦИЯ. Кроме того, на порядок выполнения операций влияют скобки, которые можно использовать в логических формулах. Например:

Пример. Вычислить значение логической формулы:

если логические переменные имеют следующие значения: Х ЛОЖЬ, У — ИСТИНА, 74 ИСТИНА.

Решение. Отметим цифрами сверху порядок выполнения операций в формуле:

1 2 4 з

Используя таблицу истинности, вычислим формулу по шагам:

Логические величины, операции, выражения

5 18

1)  

„ЛОЖЬ = ИСТИНА;

2)   ИСТИНА ИСТИНА = ИСТИНА;

3)   ЛОЖЬ ИСТИНА ЛОЖЬ; 4) ИСТИНА ЛОЖЬ = ИСТИНА. Ответ: ИСТИНА.

Логические функции на области числовых значений

Алгебра чисел пересекается с алгеброй логики в тех случаях, когда приходится проверять принадлежность значений алгебраических выражений некоторому множеству. Например, принадлежность значения числовой переменной Х множеству положительных чисел выражается через высказывание: «Х больше нуля». Символически это записывается так: Х>О. В алгебре такое выражение называют неравенством. В логике — отношением.

Отношение Х > О может быть истинным или ложным. Если Х — положительная величина, то оно истинно, если отрицательная, то ложно. В общем виде отношение имеет следующую структуру:

«(выражение 1> знак отношения> <выражение 2>

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

равно;

 — не равно;

 — больше или равно;

— меньше или равно;

> — больше;

— меньше.

Например:

х = 5; а + Ь * х — 1; 6² — 4ас О; sin(x) х/2.

Итак, отношение — это простое высказывание, а значит, логическая величина. Оно может быть как постоянной: 5 > О всегда ИСТИНА, З * 6 : 2 — всегда ЛОЖЬ; так и переменной: а < Ь, х + 1 с — d. Если в отношение входят переменные числовые величины, то и значение отношения будет логической переменной.

Программирование обработки информации

Отношение можно рассматривать как логическую функцию от числовых аргументов. Например: F(x) = (х > О) или Р(х, у) — = (х < у). Аргументы определены на бесконечном множестве действительных чисел, а значения функции — на множестве, состоящем из двух логических величин: ИСТИНА, ЛОЖЬ.

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