Обосновано понятие «развивающая задача», с теоретической точки зрения, используемая учителями информатики в профильном школьном курсе информатики. Приведены примеры развивающих задач из разных разделов информатики, рассмотрены комплексы задач разного уровня сложности, стимулирующие неординарность и развитие мышления.
Ключевые слова: развивающая задача, профильное обучение.
Современное информационное общество задаёт темпы развития нашего социума, в обществе востребованы грамотные, образованные, информированные, целеустремленные граждане. Образование нацелено на качественное обучение детей, которое должно соответствовать новым образовательным стандартам. Профильное обучение информатике ставит перед учителем и учеником следующие планки:
освоение и систематизация знаний, относящихся к математическим объектам информатики; построению описаний объектов и процессов, позволяющих осуществлять их компьютерное моделирование; средствам моделирования; информационным процессам в биологических, технологических и социальных системах;
овладение умениями строить математические объекты информатики, в том числе логические формулы и программы на формальном языке, удовлетворяющие заданному описанию; создавать программы на языке программирования по их описанию; использовать общепользовательские инструменты и настраивать их для нужд пользователя;
развитие алгоритмического мышления, способностей к формализации, элементов системного мышления;
воспитание чувства ответственности за результаты своего труда; формирование установки на позитивную социальную деятельность в информационном обществе, на недопустимость действий, нарушающих правовые, этические нормы работы с информацией;
приобретение опыта проектной деятельности, создания, редактирования, оформления, сохранения, передачи информационных объектов различного типа с помощью современных программных средств; построения компьютерных моделей, коллективной реализации информационных проектов, информационной деятельности в различных сферах, востребованных на рынке труда.
Для реализации поставленных задач в полной мере подходит использование развивающих задач из предметной области. Но прежде, чем углубиться в практическую значимость развивающих задач необходимо определиться с теоретическим значением, с понятием «развивающая задача». Термин «развивающая задача» многие подменяют разными омонимами, кто-то называет её учебной задачей, другие — проблемной. Что же такое «развивающая задача»?
Развитие — это процесс изменения, перехода от старого к новому, более совершенному; от простого к сложному; от низшего к высшему.
Развитие — степень сознательности, просвещенности, умственной и духовной зрелости, культурности.
Развитие — развёртывание. Постепенное проявление всех возможностей, с самого начала заложенных в зародыш.
Развитие — приобретение новых способностей, знаний, умений, навыков.
Развитие — процесс, связанный с наращиванием сознательного усилия, которое определяет не только возможность или невозможность нахождения на пути познания, но и оперирование им. Развитие может считаться таковым, только если познан алгоритм совершенствования, который является не только следствием развития, но и его фактором. Сознательное управление процессом не только совершенствует сам процесс — им совершенствуется и самосознание.
Развитие — это условие, которое не может иметь предела.
Задача — это есть цель, данная в определённых условиях (согласно Леонтьеву А. Н.). Современному учителю информатики необходимо не только правильно выставлять цель перед учениками, но и грамотно, можно даже сказать искусно, создавать условия для достижения учащимися поставленной цели, для возникновения непреодолимого желания двигаться к этой цели. Движение есть жизнь или развитие.
Развивающая задача — это цель, данная в определенных условиях, которые не имеют предела.
Рис. 1. Развивающая задача (начало решения)
Рис. 2. Развивающая задача (задача решена)
Решая развивающие задачи, ученик движется по пути известного философа, который сказал: «Я знаю только то, что ничего не знаю» (Сократ, 477–399 г.г. до н. э.). Решение одной задачи становится целью для другой, обрастая новыми условиями — вопросами. Рассмотрим развивающие задачи из разных разделов информатики:
1. Информация: кодирование, шифрование, измерение. Информационно–логические задачи. Задачи с решениями.
1.1 Возможна ли ЭВМ с быстродействием 1020 операций в секунду? Ответ подтвердить убедительными вычислениями.
Решение. Самая большая скорость переноса электронов ≈ скорость света в вакууме v=3╢1010 см/сек. При выполнении одной операции свет (электрон) должен пройти расстояние не меньшее диаметра атома водорода s=10≈8 см. Время этого пути равно:
t = s/v = 10≈8 см/(3╢1010 см/сек) = 10≈18 /3 сек.
Следовательно, в идеальном варианте (если вообще удастся технически это когда–то реализовать) быстродействие компьютеров на принципах переноса электронов, не может превышать 3╢1018 операций в секунду.
1.2. Привести пример лексикографически упорядоченной, а также неупорядоченной последовательностей. Добавьте слова, изменяющие упорядоченность (неупорядоченность), если это возможно.
Решение. Слова «арбуз», «банан», «киви», «лимон», «тыква» ≈ лексикографически упорядочены по входному алфавиту русского языка. Добавляемое в конце слово — «яблоко». Слова двоичного алфавита "101", "011", "010", "000" лексикографически неупорядочены. Добавить (вставить) слова упорядочивающие слова ≈ невозможно (почему?).
1.3. Описать словесно и математически закон формирования чисел данного ряда (начиная с третьего): 1, 1, 2, 5, 29, 866,....
Решение. Нетрудно заметить, что начальный отрезок похож на ряд Фибоначчи, но это обманчиво. На самом деле, каждый член ряда (с третьего) получается не сложением двух предыдущих, а сложением их квадратов. Математически это записывается в виде:
xn = (xn≈1) 2 + (xn≈2)2, n=3, 4,....
1.4 Найти систему кодировки (т. е. правило шифровки) текста, если текст «АРГУМЕНТФУНКЦИИ» зашифрован с помощью этого кода как «БСДФНЖОУХФОЛЧКК».
Решение. Сравнивая число символов исходного и зашифрованного текста (они равны) и символы, стоящие на одинаковых местах в исходном и шифрованном тексте, замечаем, что этот текст закодирован кодом Цезаря: каждый символ алфавита (любого выбранного множества символов) кодируется следующим за ним по порядку (определенном в алфавите) символом, причем последний символ кодируется первым символом алфавита т. е. алфавит «закольцован».
1.5 С некоторой планеты поступают импульсы. Отождествив один импульс с полубайтом, получаем последовательность сообщений вида:
X [1]=000100001001010101100001,
X [2]=00010001000010010101010101100001,
X [3]=0001000100010000100101010101010101100001 и т. д.
Выдвинута гипотеза: если сообщения X [i], i=1,2,3,... подчиняются некоторому простому закону, то на планете живут разумные существа. Разумные ли существа живут на планете?
Решение. Переводя полубайты в десятичную систему, получаем сообщения вида:
X [1]=109561, X [2]=11095561, X [3]=1110955561,....
Нетрудно видеть, что X [n] = 111...11109555...55561. (n единиц n пятерок). Представим его в виде:
X [n]=11...1´ 10 n+4+9´ 10 n+2+55...5´ 10 2 +61=(10 n≈1)/9´ 10 n+4+9´ 10 n+2+ +5(10 n≈1)10 2/9+61=(10 2n+4≈14´ 10 n+2+49)/9= [(10 n+2≈7)/3] 2.
Следовательно, последовательность сообщений подчиняется закону:
X [1]=3312, X [2]=33312, X [3]=333312,.... Вывод: на планете живут разумные существа.
2. Системы счисления (задачи с решениями)
2.1. Вычислить наибольшее и наименьшее 5–разрядное целое число в системе счисления с основанием 4.
Решение. Наибольшее целое n–разрядное число, которое возможно записать в системе счисления с основанием р, очевидно, равно:
Наименьшее целое n — разрядное число в этой системе равно xmin = ≈ xmax = 1 ≈ рn. Таким образом, в системе счисления с основанием 4 и числом разрядов 5 представим диапазон следующих чисел:
≈ 1023 =1 ≈ 45 £ (x)4 £ 45 ≈ 1 = 1023.
Этим формулам можно придать более компактный вид с использованием комбинаторики (или добавляя и затем отнимая 1). Например, для двоичной системы
a = 1 1 1... 1 1 12 = (2n ≈ 1)10, b = (1 ≈ 2n)10, n разрядов
а в восьмеричной системе счисления эти числа определяются в виде:
а = 7 7 7... 7 7 78 = (8n ≈ 1)10, b = (1 ≈ 8n)10. n разрядов
2.2. Привести основные общие (различные) стороны множества чисел (–1;1) в обычной и машинной n–разрядной алгебре (арифметике).
Решение. С точки зрения обычной арифметики в интервале (–1;1) имеется бесконечное множество «плотно» расположенных точек, причем в любой окрестности каждой такой точки имеется хотя бы одна точка из этого множества. Такую арифметику называют часто регулярной арифметикой. Машинная арифметика имеет следующие особенности. Она нерегулярна — точки интервала сгущаются около нуля; кроме того, в этом интервале точка х «изолирована» — если взять её любую окрестность (х–а; х+а), где а — число, которое не превосходит машинный нуль, то в этом интервале нет других точек (отличных от х). Есть и другие особенности этих множеств (связанные с выполнением операций, например), но указанные особенности– основные.
2.3. Что такое числа (арифметика) с плавающей запятой, какие неудобства чисел с ограниченной разрядностью можно указать?
Решение. Эта форма представления чисел была предложена в 1937 году Конрадом Цузе для увеличения диапазона чисел, представимых в арифметике двоичных чисел, а также для повышения точности этого представления чисел. Например, в 16–разрядной арифметике двоичных чисел можно представить диапазон целых х (старший разряд — под знак числа): 1 ≈ 215 < x < 215 ≈ 1.
Если же в этой арифметике (не меняя её разрядность) отвести 7 разрядов под мантиссу, а 7 разрядов — под порядок, то уже представим диапазон чисел: ≈ 127´ 2127 < x < 127´ 2127 (два разряда — под знак числа и знак порядка; несколько упрощена и общая картина представления — для наглядности).
К «неудобствам» этой формы представления чисел можно отнести возможность возникновения следующих «особо опасных» ситуации:
а) если число достаточно мало, например, а=0.12Е+00, то оно может быть представлено любым числом из наименьшего интервала включающего а, в частности, числом 0.120000001 или 0.199999999 и в этом случае сравнивать на равенство «в лоб» нельзя;
б) порядок выполнения операций может влиять на результат, например, в четырехразрядной арифметике с фиксированной запятой имеем:
20.0000+0.0001=20.0001, но при этом
0.2000Е+02+0.1000Е–05=0.2000Е+02;
в) может возникнуть так называемая ситуация «переполнения порядка» при сложении (умножении) очень больших чисел или «исчезновения порядка» при сложении (умножении) «очень малых чисел», например,
0.6000Е+39´ 0.1200Е+64=0.9999Е+99 (или неопределенно),
0.6000Е≈35´ 0.0200Е≈65=0.9999Е≈99 (или неопределенно)
при соответствующим образом определенной разрядности десятичной арифметики.
2.4. Выяснить, в какой системе счисления было выполнено сложение, где * обозначены неизвестные числа (возможно, разные), т. е. найти основание системы счисления р:
(33*5*)p + (1*643)p = (52424)p.
Решение. Так как во втором разряде (5+4) получается число меньшее 9, то основание системы будет меньше 9, а так как в третьем разряде (*+6) есть цифра 6 (определенная только в системах счисления с р³ 7), то 7£ р£ 8. Из второго разряда (5+4=2) следует, что был перенос в старший разряд единицы основания, т. е. 5+4≈р=2 или p=7.
2.5. В саду 100 фруктовых деревьев — 14 яблонь и 42 груши. В какой системе счисления посчитаны деревья?
Решение. Из условия задачи и переводом указанных чисел в систему счисления с пока неизвестным основанием р можно записать равенство:
1´ р2 + 0´ р1 + 0 = 1´ р1 + 4 + 4´ р1 + 2
или р2≈5р≈6=0. Из корней этого уравнения подходит в качестве основания системы только один — р=6. Деревья посчитаны в 6–ной системе счисления.
3. Алгоритмы и алгоритмизация (Задачи с решениями)
3.1 Формализовать (записать алгоритм) сложения двух целых положительных чисел и оценить число операций алгоритма.
Решение. Пусть числа заданы своими разрядами в виде: a=anan–1...a1a0, b=bmbm–1...b1b0, где ai и bj ≈ i–ый и j–ый разряды этих чисел. Разряды нумеруются справа налево. Алгоритм состоит из следующих пунктов:
1) Найти k — минимальное из n и m т. е. выполнить операцию k:=min(n,m).
2) Положить i=0 (т. е. выбрать младший разряд у складываемых чисел).
3) Если ai+bi<10, то в i–ый разряд формируемой суммы c=a+b записать цифру ci=ai+bi, в противном случае — записать цифру суммы ci=ai+bi≈10.
4) Увеличить следующий, (i+1)– ый разряд числа a на 1 (ai+1:=ai+1+1).
5) Если i³ k, то проверить, был ли перенос в предыдущем пункте 3 (в разряде i≈1) и, если он был, то в следующем разряде суммы записать цифру ci=ai+1, а все остальные разряды сj положить равными аj, j=i+2, i+3,..., n (при k=m) или записать цифру ci=ci+1, а все остальные разряды cj положить равными bj, j=i+2, i+3,..., m (при k=n); если же i<k, то перейти к п.7.
6) Заменить текущее i на i+1 (i:=i+1) и перейти к п.3.
7) Записать сумму: c=cncn–1...c0 (или же c=cn+1cn...c0) — при k=m, или c=cmcm–1...c0 (или же c=cm+1cm...c0) — при k=n. Интересен этот пример и тем, что обычно и интуитивно просто исполняемая нами процедура оказалась не очень простой при её формализации (здесь полную формализацию, т. е. запись процедуры на формальном языке, например, на учебном алгоритмическом мы не провели — оставляем это как упражнение для читателя).
3.2. Составить алгоритм выделения знака и всех цифр заданного натурального n–разрядного числа х. Цифры выдавать пользователю с младшего разряда. Составить достаточный на ваш взгляд набор тестов. Указать число, функцию, выражение или способ для оценки эффективности этого алгоритма. Как можно решить эту задачу, если n не задается? Изменится ли сложность алгоритма по выбранной вами оценке или оценкам при этом и почему?
Решение. Алгоритм имеет вид:
алг Выделение цифр (арг цел n, х);
дано | натуральное n–разрядное число х, которое может быть | записано в виде, например, своими цифрами: х=х [1]x [2]...x [n]
надо | выделить и вывести по мере выделения все цифры этого числа
нач | начало тела алгоритма
цел i, | переменная цикла выделения (номер выделяемой цифры)
х, | заданное число
у | выделенная очередная цифра
если x>0 | число положительно (можно и через sign(x))?
то вывод («знак числа: + ") | да, положительно
иначе | остальные случаи
если x=0 | число равно нулю?
то вывод («число 0") | да, это нуль
иначе вывод («знак числа: — ") | нет, отрицательно
все | закончили с неположительными числами
все | закончили со всеми числами
нц для i от 1 до n | заголовок цикла для выделения цифр
y:=mod(x,10) | выделяем последнюю цифру текущего
| значения числа х (оно по ходу будет изменяться так, как это указано ниже)
вывод (у) | выдача очередной цифры числа
x:=div(x,10) | заменяем х числом, получаемым из х «отбрасыванием» последней цифры: | она была уже выше найдена
кц | конец тела цикла выделения цифр
кон | конец тела алгоритма.
Набор тестов должен включать, как минимум, тесты типа:
а) все разряды числа х — равны (в том числе и нулю);
б) среди разрядов есть равные между собой (в том числе и идущие последовательно);
в) случай n=1.
Функцию эффективности можно строить исходя из различных критериев эффективности, например, из числа операций, операндов, команд и т. д. В частности, показателем эффективности может служить простая интегральная оценка вида:
1) операций присваивания — 3n (2 явные операции в теле и одна неявная — в заголовке цикла и они повторяются n раз);
2) операций проверки простых предикатов — n+2 (в заголовке цикла, неявно, — n и явно в условных командах — 2);
3) вычислений функций — 2n;
4) логическая сложность, например, оцениваемая по глубине вложения циклов (равна 1) и условных команд (равна 2).
Если n неизвестно, то для решения задачи вместо цикла типа «до» можно использовать цикл типа «пока»:
n:=0 | начальное значение счетчика разрядов
нц пока x>0 | пока «есть цифры в числе»
y:=mod(x,10) | выделяем очередную цифру
x:=div(x,10) | «отбрасываем» найденную цифру
n:=n+1 | переходим к следующей цифре
вывод (n»,-я цифра:", y) | выдача очередной цифры
кц | конец цикла поиска следующих цифр в числе.
Оценки 2) — 4) при этом не изменяются, а число присваиваний станет равно 3n+1 (все явные). Это демонстрирует тот факт, что недостаток информации для решения задачи (в исходной форме) может увеличивать хаос и сложность.
4. Типы и структуры данных (Задачи с решениями)
4.1. Описать полно все основные стандартные типы данных, т. е. не описываемые в алгоритме специально.
Решение. 1) Тип «целые числа». Имя типа данных: цел. Область определения типа: целые числа iÎ Z. Разрешенные для типа операции::=, +, –, *, **, =, ¹, <, >, ³, £. Функции от аргумента типа: int, mod, abs, sqrt, sign, sin, cos, tg, ctg, arcsin, arccos, arctg, arcctg. ln, lg, exp, div, rnd.
2) Тип «вещественные числа». Имя типа данных: вещ. Область определения типа: вещественные числа rÎ R.. Разрешенные для типа операции::=, +, –, *, **, =, ¹, <, >, ³, £. Функции от аргумента типа: как в типе цел, кроме mod, div.
3) Тип «символьная константа». Имя типа данных: сим. Область определения типа: литеры (символы) языка. Разрешенные для типа операции::=, +, =, ¹, <, >, ³, £. Функции от аргумента типа: длина, [] (вырезка, сечение).
4) Тип «литерная константа». Имя типа данных: лит. Область определения типа: последовательность литер (символов). Разрешенные для типа операции::=, +, =, ¹, <, >, ³, £. Функции от аргумента типа: длина, [] (вырезка, сечение).
5) Тип «логическая константа». Имя типа данных: лог. Область определения типа: 1 («истина»), 0 («ложь»). Разрешенные для типа операции: Ù, Ú, Ø, =, ¹, <, >, ³, £. Функции от аргумента типа: отсутствуют.
4.2 Дана некоторая абстрактная структура данных Список_учеников_школы, состоящая из определенного числа учеников. Привести примеры корректных абстрактных операций для структуры.
Решение. Разрешены, например, абстрактные операции: добавить ученика; удалить ученика; выдать атрибуты ученика.
4.3. Пусть х — переменная типа цел, у — типа вещ, s –типа лог. Определить неправильные (с указанием ошибок) команды:
a) z:=4*x+100; б) y:=max(z,100)<y;
в) s:=(x<0)Ú (y=4); г) x:=mod(x,y).
Решение. Команда а) неверна, логической переменной z будет сделана попытка присвоения целочисленного значения; б) неверна, делается попытка присвоения вещественной переменной у логического значения (значение отношения неравенства — «истина» или «ложь»); в) — верное присваивание; г) неверно, аргумент y функции mod — не целый.
4.4. Описать абстрактные типы данных: День, День_недели, Жилище, Религия.
Решение. День=(пасмурный, светлый, теплый, холодный, дождливый);
День_недели=(понедельник, вторник, среда, четверг, пятница, суббота, воскресенье);
Жилище=(дом, квартира, шалаш, пещера);
Религия=(буддизм, ислам, христианство).
Литература:
Давыдов В. В. Проблемы развивающего обучения. М., 1986
Давыдов В. В. Теория развивающего обучения. М., 1996
Казиев В. М. Развивающие задачи //Информатика и образование.1997, № 3; 1998, № 2.
Философский энциклопедический словарь / М.: Инфра-М, 1997–576 с.
Федеральный государственный образовательный стандарт общего образования. Среднее (полное) общее образование. http://standart.edu.ru/catalog.aspx?Catalogld=6408
Ясенева, Г. Г. Развитие интеллектуальной сферы учащихся на уроках информатики / Г. Г. Ясенева. //Информатика и образование. 2006, № 2.