середу, 18 квітня 2012 р.

Каким быть курсу информатики?..

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

   Примечание: отсутствующие рисунки рисуются и будут добавлены.
====

- А на той планете есть охотники?
- Нет.
- Как интересно! А куры там есть?
- Нет.
- Нет в мире совершенства! – вздохнул лис.
Антуан де Сент-Экзюпери,
«Маленький принц»

Взгляд на информатику как на предмет в общеобразовательной школе за немногим более чем двадцатилетнее развитие обладал некоей «аномальной» изменчивостью. С одной стороны, это ситуация обусловлена объективными причинами (динамичность развития данной области действительности и т. д.), а с другой – все ли ладно в нашем «Датском королевстве»? Попробуем как бы забыть на время обо всех существующих концепциях, позициях, учебниках и т. д. и, опираясь только на более чем тридцатилетний опыт работы как в разработке реальных систем обработки информации, так и в образовательной информатике, сформулировать точку зрения прагматика.
             Зададим себе первый наивный вопрос – «что такое информатика»? Оказывается, что дать простой и  ясный ответ на него не очень просто! Такие области, как, например, математика или физика, имеют достаточно четкие границы, а информатика? Конечно, допустимо сказать: это – что-то связанное с информационными процессами, с обработкой информации и т. д., но тогда одно понятие будет определяться через другие, образуется длинна понятийная цепочка, часто – тавтологическая, и прагматику не очень ясно, где начало и где конец этого понятийного многообразия.
            Упростим (или умножим?) первоначальный вопрос: «Возможна ли информатика без компьютера»? Если ответить «да», то границы этой области становятся еще более неопределенными, понятие «информатика» переходит в разряд «сверхоткрытых», и впору задать вопрос – «а что не есть информатика»? Но предположим, что мы ответили «нет». В этом случае  нас уже появляется граница, пусть пока только «пунктирная». Но появляется и новое понятие – «компьютер», и ту же возникают вопросы как минимум о взаимосвязи и о том, что есть компьютер – объект изучения в информатике или средство (инструмент)  изучения информатики?
            Определимся с условными границами понятия «компьютер». Самый низший уровень – это «железо» (hardware). Безусловно, понимание того, как функционирует аппаратное обеспечение, необходимо. Хорошо, например, знание того, что для реализации всех возможностей этого уровня компьютеру достаточно уметь выполнять только операции инверсии сдвига на один разряд и прибавления единицы а все остальные операции конструируются из этих примитивов. Но полезность компьютера при таком ограничении меньше, чем у молотка: последним хотя бы можно гвозди забивать.  Таким образом, в понятие «компьютер» следует вложить как минимум операционную систему( ее основные  и функциональные возможности и структуру) и простейшую систему программирования после этого компьютер уже выполняет свое основное предназначение – вычисляет и перебирает, т. е. происходит то чудесное «оживление», которое делает компьютер универсальным устройством, универсальным вычислителем и переборщиком вариантов.
            Итак, граница очерчена и просматривается, в каком объеме (хотя бы минимальном), компьютер является объектом изучения. А что дальше? дальше у нас два пути. Первый – расширяя понятие «компьютер», добавляя к нему уже некий готовый функционал (например, графический редактор), мы можем изучать его и утверждать, что изучается информатика – редакторы же связаны с компьютером! Второй путь – ответить на вопрос, что произошло в цепочке от потребности человека рисовать к появлению у компьютера такого функционала, удовлетворяющего эту потребность.
            Оставим на время второй путь и закончим рассуждения о нашем понимании компьютера. Повторим мысль, что возможности компьютера ограничены. Простейший пример (чуть- чуть абсурдный): любой из нас, если потребуется, выполнит вычисления  101000, просто записывая соответствующее количество нулей, а вот  компьютер (без специальных ухищрений) этого не сделает!  Естественно, что возможности компьютера увеличиваются со временем  - сравним хотя бы компьютеры двадцатилетней давности и нынешнее. Расширение возможностей позволяет решать все новые проблемы и совершенствовать решение старых, но ограниченность компьютера остается.
            Однако вернемся к нашим рассуждениям об информатике и продолжим их с помощью примера. Человек и до появления компьютера работал с текстом. В зависимости от вида его деятельности, эта работа была различной (писатель, редактор и т. д.). Другими словами, есть потребность работы с текстом, и есть проблемы работы с текстом. С появлением компьютера человек «углядел», что последний может быть полезен для удовлетворения этой потребности, и разработал в начале простейший текстовый редактор, а затем текстовый процессор с огромным (если сравнить с первыми версиями) возможностями. Отметим, что в данном случае (как и в других) совершенство инструмента, а текстовый процессор является именно инструментом, оказывает обратное влияние на процесс работы с текстом (обратная связь). Но не это главное, а продолжение нашего наивного вопроса – «где здесь информатика»?
            Итак, в самом общем виде (см. рис. 1) есть действительность, если проблемы этой действительности и есть отображение этих проблем в некие их решения, использующие компьютер, в результате чего получаются некие продукты (причем так называемые «новые информационные технологии» - это лишь небольшая часть этих продуктов), удовлетворяющие потребностям этой действительности.
          Примеры можно продолжить. Вот еще один из них для наглядности, связанный, в частности, с обработкой текстов. В молекулярной биологии и в других областях знаний существует проблема поиска в больших объемах текстовых данных входящих в них образцов. Прообразом этой проблемы является элементарная задача поиска слов в тексте. Постоянное наращивания возможностей уровня В не решало запросы действительности. И поэтому в последние 30 лет сформировался новый подраздел информатики – «методы обработки строк».
         Вернемся к первоначальному вопросу. Информатика – это уровни А, В, С или  А и В? (Мы оставляем только самые логические и разумные сочетания.) Отметим, что при положительном ответе на вопрос о взаимосвязи информатики и  компьютера («возможна ли информатика без компьютера») в нашей схеме, а она применима не только к информатике, появляется еще один трудно определимый «прямоугольник».
        Далее можно было бы рассуждать следующим образом. Можно взять образовательный стандарт школьного  курса, соотнести его положения с приведенной схемой, а затем на основе некого анализа  с учетом привнесенных извне положений сделать определенные выводы и ответить на поставленный вопрос. Очевидно, что в зависимости от этих «привнесенных извне положений» могут получится различные результаты – вплоть до того, что мы рассуждаем вовсе не о том, или до появления некой «новой информатики» (например, «асоциальной»). Но мы попробуем пойти другим путем – спроецируем ситуацию на высшую школу, поймем, как отвечают на поставленный вопрос в ней, и сделаем «обратную проекцию» на общеобразовательную школу. (Такие операции «проецирования», как прямого, так и обратного, не приводят к искажению предмета анализа, ибо речь идет об одном и том же, просто в разных объемах).
      Область высшей школы также поражает своим многообразием направленности подготовки специалистов по информатике, но имеет более определенные границы. Вычленим три основополагающих российских образовательных стандарта.
      Специальность 010200 – «Прикладная математика и информатика», квалификация математик, системный программист. Естественно, что здесь осуществляется фундаментальная подготовка по математике. В блоке общеобразовательных дисциплин информатика представлена здесь курсами «Языки программирования и методы трансляции», «Системное и прикладное программное обеспечение» и «Базы данных и экспертные системы». Остальные составляющие подготовки зависят от выбранной в вузе специализации, но в основном, если последняя связана с информатикой, рассматриваются вопросы программирования и функционирования операционных систем (см. рис. 1), это уровни А и В, причем уровень А трактуется чисто с математических позиций. Согласно логике стандарта, подготовка по математике обеспечивает реализацию отображения А, с чем, конечно, трудно согласится. Математическая составляющая в А, безусловно, есть, в некоторых проблемах она имеет принципиальное значение, но сведение методов решения проблем только к ней не соответствует реальному состоянию дел. И здесь в информатике имеет место парадоксальная ситуация, образно характеризуем фразой «сапожник без сапог». Специалисты по информатике создают системы обработки информации различного назначения, в частности автоматизирующие разные виды деятельности, но собственная деятельность по отображению проблемы в некий программный продукт (уровень А) соответствующей поддержки практически не имеет! Структурное, объектно-ориентированное проектирование, а также технологии типа CASE (Computer Aided Software Engineering) или RAD (Rapid Application Development) лишь частично решают эту проблему, причем последние относят скорее к уровню С, а не А. Естественно, что эта части проблематики уровня А слабо представлена в образовательных стандартах или вообще никоим образом там не затрагивается.
      Специальность 351400 – «Прикладная информатика(по областям)», квалификация – информатик (квалификация в области). Для определенности будем считать такой областью экономику (самый распространенный вариант). Общеобразовательный блок здесь представлен стандартным набором курсов: вычислительные системы, сети и телекоммуникации; информационные системы; базы данных; высокоуровневые методы информатики и программирования; операционные системы, среды и оболочки; информационные технологии. К специальным дисциплинам относятся проектирование информационных систем; интеллектуальные информационные системы; информационная безопасность, а также информационные системы в бухгалтерском учете и аудите, в банковском деле и т.д. Итого, в данном стандарте четко представлен уровень В (его программная составляющая) и та часть уровня С, которая относится к выбранной отрасли. Уровень А дается скорее в технологическом плане, связанном с общими вопросами проектирования информационных систем.
