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

Корректность. Решение должно быть правильным для любых допустимых исходных данных.

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

Исполнитель -- фундаментальное понятие информа-тики. Оно входит в определение алгоритма.

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

Каковы наиболее важные черты исполнителей?

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

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

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

Третьей важной особенностью исполнителей является наличие различных режимов его работы; перечень режи-мов у каждого исполнителя, естественно, свой. Для боль-шинства учебных исполнителей особо выделяют режимы непосредственного и программного управления1. В первом случае исполнитель ожидает команд от человека и каждую немедленно выполняет. Во втором исполнителю сначала задается полная последовательность команд (программа), а затем он исполняет ее в автоматическом режиме. Боль-шинство исполнителей могут работать в обоих режимах.

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

Желательно изложить

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

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

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

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

1 Аналогичные режимы издавна существовали в языке Бейсик, где строка без номера немедленно исполнялась интерпретатором, а с номером -- заносилась в память для последующего исполне-ния; нечто похожее существует и в более поздних версиях под MS-DOS, реализованных в виде компиляторов.

ных частей, которые принято называть тактами (пом-ните термин "тактовая частота процессора" ? -- он про-исходит именно отсюда!). В зависимости от сложности команды, она может быть реализована за разное коли-чество тактов.

При выполнении каждой команды ЭВМ проделывает определенные стандартные действия, описанные ниже.

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

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

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

4. Все описанные действия циклически повторяются с п. 1.

Рассмотренный основной алгоритм работы ЭВМ по-зволяет шаг за шагом выполнить хранящуюся в ОЗУ про-грамму.

Примечания для учителей

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

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

Возможно, не все учителя считают нужным излагать материал об основном алгоритме работы ЭВМ. Тем не менее, обосновывая формальность исполнения програм-мы, о нем желательно сказать.

Примечания для учеников

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

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

2 Б порядке исключения, так как обычно, напротив, всегда при-зывали к осмысленному запоминанию материала, а не заучиванию

Готовимся к экзамену по информатике

Е.А. Еремин, В.И. Чернатынский, А.П. Шестаков,

г. Пермь

Продолжение. См. № 10--15/2004

БИЛЕТ № 15

1. Алгоритмическая структура "ветвление". I Команда ветвления. Примеры полного и неполного | ветвления.

2. Двоичное кодирование текстовой информации, i Различные кодировки кириллицы.

3. Практическое задание. Формирование запроса I на поиск данных в среде системы управления база- | ми данных.

1. Алгоритмическая структура "ветвление". Команда ветвления. Примеры полного и неполного ветвления

Базовые понятия

Алгоритм, ветвление, условие, полное ветвление и неполное ветвление.

Обязательно изложить

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

В словесной форме представления алгоритма "ветв-ление" реализуется в виде команды:

ЕСЛИ <АВ> то <Серия 1> ИНАЧЕ <Серия2>

Здесь <ЛВ> -- это логическое выражение, < Серия 1> -- описание последовательности действий,

которые должны выполняться, когда <ЛВ> прини-мает значение ИСТИНА, < Серия 2> -- описание пос-ледовательности действий, которые должны выпол-няться, когда <ЛВ> принимает значение ЛОЖЬ. Любая из серий может быть пустой. В этом случае ветвление называется неполным. Каждая серия мо-жет, в свою очередь, содержать команду ветвления, что позволяет реализовать не только альтернативный выбор действий.

Если для представления алгоритма используется блок-схема, структура "ветвление" изображается так:

Полное ветвление Неполное ветвление

В языке программирования Turbo Pascal структура ветвления изображается оператором:

IF <ЛВ> THEN <БЛОК1> ELSE <БлОк2>;

Здесь <Бл<ж1> и <Блок2> -- последовательности операторов языка Turbo Pascal, заключенные в опера-торные скобки BEGIN . . END.

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

Алгоритм

/ *'Y /

i Г

Конец

2004 № 17 ИНФОРМАТИКА

Программа

PROGRAM SORT;

VAR X,Y,C: STRING;

BEGIN

WRITELN (-'Введи две фамилии'); READLN(X,Y); IF X > Y THEN BEGIN

С := X; X := Y; Y := С END;

WRITELN('После сортировки'); WRITELN (X); WRITELN (Y) END.

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

Алгоритм

Программа

PROGRAM REL; VAR А,В,С: REAL; BEGIN

WRITELN('Введи 2 числа'); READLN(А,В); IF В О О THEN

