Методические рекомендации по изучению темы

Изучаемые вопросы:

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

ª Основные понятия позиционных систем: основание, алфавит.

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

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

ª Особенности двоичной арифметики.

ª Связь между двоичной и шестнадцатеричной системами.

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

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

XXX 333

Первое — римское тридцать, второе — арабское триста тридцать три. И задайте вопрос: «Чем отличается принцип записи многозначных чисел римскими и арабскими цифрами?» Скорее всего, вы сразу не услышите тот ответ, который бы хотели получить. Тогда, указывая на отдельные цифры римского числа, спрашивайте: «Что (какое количество) обозначает эта цифра?» Получите ответ: «Десять!» — «А эта цифра?» — «Десять!» — «А эта?» — «Десять» — «Как получается значение данного трехзначного числа?» — «Десять прибавить десять, прибавить десять, получается тридцать!» А теперь переходим к числу 333. Снова задаем вопросы: «Какое количество в записи числа обозначает первая цифра справа?» — «Три единицы!» — «А вторая цифра?» — «Три десятка!» — «А третья цифра?» — «Три сотни!» — «А как получается общее значение числа?» — «К трем единицам прибавить три десятка и прибавить три сотни получится триста тридцать три!»

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

Система счисления — это определенный способ представления чисел и соответствующие ему правила действия над числами.

Римский способ записи чисел является примером непозиционной системы счисления, а арабский — это позиционная система счисления.

Следует подчеркнуть связь между способом записи чисел и приемами арифметических вычислениц в соответствующей системе счисления. Предложите ученикам выполнить умножение, например, числа сто тридцать четыре на семьдесят шесть, используя римскую и арабскую системы счислений! С арабскими числами они легко справятся, а также смогут убедиться, что римские цифры — не помощники в вычислениях. В римской системе нет простых и понятных правил выполнения вычислений с многозначными числами. Для арабской системы такие правила известны еще с IX в. В этой теме полезно рассказать ученикам, что правила выполнения вычислений с многозначными числами были разработаны выдающимся математиком средневекового Востока Мухамедом аль-Хорезми и в Европе были названы алгоритмами (от латинского написания имени аль-Хорезми — Algorithm!). Этот факт следует напомнить позже, при изучении алгоритмизации. Итак, именно позиционные системы счисления стали основой современной математики. Далее, как и в математике, в информатике мы будем иметь дело только с числами в позиционных системах счисления.

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

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

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

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,..., 19, 20,..., 99, 100, 101,...

Принцип построения ряда такой: сначала в порядке возрастания значений записываются все однозначные числа; первое двузначное число — всегда 10 (у многозначных целых чисел 0 впереди не является значащей цифрой и обычно не пишется). Далее следуют все двузначные сочетания единицы с другими цифрами; затем — двузначные числа, начинающиеся с 2, затем — с 3 и т. д. Самое большое двузначное число — 99. Затем идут трехзначные числа, начиная от 100 до 999 и т.д.

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

1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33, 100,

101, 102, 103, ПО, 111,..., 333, 1000,...

Аналогично и для других систем. Наибольший интерес представляет натуральный ряд двоичных чисел. Вот как он выглядит:

1, 10, 11, 100, 101, ПО, 111, 1000, 1001, 1010, 1011, 1100,

1101, 1110, 1111, 10000,...

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

Для указания на основание системы, к которой относится число, вводим индексное обозначение. Например, 36₈ указывает на то, что это число в восьмеричной системе счисления, 1А6,₆ — шестнадцатеричное число, 1011₂ — число в двоичной системе. Индекс всегда записывается десятичным числом. Следует подчеркнуть то, что в любой системе счисления ее основание записывается как 10.

Еще одно важное замечание: ни в коем случае нельзя называть недесятичные числа так же, как десятичные. Например, нельзя называть восьмеричное число 36₈ как тридцать шесть! Надо говорить: «Три — шесть». Или, нельзя читать 101₂ как «сто один». Надо говорить «один — ноль — один». Следует также понимать, что, например, 0,1₂ — это не одна десятая, а одна вторая, или 0,1₈ — это одна восьмая и т. п.

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

5319,12 = 5000 + 300 + 10 + 9 + 0,1 + 0,02 =

= 5´10³ + 3´10² + 1´10¹ + 9 + 1´10^-1 + 2´10^-2.

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

1753₈ = 1´10³ + 7´10² + 5´10¹ + 3.

Здесь 10₈ = 8₁₀.

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

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

1753₈ = (1´10³ + 7´10² + 5´10¹ + 3)₈ = (1´8³ +7´8² + 5´8¹+ 3)₁₀.

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

1753₈ = (192 + 448 + 40 + 3)₁₀ = 683₁₀.