Специальность 654600 – «Информатика и вычислительная техника», квалификация – инженер. Общеобразовательный блок здесь с точностью до деталей совпадает с аналогичным блоком предыдущей специальности, а в специальных дисциплинах (в зависимости от специализации) более детально представлен уровень В, например курсами «Теория вычислительных процессов», «Архитектура вычислительных систем» и т.д. Уровень А отождествляется с программированием.
С некоторыми оговорками можно считать, что подготовка специалистов по уровню А осуществляется в рамках специальности «Прикладная математика и информатика» (Квалификация выпускника – математик, системный программист), по уровню В «Информатика и вычислительная техника» (квалификация выпускника – инженер), со уровню С  - «Прикладная информатика (по отраслям)» (квалификация выпускника – например, информатик-экономист).
Итак, если уровни В и С достаточно четко очерчиваются, то с уровнем А все обстоит несколько сложнее. Так или иначе, в нем присутствует то, что обозначает понятие «программирование». Но само по себе программирование как знание систем программирования и умения что-то на них записывать, пусть даже в формализованном виде, не решает проблемы отображения А (см. рис. 1), как не решает ее и чисто математическое составляющая подготовки!
Приведем примеры в подкрепление точки зрения «за» и «против». Новый раздел информатики – методы обработки строк, имеющий огромное значение для многочисленных приложений. Его математическая составляющая минимальна. Другой раздел – методы защиты информации, где без знания математики не достигается даже первичные понимание сути пионерской работы У. Диффи и М.Э. Хеллмана. Но и в том, и в другом случае ключом является понятие «алгоритм» и нечто (вспомним ситуацию «сапожник без сапог»), что мы условно обозначим как искусство перевода и решения проблемы (заметим – оно не сводится к алгоритму!) на язык, понятный на уровне В.
Подведем определенную черту под вышеизложенным. Уровни В и С четко прописываются в стандартах, чего не скажешь об уровне А: общепринятого понятия уровня А нет, а  различной его трактовке опираются на не очень понятную аксиоматику. Использованные же нами понятия «искусство» - вынужденное. Человек, когда его не удовлетворяет определенный язык как инструмент формализации, создает некий «метаязык». Но в данном случае все попытки создания его в информатике трудно считать успешными, и популярное в настоящее время объектно-ориентированное проектирование вряд ли в полном объеме решает проблему.
А в школе, в школьном образовании, дается попытка интеграции уровней в единое целое в рамках ограниченного времени на изучение. И естественно, возникает вопрос – возможно ли решение данной проблемы? Как собрать в малом (по времени) большое, и не просто большое, а постоянно растущее, особенно на уровне С, целое?
Помимо теоретической возможности такой интеграции, есть еще один вопрос – а надо ли это делать? Если следовать логике одного из государственных мужей, утверждающего, что основной задачей школы является «подготовка грамотного пользователя технологий» (естественно, с приставкой – «новых информационных»), то, конечно, «да», - и основной акцент должен быть сделан на уровне С. Кстати, изучение уровня С имеет еще одну особенность, которою просто необходимо отменить. Научно доказано что существующие методики изучения уровня С (во всяком случаи те, которые представлены в современных школьных учебниках) не развивают или очень слабо развивают интеллектуальный потенциал школьника. (Мы не говорим, что не учат, но это несколько разные срезы явления.)   Сумма запоминаемого фактографического материала огромна, также как и навыки манипулирования мышью. Но ведь святая святых образования – это развитие школьника, развитие его умственных способностей и возможностей, позволяющих решать любую встречающуюся проблему, опираясь не только на чувственный аппарат, данный человеку, но используя мощь всего аналитического аппарата ума, который формируется  у человека, в частности, в процессе его обучения. Доказательная база «греховности» традиционных методик изучения информационных технологий предельно проста. Вот одна из возможных схем такого доказательства. Есть, например, теория поэтапного развития умственных способностей школьника одного из ведущих психологов и педагогов ХХ столетия, Петра Яковлевича Гальперина. Опуская многое (что естественно для данного материала), зафиксируем «итого», т.е. главное. Непременным условием умственного развития школьника является определенная познавательная деятельность (вообще говоря, слово «познавательная» можно опустить), включающая в себя действия, классифицируемые как исполнительские, ориентировочные и контрольные. Не будем раскрывать их, ибо это только отяготит текст, но не пояснить текст доказательства. Упрощая, скажем, что в развитии умственных способностей ключевую роль играет преобладание и синтез именно действий второго и третьего типов, и зафиксируем этот момент как некий «узелок» нашего понимания проблемы. Таким образом, выстраиваются необходимые условия развития. А затем мы «расчленяем» методику изучения информационных технологий школьных учебников до уровня конкретных действий – тех, которые должен выполнить школьник, - и сопоставляем (устанавливаем соответствие) их с действиями по П.Я.Гальперину. Если оказывается, что большинство действий относится к первому типу, а не второму и третьему, как необходимо, то доказательство завершено (необходимые условия не выполнены), а мы получаем обучение в соответствии с «принципом банана» (известный образ по выработке условного рефлекса у обезьян по доставанию банана)…
В заключение необходимо вспомнить об огромной ответственности современного общества перед детьми за их будущее. Любое движение цивилизации кроме позитивной несет в себе и негативную составляющую. Компьютер – это хорошо или плохо для образования, для развития школьника? Современный школьник не знает таблицу умножения – зачем, если есть калькулятор? Так в чем же заключающая негативная составляющая компьютера (а она обязательно есть)? Любому педагогу, связанному с информатикой, приходилось (и, вероятно, не один раз) отвечать на вопрос родителей : «Мы купили ребенку компьютер в надежде на то, что он повлияет на его развитие, а ребенок день и ночь играет – что делать»? Приведем почти абсурдный пример из другой области, чтобы пояснить эту мысль. Потребность человека убивать себе подобных хорошо известна. Человек придумал атомную бомбу, чтобы эффектно убивать. Предположим, что она стала предметом общего пользования. Что тогда произойдет – предсказать нетрудно. А что убьет компьютер? Компьютер – при его бездумном использовании – убьет в человеке его творческое начало и сделает из него нечто как начинающееся, так заканчивающееся примитивным потреблением кем-то созданных услуг! И пусть это несколько гипертрофированное утверждение, но это лучше, чем очередная эйфория, связанная с всеобщей компьютеризацией…