BEGIN

С := А/В; WRITELN('С = ',С) END ELSE

WRITELN('ДЕЛЕНИЕ HA 0') END.

Ссылка на материалы вопроса

1. Угринович Н. Информатика и информационные технологии. Учебное пособие для 10--11-х классов. Углубленный курс. М.: Лаборатория Базовых Знаний, 2000, 440 с.

2. Семакин И., Залогова А., Русаков С., Шестакова Л. Базовый курс для 7--9-х классов. М.: Лаборатория Базовых Знаний, 2001, 384 с.

2. Двоичное кодирование текстовой информации. Различные кодировки кириллицы

Базовые понятия

Код, кодирование, двоичное кодирование, символ, код символа, кодировочная таблица.

Обязательно изложить

Если каждому символу какого-либо алфавита сопос-тавить определенное целое число, то с помощью дво-ичного кода можно кодировать и текстовую информа-цию. Для хранения двоичного кода одного символа может быть выделен 1 байт = 8 бит. Учитывая, что каждый бит принимает значение 0 или 1, количество их возможных сочетаний в байте равно 28 = 256. Зна-чит, с помощью 1 байта можно получить 256 разных двоичных кодовых комбинаций и отобразить с их по-мощью 256 различных символов. Такое количество символов вполне достаточно для представления тек-стовой информации, включая прописные и заглавные буквы русского и латинского алфавита, цифры, знаки, псевдографические символы и т.д. Кодирование зак-лючается в том, что каждому символу ставится в соот-ветствие уникальный десятичный код от 0 до 255 или соответствующий ему двоичный код от 00000000 до 11111111. Таким образом, человек различает символы по их начертанию, а компьютер -- по их коду. Важ-но, что присвоение символу конкретного кода -- это вопрос соглашения, которое фиксируется в кодовой таблице. Кодирование текстовой информации с помо-щью байтов опирается на несколько различных стан-дартов, но первоосновой для всех стал стандарт ASCII (American Standard Code for Information Interchange), разработанный в США в Национальном институте ANSI (American National Standards Institute). В систе-ме ASCII закреплены две таблицы кодирования -- базовая и расширенная. Базовая таблица закрепляет значения кодов от 0 до 127, а расширенная относится к символам с номерами от 128 до 255. Первые 33 кода (с 0 до 32) соответствуют не символам, а опера-циям (перевод строки, ввод пробела и т.д.). Коды с 33-го по 127-й являются интернациональными и со-ответствуют символам латинского алфавита, цифрам, знакам арифметических операций и знакам препина-ния. Коды с 128-го по 255-й являются национальны-ми, т.е. в национальных кодировках одному и тому же коду соответствуют различные символы.

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

В настоящее время существует несколько различ-ных кодовых таблиц для русских букв (КОИ-8,

2004 № 17 ИНФОРМАТИКА

СР-1251, СР-866, Mac, ISO), поэтому тексты, создан-ные в одной кодировке, могут неправильно отобра-жаться в другой.

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

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

Международная организация по стандартизации (International Organization for Standardization, или IOS) разработала свой код, способный соперничать с Unicode. Здесь для кодирования символов использует-ся комбинация из 32 бит.

Желательно изложить

Кодирование и шифрование текста -- исторический подход.

Перевод текста из одной кодировки в другую.

Ссылка на материалы вопроса

"Информатика" № 12, 2003, с. 3 -- 5.

3. Практическое задание. Формирование запроса на поиск данных в среде системы управления базами данных

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

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

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

Примеры заданий

В качестве вариантов заданий можно использовать материалы задачника-практикума "Информатика. За-дачник-практикум в 2 т." / Под ред. И.Г. Семакина, Е.К. Хеннера. Т. 1, 2. М.: Лаборатория Базовых Зна-ний, 1999.

Примеры запросов можно посмотреть в статье: Брыз-галов Е.В., Шестаков А.П. Уроки по Access // Инфор-матика и образование № 7, 2000, с. 18--29.

Ссылка на материалы

"Информатика" № 16, 2002, с. 13--22.

БИЛЕТ № 16

1. Алгоритмическая структура "цикл". Циклы со I счетчиком и циклы по условию

I 2. Двоичное кодирование графической информа- I | ции. Растр. Пиксель. Глубина цвета

I 3. Задача на определение количества информа- I I ции и преобразование единиц измерения количест- i . ва информации1. Алгоритмическая структура "цикл". Циклы со счетчиком и циклы по условию