Чаще всего развернутую форму числа сразу записывают в десятичной системе. Вот еще пример с двоичным числом:

101101,1₂ =(1х2⁵ + 0´2⁴ + 1´2³ + 1´2² + 0´2¹ + 1 + 1´2^-1)₁₀ = 32 + 8 + 4 + 1 + 0,5 = 45,5₁₀

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

1753₈ = (1´8³ + 7´8² + 5´8¹ + 3)₁₀ = ((1´8 + 7) ´8 + 5) ´8 + 3.

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

Перевод десятичных чисел в другие системы счисления — задача более сложная. В принципе, все происходит через ту же самую развернутую форму записи числа. Только теперь нужно суметь десятичное число разложить в сумму по степеням нового основания п Ф 10. Например, число 85,₀ по степеням двойки раскладывается так:

85₁₀ = 1´2⁶ + 0´2⁵ + 1´2⁴ + 0´2³ + 1´2² + 0´2 + 1 = - 1010101₂.

Однако проделать это в уме довольно сложно. Здесь следует показать формальную процедуру (алгоритм) такого перевода. Описание алгоритма можно прочитать в учебнике [9] или пособии [1]. Там же дается математическое обоснование алгоритма. Разбор этого обоснования требует от учеников определенного уровня математической грамотности и возможен в варианте углубленного изучения базового курса.

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

Если ставится цель получения при переводе дробного числа наиболее близкого значения, то, ограничивая число знаков, нужно производить округления. Для этого в процессе перевода следует вычислять на одну цифру больше, а затем, применяя правила округления, сокращать эту цифру. Выполняя округление, нужно соблюдать следующее правило: если первая отбрасываемая цифра больше или равна n/2 (п — основание системы), то к сохраняемому младшему разряду числа прибавляется единица. Например, округление восьмеричного числа 32,32471₈ до одного знака после запятой даст в результате 32,3; а округление до двух знаков после запятой — 32,33.

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

Применение двоичной системы счисления в ЭВМ может рассматриваться в двух аспектах: 1) двоичная нумерация; 2) двоичная арифметика, т. е. выполнение арифметических вычислений над двоичными числами. С двоичной нумерацией ученики встретятся в теме «Представление текста в компьютерной памяти». Рассказывая о таблице кодировки ASCII, учитель должен сообщить ученикам, что внутренний двоичный код символа — это его порядковый номер в двоичной системе счисления.

Практическая потребность знакомства с двоичной арифметиrой возникает при изучении работы процессора (см., например, [9, гл. 11]). В этой теме рассказывается, как процессор ЭВМ выполняет арифметические вычисления. Согласно принципу Дж. фон Неймана, компьютер производит вычисления в двоичной системе счисления. В рамках базового курса достаточно ограничиться рассмотрением вычислений с целыми двоичными числами.

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

0+0=0 0´0=0

1+0=1 1´0=0

1 + 1 = 10 1´1=1

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

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

0-0=0; 1-0 = 1; 10 - 1 = 1.

А вот пример вычитания многозначных чисел:

_ 1001101101

100110111

Полученный результат можно проверить сложением разности с вычитаемым. Должно получиться уменьшаемое число.

Деление — операция обратная умножению. В любой системе счисления делить на 0 нельзя. Результат деления на 1 равен делимому. Деление двоичного числа на 10₂ ведет к перемещению запятой на один разряд влево, подобно десятичному делению на десять. Например:

10010:10 = 1001; 1011:10 = 101,1; 101100:10 = 10110.

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

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

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

Таблица 8.1

Двоично-шестнадцатеричная таблица

 

		А
		В
		С
		D
		Е
		F

 

Такая связь основана на том, что 16 = 2⁴, и число различных 4-разрядных комбинаций из цифр 0 и 1 равно 16: от 0000 до 1111. Поэтому перевод чисел из «16» в «2» и обратно производится путем формальной перекодировки. Принято считать, что если дано шестнад-цатеричное представление внутренней информации, то это равносильно наличию двоичного представления. Преимущество шестнадцатеричного представления состоит в том, что оно в 4 раза короче двоичного. Желательно, чтобы ученики запомнили двоично-шестнад-цатеричную таблицу. Тогда действительно для них шестнадцатерич-ное представление станет эквивалентным двоичному.