неділю, 8 квітня 2012 р.

Битовые операции

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

Часть I. Базовые битовые операции

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

Операнды
побитовое
И
побитовое ИЛИ
побитовое исключающее ИЛИ
A
B
&
|
^
0
0
0
0
0
0
1
0
1
1
1
0
0
1
1
1
1
1
1
0
   Рассмотрим эти, а также некоторые другие операции и их использование более детально.
   §1.1 Сдвиг влево и сдвиг вправо (<< SHIFT LEFT, >> SHIFT RIGHT). Основная функция операций сдвиг влево (<< SHIFT LEFT) и сдвиг вправо (>> SHIFT RIGHT) - это сдвиг целочисельной переменной на указанное количество бит влево (или вправо), при этом старшие (или младшие) биты "исчезают", т.е. приобретают новые значения, старые значения при этом не сохраняются. Примеры:

Исходное
десятичное
число
Двоичное
представление
Операция
Новое
двоичное
представление
Новое
десятичное
значение
5 00000101 5 << 1 00001010 10
5 00000101 5 << 2 00010100 20
5 00000101 5 >> 1 00000010 2
5 00000101 5 >> 2 00000001 1
   Компьютерные поразрядные вычисления (битовые операции) выполняются быстрее арифметических, поэтому многие профессиональные программисты используют функции битового сдвига для замены операций деления нацело на 2 и умножения на 2. Преимущество такого использования проявляется в повышении эффективности выполнения программы, недостатком является более низкая читаемость подобного кода. Приведём пример подобного использования деления нацело на 2:
...
int n = 5;
n = n >> 1;
  // значение n = n/2
/ * Эту же формулу можно записать в виде n >> = 1 или n /= 2 */
...
   §1.2 Побитовое И (& AND). Это функция побитового сравнения двух целочисельных переменных, устанавливающая в новой переменной биты в состояние 1 только в том случае, если они оба равны 1 в исходных переменных.


Двоичное представление Десятичне значение
x
00000000000000000000000001110100
116
y
00000000000000000000000000101001
41
x & y
00000000000000000000000000100000
32
   Примером использования является подсчёт битов в заданном числе.

Первый способ Второй способ
...
int count_bit_1(int n)
{

 // считаем слева направо удаляя правый бит
    int c = 0;
    for (int i=0; i<32; ++i)  // int - 32-битная переменная
        if (n & (1 << i))
            c++;
    return c;
}
...
...
int count_bit_1(int n)
{
// то же,  но удаляя левый бит
    int c = 0;
    for (; n; n>>=1)
        if (n & 1)
            c++;
    return c;
}
...

   §1.3 Побитовое ИЛИ (| OR). Это функция побитового сравнения двух целочисельных переменных, устанавливающая в новой переменной биты в состояние 1 только в том случае, если хотя бы один из них равен 1 в исходных переменных.


Двоичное представление Десятичне значение
x
00000000000000000000000001110100
116
y
00000000000000000000000000101001
41
x | y
00000000000000000000000001111101
125
   Пример применения: установить 5-й бит в числе раным 1:
...
int mark_5th_bit(int n)
{
    return n | (1 << 4);
}
...
   §1.4 Побитовое исключительное ИЛИ (^ XOR). Это функция побитового сравнения двух целочисельных переменных, устанавливающая в новой переменной биты в состояние 1 только в том случае, если в одной и только в одной из исходных переменных один из рассматриваемых двух битов равен 1.


Двоичное представление Десятичне значение
x
00000000000000000000000001110100
116
y
00000000000000000000000000101001
41
x ^ y
00000000000000000000000001011101
93
   Пример применения: инвертировать 5-й бит в заданном числе:
...
int reverse_5th_bit(int n)
{
    return n ^ (1 << 4);
}
...
   §1.5 Побитовое инвертирование (~ NOT). Это функция побитового инвертирования целочисельной переменной, меняющая значение битов на обратные (0 на 1, а 1 на 0).


Двоичное представление Десятичне значение
x
00000000000000000000000000000011
3
~x
11111111111111111111111111111100
-4
   Следует отметить, что эту функцию можно применять и в других целях. Например, если в задаче нужно прочесть некоторое наперёд неизвестное количество целочисельных переменных, то это можно организовать так:

while(~scanf("%d",&n))
{
    …
}

Часть II. Битовые трюки

   §2.1 Манипуляции с младшими битами. Приведённые здесь формулы можно с успехом использовать для ускорения работы многих программ.
   Для того, чтобы обнулить крайний справа единичный бит (01011000=>01010000), использутся формула
x&(x-1)
   Эту формулу можно применять для проверки того, является ли беззнаковое целое степенью 2 (путём проверки результата вычислений на равенство 0).

   Обмен значений 2-х целочисельных переменных:

Первый способ Второй способ

void swap(int& x, int& y)
{
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
}
 

void swap(int& x, int& y)
{
    x ^= y ^= x ^= y;
}


   Проверка, является ли число степенью двойки:


bool ispow2(int n)
{
    return (n & -n) == n;
}
   Увеличить (уменьшить) целочисельную переменную на единицу:

Увеличить на 1 Уменьшить на 1

void add_one(int& x)
{
    return -~x; // ++x
}
… 

void sub_one(int& x)
{
    return ~-x; // --x
}
   Замена целого на противоположное:

Первый способ Второй способ

void negative(int& x)
{
    return ~x + 1;          // -x;
}
… 

void negative(int& x)
{
    return (x ^ -1) + 1;    // -x;
}
   Проверка целого на чётность (нечётность):


bool even_or_odd(int& x)
{
    return x & 1;   // x % 2;
}
   Вычисление остатка от деления на степень двойки:


int mod(int& x, int& m) // 
m должно быть степенью двойки
{
    return x & (m - 1); // 
x % m;
}
   Вычисление абсолютного значения целого числа:


int abs(int& x)
{
    
// x < 0 ? -x : x;
    return (x ^ (x >> 31)) - (x >> 31);
}
  Вычисление квадратного корня из обратного числа, т.е. для заданного целого n найти квадратный корень от 1/n:


// 1.0 / sqrt(x)
float InvSqrt(float x)
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);
    x = *(float*)&i;
    x = x*(1.5f-xhalf*x*x);
    return x;
}
   Подсчёт количества значущих бит в 32-битном целом:

...
int count_bits(int& x)
{
        x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
        x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
        x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
        x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
        x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
        return x;
}
...
  В 32-битном целом поменять порядок битов на обратный:


int reverse_bits(int& x)
{
    x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
    x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
    x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
    x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
    x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
    return x;
}



 (Продолжение следует...)