Базовые понятия

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

Циклы с неопределенным количеством повторений (по условию) и с параметром (счетчиком).

Обязательно изложить

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

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

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

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

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

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

Желательно изложить

Циклы с неопределенным количеством повторений, как правило, не имеют каких-то существенных осо-бенностей реализации в различных языках. А вот цикл с параметром (FOR), напротив, часто обладает теми или иными специфическими свойствами. Например, в языке Бейсик, где параметром цикла может быть только числовая переменная (но зато любого типа), разрешается цикл от 0 до 1 с дробным шагом изме-нения 0.1. В Паскале параметр цикла не обязательно числовой, но зато он должен являться порядковым (иметь конечный упорядоченный набор допустимых значений). Таким образом, можно строить циклы по целым, символьным (CHAR), логическим, заданным перечнем своих значений и некоторым другим типам переменных, но зато запрещено использование веще-ственных значений1. Фактически в Паскале при каж-дом новом исполнении цикла берется или следующее, или предыдущее в используемом типе значение. В языке Си цикл FOR еще более интересный. Его заголовок фактически содержит три части: действия по инициа-лизации, действия по проверке окончания цикла и,

1 Хотя бы потому, что для вещественных чисел не определено понятие "следующий": в самом деле, какое значение следует пос-ле 1.1 - 1.2, 1.11 или 1.101?

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

for (i = 0, j = n - 1; i < n; i++, j --) a[i] = a[j];

Настолько общий подход позволяет вообще напи-сать цикл без содержимого: например, сам оператор организации цикла

for (s=0, i = 1; i < 11; s=s+i, i=i+l) уже вычисляет сумму первых 10 натуральных чисел.

Примечание. Ярые приверженцы Си последние два опе-ратора никогда не напишут иначе, чем s += i, i++, давая возможность компилятору составить чуть более эффективную программу. Но мне хотелось сделать текст более удобочитае-мым для тех, чье мышление не связано с конкретными комби-нациями значков.

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

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

Примечание для учителей

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

Примечание для учеников

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

2. Двоичное кодирование графической информации. Растр. Пиксель. Глубина цвета

Базовые понятия

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

Пиксель -- логический элемент изображения.

Обязательно изложить

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

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

Ссылка на материалы вопроса

"Информатика" № 14, 2003, с. 3 -- 8.

2. Двоичное кодирование звуковой информации. Глубина кодирования и частота дискретизации

Базовые понятия

Дискретная и непрерывная форма представления информации. Аналого-цифровой и цифро-аналоговый преобразователи.

Дискретизация звукового сигнала по времени и ам-плитуде.

Теорема Найквиста для выбора частоты дискрети-зации звука.

Обязательно изложить

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

Каковы основные принципы работы АЦП?

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

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

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

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

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

Желательно изложить

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

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

БИЛЕТ № 17

1. Технология решения задач с помощью компьютера! | (моделирование, формализация, алгоритмизация, програм-1 мирование). Показать на примере задачи (математиче-ской, физической, экономической, экологической). ' 2. Двоичное кодирование звуковой информации. I | Глубина кодирования и частота дискретизации.3. Задача. Составление таблицы истинности для ло-| I гической функции, содержащей операции отрицания, (инверсию), умножения (конъюнкцию), сложения

I (дизъюнкцию).

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

Базовые понятия

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

Обязательно изложить

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

Первый этап -- определение целей моделирования. Основные из них таковы:

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

* научиться управлять объектом (или процессом) и определить наилучшие способы управления при задан-ных целях и критериях (оптимизационные и много-критериальные модели);

* научиться прогнозировать прямые и косвенные последствия воздействия на объект (игровые и ими-тационные модели).

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

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

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

Моделирование -- процесс построения формальной модели реального явления и ее использование в целях исследования моделируемого явления.

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

Если в качестве средства решения задачи' выступает тот или иной язык программирования (впрочем, это актуаль-но и для математических пакетов), следующий этап -- разработка алгоритма и составление программы для ЭВМ (понятия алгоритма и программы подробно рассматри-ваются в билете 13, вопрос 1; а основы алгоритмическо-го программирования -- в билете 2, вопрос 2).

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

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

Примеры решения содержательных задач из раз-личных областей см.: Шестаков А.П. Профильное обу-чение информатике в старших классах средней школы (10--11-е классы) на основе курса "Компьютерное математическое моделирование" (КММ) // "Инфор-матика" № 34, 36, 38, 40, 42, 44, 46, 48/2002.