В шестнадцатеричном виде записываются адреса оперативной памяти компьютера. Например, для учебного компьютера «Нейман» [9] диапазон адресации байтов памяти от 00 до FF. Значит, в десятичной системе — от 0 до 255. Рассматривая структуру памяти компьютера, принципы адресации байтов памяти, можно обсудить с учениками следующий вопрос: как связан диапазон адресов с разрядностью адреса. В учебном компьютере «Нейман» адреса памяти представляются 8-разрядными двоичными числами (2-разрядными шестнадцатеричными). Поэтому число различных адресов равно 2⁸, а диапазон значений — от 0 до 2⁸ — 1 = 255 (FF₁₆). Если адрес 16-разрядный, что часто имеет место для реальных ЭВМ, то размер адресуемой памяти равен 2¹⁶ байт = 2⁶ Кбайт = 64 Кбайт. Диапазон шестнадцатеричных адресов в таком случае: от 0000 до FFFF.

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

Массивы

 

Изучение структурированных типов начните с наиболее традиционного — массива. Подчеркните его групповые свойства: упорядоченная однородная статическая структура прямого доступа; приведите обоснование этих свойств.

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

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

 

Var A: array [1980..2000,1.. 15] of real

 

вместо альтернативного, явно отражающего фразу «массив массивов»:

 

Var A: array [1980.. 2000] of array [1.. 15] of real

 

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

Туре В = array [1980.. 2000,1.. 15] of real

Var А:В

 

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

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

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

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

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

Методические рекомендации по изучению темы

Изучаемые вопросы:

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

ª Математическая логика в базах данных.

ª Математическая логика в электронных таблицах.

ª Математическая логика в программировании.

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

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

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

«Лед — твердое состояние воды» — истинное высказывание.

«Треугольник, это геометрическая фигура» — истинное высказывание.

«Париж — столица Китая» — ложное высказывание.

6 < 5 — ложное высказывание.

Логические величины: понятия, выражаемые словами: ИСТИНА, ЛОЖЬ (true, false). Следовательно, истинность высказываний выражается через логические величины.

Логическая константа: ИСТИНА или ЛОЖЬ.

Логическая переменная: символически обозначенная логическая величина. Следовательно, если известно, что А, В, X, У и пр. — переменные логические величины, то это значит, что они могут принимать значения только ИСТИНА или ЛОЖЬ.

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

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

Конъюнкция (логическое умножение). В русском языке она выражается союзом И. В математической логике используются знаки & или Ù. Конъюнкция — двухместная операция; записывается в виде: А Ù В. Значение такого выражения будет ЛОЖЬ, если значение хотя бы одного из операндов ложно.

Дизъюнкция (логическое сложение). В русском языке этой связке соответствуют союз ИЛИ. В математической логике она обозначается знаком Ú. Дизъюнкция — двухместная операция; записывается в виде: A Ú В. Значение такого выражения будет ИСТИНА, если значение хотя бы одного из операндов истинно.

Отрицание. В русском языке этой связке соответствует частица НЕ (в некоторых высказываниях применяется оборот «неверно, что...»). Отрицание — унарная (одноместная) операция; записывается в виде: Ø А или А̅.

Логическая формула (логическое выражение) — формула, содержащая лишь логические величины и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА или ЛОЖЬ.

Пример 1. Рассмотрим сложное высказывание: «Число 6 делится на 2, и число 6 делится на 3». Представить данное высказывание в виде логической формулы.

Обозначим через А простое высказывание «число 6 делится на 2», а через В простое высказывание «число 6 делится на 3». Тогда соответствующая логическая формула имеет вид: А & В. Очевидно, ее значение — ИСТИНА.

Пример 2. Рассмотрим сложное высказывание: «Летом я поеду в деревню или в туристическую поездку».

Обозначим через А простое высказывание «летом я поеду в деревню», а через В — простое высказывание «летом я поеду в туристическую поездку». Тогда логическая форма сложного высказывания имеет вид A Ú В.

Пример 3. Рассмотрим высказывание: «Неверно, что 4 делится на 3».

Обозначим через А простое высказывание «4 делится на 3». Тогда логическая форма отрицания этого высказывания имеет вид Ø А.

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

Таблица 8.2

 

	А	В	Ø	А&В	AÚ В
	и	и	л	и	и
	и	л	л	л	и
	л	и	и	л	и
	л	л	и	л	л

 

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

Пример 4. Вычислить значение логической формулы:

не X и Y или Х и Z,

если логические переменные имеют следующие значения: X = = ЛОЖЬ, Y = ИСТИНА, Z = ИСТИНА.

Отметим цифрами сверху порядок выполнения операций в выражении:

1243 не X и Y или X и Z.

Используя таблицу истинности, вычислим формулу по шагам:

1) не ЛОЖЬ = ИСТИНА;

2) ИСТИНА и ИСТИНА = ИСТИНА;

3) ЛОЖЬ и ИСТИНА = ЛОЖЬ;

4) ИСТИНА или ЛОЖЬ = ИСТИНА. Ответ: ИСТИНА.