Желательно изложить

История развития технологии решения задач с ис-пользованием ЭВМ.

Примечание для учителей

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

Для высококачественного воспроизведения звука верхнюю границу обычно с некоторым запасом при-нимают равной 22 кГц. Отсюда из теоремы Найквис-та следует, что частота звукозаписи в таких случаях (например, при записи музыкальных компакт-дисков) должна быть не ниже 44 кГц2. Часто такое высокое качество не требуется, и частоту дискретизации мож-но значительно снизить. Например, при записи речи вполне достаточно частоты дискретизации 8 кГц. За-метим, что результат при этом получается хотя и не блестящий, но легко разборчивый3 -- вспомните, как вы слышите голоса своих друзей по телефону.

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

Примечание для учителей

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

Примечание для учеников

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

2 Обычно используется значение 44 032 Гц, которое делится нацело на 256.

3 Известно, что высокие частоты в основном влияют на "окрас-ку" (тембр) человеческого голоса.

Ссылка на материалы по вопросу

Подробные материалы опубликованы в "Информа-тике" № 14, 2003. Электронная версия имеется на сайте редакции по адресу http:/ /inf.lsepteniber.ru/ eremin/emc/theory/info/Ъ17__2.html.

По поводу непрерывной и дискретной информации можем порекомендовать почитать ответ на "старый вопрос 3 билета 10, опубликованный в "Информати-ке" № 14, 2003 (также доступно в Интернете по ссыл-ке из списка литературы предыдущего вопроса).

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

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

Вариант 1. Доказать распределительный закон:

~Х и Y * Z = (X u F) * (~Х u Z)

Решение. Построим таблицу истинности, придавая возможные значения логическим переменным (1 -- ис-тина, 0 -- ложь) и пользуясь соглашением о приоритете логических операций (НЕ, И, ИЛИ в порядке БИЛЕТ № 18 I

I 1. Программные средства и технологии обработ-| ки текстовой информации (текстовый редактор, | текстовый процессор, редакционно-издательские i системы).

2. Алгоритмическая структура

3. Задача. Перевод десятичных чисел в двоичную,' I восьмеричную, шестнадцатеричную системы счис-1 | ления

1. Программные средства и технологии обработки текстовой информации (текстовый редактор, текстовый процессор, редакционно-издательские системы)

Базовые понятия

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

Обязательно изложить

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

Основные функции текстовых процессоров:

* создание документов;

* редактирование;

* сохранение документов во внешней памяти (на дисках) и чтение из внешней памяти в оперативную;

* форматирование документов;

* печать документов;

* составление оглавлений и указателей в документе;

* создание и форматирование таблиц;

* внедрение в документ рисунков, формул и др.;

* проверка пунктуации и орфографии.

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

Обычно текстовые процессоры предусматривают две основные операции изменения формата доку-мента:

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

* форматирование абзацев.

При форматировании символов можно изменить:

* шрифт;

* начертание шрифта (полужирный, курсив, под-черкнутый);

* размер шрифта;

* межсимвольный интервал;

* применить к символам эффекты (нижний, верх-ний индекс, малые строчные буквы и т.д.).

При форматировании символов можно изменить:

* способ выравнивания строк абзаца (влево, впра-во, по центру, по ширине);

* отступ в красной строке абзаца;

* ширину и положение абзаца на странице;

* межстрочное расстояние (интерлиньяж) и рас-стояние между соседними абзацами;

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

Наиболее распространенные форматы текстовых файлов: текстовый, Rich Text Format, текст DOS, до-кумент Word, документ HTML.

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

Настольные издательские системы представляют собой комплекс аппаратных и программных средств, предназначенных для компьютерного набора, верст-ки и издания текстовых и иллюстративных материа-лов. Отметим, что с аппаратной точки зрения про-фессиональная работа с издательской системой тре-бует прежде всего монитора с достаточно большой диагональю (19--25"), производительного видеоадап-тера с достаточным объемом видеопамяти (порядка 256 Мб -- 1 Гб), производительного процессора и объемного жесткого диска. Это связано с тем, что макет чаще всего содержит немало иллюстраций вы-сокого качества, что и требует использования приве-денных выше ресурсов.

Назовем некоторые издательские системы: Express Publisher, Illustrator for Windows, Ventura Publisher, PageMaker, TeX (LaTeX) и др. Первые системы обще-го назначения, последняя предназначена прежде всего для верстки текста с преобладанием математических формул и используется многими научными физико-математическими журналами.

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

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

Желательно изложить

Правила компьютерного набора и оформления текстов.

Отличительные черты текстовых процессоров в раз-ных операционных системах.

Дополнительные возможности текстовых процессо-ров как настольных издательских систем.

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

Сканирование и распознавание текстовой инфор-мации.

Ссылка на материалы вопроса

"Информатика" № 14, 2003, с. 3 -- 8.

2. Алгоритмическая структура "выбор" Базовые понятия

Оператор выбора (оператор множественного ветв-ления).

Обязательно изложить

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

В алгоритмической структуре "выбор" вычисля-ется выражение /с и выбирается ветвь, значение метки которой совпадает со значением k. После выполне-ния выбранной ветви происходит выход из конст-рукции выбрра (в СН--К в отличие от Turbo Pascal, такой выход не осуществляется, а продолжают вы-полняться последующие операторы, поэтому для при-нудительного завершения оператора выбора приме-нятся оператор break). Если в последовательности нет метки со значением, равным значению выраже-ния /с, то управление передается внешнему операто-ру, следующему за конструкцией выбора (это про-исходит в случае отсутствия альтернативы выбора; если она есть, то выполняется следующий за ней оператор, а уже затем управление передается внеш-нему оператору).

Запись оператора выбора: Turbo Pascal

case k of

Al : серия 1; A2 : серия 2;

AN : серия N; else серия N + 1 end;

C++

switch (k)

{case Al :

case A2 :

серия 1; break; серия 2; break;

case AN : серия N; break; default: серия N + 1;}

Любая из указанных серий операторов может со-стоять как из единственного оператора, так и не-скольких (в этом случае, как обычно, операторы, от-носящиеся к одной метке, должны быть заключены в операторные скобки begin, .end -- в Turbo Pascal и {..} -в C++).

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

Привести примеры задач с использованием опера-тора выбора.

Желательно изложить

Сравнительная характеристика условного операто-ра и оператора выбора.

Примечание для учителей

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

Ссылка на материалы вопроса

1. "Информатика" № 14, 2003, с. 3 -- 8.

2. http://comp-science.narod.ru/Progr/UsljCase.htm.

3. Перевод десятичных чисел в двоичную, восьмеричную, шестнадцатеричную системы счисления.

Теоретический материал к этой задаче содержится в билете № 13, вопрос 2. Примеры перевода с под-робными пояснениями и варианты заданий можно найти на сайте http:\comp-science.narod.ru\ Progr\Syst_Sch.html и в газете "Информатика" № 19, 2002, с. 5--7.

БИЛЕТ № 19

Программные средства и технологии обработки |

| числовой информации (электронные калькуляторы I

| и электронные таблицы). Назначение и принципы i

I работы

2. Событийное объектно-ориентированное про- ,

граммирование. Событийные и общие процедуры.

3. Компьютерные вирусы. Практическое зада- '

I ние. Исследование дискет на наличие вируса с по- I

I мощью антивирусной программы.

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

Примечания для учителей

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

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

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

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

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

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

Итак, как можно поступить в данной ситуации? Возможно несколько путей.

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

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

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

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

Базовые понятия

Технологии обработки числовой информации на современном компьютере. Электронные таблицы.

Обязательно изложить

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

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

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

Современное программное обеспечение, имеющее своей целью реализацию на компьютере всевозможных расчетов, необычайно разнообразно. Для организации вычислений с помощью ЭВМ существует большое коли-чество программ, которые различаются идеологией по-строения, набором возможностей, степенью автомати-зации расчетов, трудозатратами на организацию вычис-лительного процесса, а также возможностями представ-ления результатов (например, в графическом виде). Ко-нечно, круг программных средств и технологий обработ-ки, числовой информации не ограничивается калькулято-рами и электронными таблицами. Любой школьник знает, что вычислительные задачи можно эффективно решать с помощью языков программирования. Некоторые даже имели опыт работы с системами аналитических преоб-разований математических выражений (Maple, Mathematica или им подобными), которые могут, преж-де чем подставлять конкретные числовые значения, ре-шить задачу в общем виде; часто полученных формул уже без всяких дополнительных расчетов бывает доста-точно, чтобы понять результаты задачи.

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

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