Обзорная работа по категориям и уровням межпредметных заданий в информатике (5 класс и старше)

Чайка К.В. учитель информатики гимназии №1 г. Симферополя

Содержание

Содержание  2

Уровни межпредметных заданий   3

Логические задачи   4

Кодирование информации   8

Системы счисления и позиционная запись   10

Построение графиков   12

Решение задач подбором параметров   17

Нахождение экстремумов   20

Альтернатива перебора   21

Длинная арифметика   23

Криптография   25

Матрицы    26

Элементы дифференциального и интегрального исчисления   28

Комбинаторика   31

Разложение функций в ряды    33

Некоторые олимпиадные задачи   34

Числа Фибоначчи и «Золотое сечение»  36

Не включенные в разбор темы    39

Уровни межпредметных заданий

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

	IV. Исследовательские Систематизация, анализ и синтез; Формирование предметной компетентности;
	III. Творческие Формирование интереса к предметной области; Стимулирование самостоятельного изучения;
	II. Усиленные Развитие абстрактного мышления;  Разнообразие логических приемов;
	I. Стандартные Изучение базовой программы; Расширение класса решаемых задач;

                                            Цель нашей жизни столь бесспорна,

                                            Что зря не мучайся, приятель:

                                            Мы сеем будущего зерна,

                                            А что взойдет - решит Создатель.

                                                                   И. Губерман

Логические задачи

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

Задача №1

Составить из 6 спичек 4 равносторонних треугольника

Решение

Расположите спички в виде тетраэдра.

Задача №2

Задано число 81**. Вместо звездочек вставить цифры так, чтобы полученное число делилось на 45

Решение

Чтобы данное число делилось на 45 необходимо, чтобы оно делилось на 5 и 9. Чтобы число делилось на 5, оно должно заканчиваться цифрами 0 или 5. Чтобы оно делилось на 9, сумма его цифр тоже должна быть кратна 9. Значит, такими числами могут быть 8100, 8145 и 8190.

Задача №3

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

               

Идея решения

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

Логические задачи в информатике

В информатике тоже рассматривается класс логических задач, но основное внимание уделяется не свойствам чисел и геометрических объектов, а логическим умозаключениям и алгоритмическому подходу решения задач

Игра «Блеф-лоб»

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

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

Для разминки представьте, что Катя заявила: «Я не знаю», а Петя и Вася по очереди произнесли: «Я проиграл». Услышав сказанное, можно догадаться, что у Кати на лбу был туз, а у ребят – карты помладше. Иллюстрация поможет вам разобраться, почему это именно так.

Я проиграл Я не проиграл Я не выиграл Я выиграл Делим куш Я не знаю

А теперь к делу. Что вы можете сказать о картах игроков по приведенным стенограммам пяти игр?

Игра 1: Катя сказала: «Я не знаю». Петя произнес: «Я не выиграл», а Вася объявил: «Я выиграл».

Игра 2: Катя призналась: «Я не знаю». Петя молвил: «Я не выиграл». Вася изрек: «Делим куш».

Игра 3: Катя произнесла: «Я не знаю», а Петя и Вася сказали: «Я не выиграл».

Игра 4: Сначала все трое заявили: «Я не знаю», а затем Катя молвила: «Я проиграла». Как вы считаете, что потом сказали Петя и Вася?

Игра 5: Первые два раза все трое говорили: «Я не знаю». Затем Катя и Петя сказали: «Я не знаю», а Вася радостно вскричал: «Я выиграл!» Какая у него была карта, и что он  увидел на лбах своих товарищей?

Таблицы истинности

Дима занимается карате, Петр никогда не увлекался дзюдо, айкидо  и греко-римской борьбой, Миша достиг определенного уровня в дзюдо и айкидо, Алеша занимался всеми названными видами единоборств, Боря владеет приемами бокса и айкидо. Ребята договорились идти на соревнования по одному виду спорта каждый, причем, не пересекаясь с друзьями. Как они могут это сделать?

Решение

Составим таблицу истинности для названных условий

спортсмен	карате	дзюдо	айкидо	греко-римск. борьба	бокс
Дима	+
Петр		-	-	-
Миша		+	+
Алеша	+	+	+	+	+
Боря			+		+

Очевидно, что Дима пойдет на чемпионат по карате. Тогда Петру придется пойти на бокс. Значит, Борису нужно участвовать в соревнованиях айкидо. В итоге Миша выберет дзюдо, а Алеша постарается победить как борец греко-римского стиля.

Логические схемы

Задача №1

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

а) В начальный момент времени все выключатели выключены. Три ученика расположились у выключателей A, C и D, а затем щелкнули рубильниками. Включился ли в зале свет? б) Могут ли 2 ученика включить свет в зале, не переходя к разным выключателям? Может ли это сделать 1 ученик?

Решение

Задание (а) можно отнести к 1 уровню классификации. Оно несложно решается с применением таблиц истинности функций конъюнкции, дизъюнкции и отрицания.

Задание (б), которое скорее относится ко второй ступени, решается «с конца». Ко второй схеме «И» должны прийти сигналы 1 с обоих входов. Значит в схему «Не» должен прийти 0, т.е. А и B нулевые. Первая схема «И» даст 1 только в том случае, когда C и D равны 1. Следовательно, 2 ученика могут включить свет, а 1 – нет.

Задача №2

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

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

Решение

1. Очевидно, что если на входе схемы И и ИЛИ находятся либо одни нули, либо единицы, то ответ будет одинаков в обоих случаях. Значит, нам нужно добиться того, чтобы к каждой схеме «подходили» разные сигналы – 0 и 1.

2. На входы A, B, C и D нужно подать соответственно 1, 0, 1 и 1. Если все элементы указаны верно, то на выходе E появится ноль, а на выходе F – единица (можете проверить с помощью таблиц истинности). Если хотя бы один из вентилей указан неправильно, комбинация результатов на выходах будет иной.

Кодирование информации

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

Совершенные коды

Исходные 4 разряда кода Хемминга	Полные 7 бит с учетом контрольных разрядов

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

Информационный обрыв

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

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

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

Маше я сообщил, что точка лежит на линии x=13, Васе – что она расположена на прямой y=6, а Кате – что искомые координаты связаны соотношением y=x–7 (см. рис. внизу). Как мои товарищи могут использовать полученную информацию? Согласны ли вы, что для успешного поиска необходимо и достаточно получить сведения, известные любой паре?

Системы счисления и позиционная запись

Подобного рода задачи помогают ученикам отчетливо понять термины «цифра», «число», способы записи чисел и основные арифметические операции над ними

Задачи на уроке информатики

Номера задач 1-3 соответствуют ступени классификации. Данные задачи можно рассматривать как развивающие системный подход и логическое мышление.

Задача №1

Каждый день своей жизни на необитаемом острове Робинзон Крузо делал зарубку на дереве. Какая система счисления при этом использовалась?

Решение

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

Задача №2

С. А. Хоар как-то сказал «Некоторые люди на пальцах считают до 10, я же до 1023». Поясните, каким образом это возможно.

Решение

Люди используют для счета на пальцах унарную систему, а Хоар подразумевал бинарную. т.е. прижатый палец означал 0, а поднятый 1. В итоге счет на пальцах можно вести от 0 до 2¹⁰-1=1023.

Задача №3

„В бумагах одного чудака-математика найдена была его автобиография. Она началась следующими строками: «Я окончил курс университета 44 лет от роду. Спустя год, 100-летним молодым человеком, я женился на 34-летней девушке. Незначительная разница в возрасте — всего 11 лет,— способствовала тому, что мы жили общими интересами и мечтами. Спустя немного лет, у меня была уже и маленькая семья из 10 детей» и т. д. Чем объяснить странные противоречия в числах этого отрывка?

Решение

Недесятичная система счисления—вот единственная причина кажущейся противоречивости приведенных чисел. Напав на эту мысль, нетрудно догадаться, в какой именно системе счисления изображены числа чудаком-математиком. Секрет выдается фразой: „спустя год (после 44-летнего возраста), 100-летним молодым человеком..." Если от прибавления одной единицы число 44 преображается в 100, то, значит, цифра 4—наибольшая в этой системе (как 9—в десятичной), а следовательно, основанием системы является 5.

Задачи на уроке математики

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

Задача №1

Перевести 567₁₀ в двоичную систему методом «деления уголком»

_567	2
566	_283	2
1	282	_141	2
	1	140	_70	2
		1	70	_35	2
			0	34	_17	2
				1	16	_8	2
					1	8	_4	2
						0	4	_2	2
							0	2	1
								0
									1

567 в двоичной системе счисления записывается как 1000110111.

Задача №2

Найти неизвестные x и y, если верны соотношения

Решение

Выравниваем единицы измерения информации:

Отбрасывая теперь размерности, получаем:

          Отсюда следует, что x=17, y=7

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

Функции одной переменной

Описание

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

                                   

в каждой из которых вычисляется значение функции f(x)

                                    ,

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

Применение

y=x2 y=3x+2 x парабола прямая -5 25 -13 -4 16 -10 -3 9 -7 -2 4 -4 -1 1 -1 0 0 2 1 1 5 2 4 8 3 9 11 4 16 14 5 25 17

Недостатки

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

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

Рис. Пример неправильного построения графика функции, имеющего разрывы

Преимущества

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

Пример

График функции

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

Производная положительна, т.е. функция строго возрастает на всей своей области определения . Характерная точка x=0 y=5^1/4. Нулей функции нет. В общем, стандартная схема исследования не дает нам много сведений о поведении кривой.

Параметрические кривые

Перейти от графиков функций одной переменной к кривым, заданным параметрическими уравнениями с помощью табличного процессора Microsoft Office Excel совсем несложно. Задав таблицу значений функций x(t) и y(t), нам остается всего лишь расставить пары точек (x_i,y_i) и соединить их гладкими кривыми.

Рисунок. Траектория тела с двумя взаимно перпендикулярными гармоническими колебаниями (фигуры Лиссажу)

Объемные и заданные параметрически фигуры

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

Декартовы координаты                                           «Экранная» система координат

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

Решение задач подбором параметров

Инструмент «Подбор параметра» в табличном процессоре

Описание

Метод позволяет найти один произвольный корень уравнения вида:

                                   

Математическая сущность этого численного метода проста. На числовой прямой перебором значений находятся точки x₁ и x₂ , такие что:

                                              

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

Применение

1. В одну из ячеек рабочего листа помещается произвольное значение аргумента x. Затем в другую записывается функция f(x) по синтаксическим правилам табличного процессора
2. Задав соответствующие формулы в MS Excel, выполним Сервис → Подбор параметра

3. Воспользоваться результатами вычислений, представленными в виде:

Преимущества

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

Пример

x¹⁷-5x⁹+7x⁸-x²+2cos(x)=10

Недостатки

• Находит лишь ОДНО решение (либо позволяет сделать вывод, что корней нет), то есть, строго говоря, НЕ РЕШАЕТ уравнение.

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

Нахождение экстремумов

Надстройка «Поиск решения»

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

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

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

Альтернатива перебора

Вычисление сумм и средних величин в наборах данных

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

, где d – разность соседних членов

Аналитические решения вместо циклов

Пример:

В ребусе КТО+КОТ=ТОК все цифры заменены буквами. Найти значение слова КОТ.

1 решение:

перебор вариантов К(1-9), Т(1-9), О(0-9). Итого 810 комбинаций.

2 решение:

                                       О+Т=К или О+Т=10+К                                 

 (первое неверно)=>

• ответ: 459

И все же если альтернативы НЕТ…

Здесь я приведу задачу второй ступени, с двумя переборными решениями. Если проанализировать условие задачи, то неизбежный процесс перебора можно значительно упростить (особенно для решения №1, если брать лишь числа, кратные 13 и т.д.)

Семейка Адамс

У каждого члена семейки Адамс есть своя счастливая цифра:

Известно что

Раскройте тайну семьи Адамс (узнайте цифру каждого члена семьи).

Решение №1 (Электронная таблица с фильтром)

Переберем все четырехзначные числа и проверим, для какого из них выполняется данное свойство:

 

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

=(A4=H4)

после чего остается лишь применить автофильтр и выяснить что:

Решение №2 (Программа)

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

Длинная арифметика

Суммирование длинных чисел

Пусть требуется сложить 2 числа

               и         

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

Копированием нескольких ячеек заполним две строки исходными числами. Выровняем эти числа по правому краю

Теперь сумму можно определить, найдя каждую цифру этого числа.

Задача

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

Турнир юных математиков

Задача

Учитель математики Сергей Иванович хочет проверить, какой остаток дает число 19202122…979899 (подряд записаны двузначные числа от 19 до 99) при делении на 3³ и 3⁴. Помогите ему узнать это, используя электронные таблицы.

Подсказка: признак делимости по сумме цифр как для чисел 3 и 3²=9 здесь не применим.

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

Ответ: ДА.

Чтобы определить делится ли полученное число еще раз на 3 можно продолжить эту логику (по сути – деление уголком) или воспользоваться признаком делимости на 3 числа, записанного в строке 4. Для этого достаточно найти сумму ячеек диапазона 4:4 и разделить ее на 3.

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

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

Ввод новой системы счисления

Существуют и другие представления "длинных" чисел. Рассмотрим одно из них.

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

30! = 265252859812191058636308480000000

в виде:

30! =2×(10⁴)⁸+6525× (10⁴)⁷+2859× (10⁴) +
            +  8121× (10⁴)⁵ + 9105×(10⁴)⁴+
            +  8636× (10⁴)^{3  +} 3084 ×(10⁴)² +
            +  8000× (10⁴)¹ + 0000× (10⁴)⁰.

Это представление наталкивает на мысль о массиве, приведенном в таблице:

Номер элемента в массиве А	-1	0	1	2	3	4	5	6	7	8
Значение	9	0	8000	3084	8636	9105	8121	2859	6525	2

Мы можем считать, что наше "длинное" число представлено в 10000—10 системе счисления (десятитысячно-десятичная система счисления, приведите аналогию с восьмерично-десятичной системой счисления), а "цифрами" числа являются четырехзначные числа.

Примечание: Элемент с номером -1 мы вводим для удобства работы, чтобы знать, сколько у нас реально используемых элементов массива

Криптография

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

Простые числа

• Простые числа имеют широкое применение в криптографии, поскольку при кодировании чисел нередко используется разложение числа на простые множители
• Криптография с открытыми ключами часто использует большие простые числа (большие 512 бит)

Алгоритм Евклида

Алгоритм Евклида основан на том факте, что любой делитель элементов R и r также должен делить их сумму и разность.

Малая теорема Ферма

Если p – простое число, x^p-1=1 (mod p)                                  (1)

Для любого x, простого относительно p: x^p=x (mod p)          (2)

Китайская теорема об остатках

Для заданных простых чисел p₁, p₂, …, p_k и произвольных чисел c₁,c₂, …, c_k система сравнений

имеет единственное решение по модулю

Арифметика вычетов

Если Маша обещала быть дома в 10:00 и вернулась на 13 часов позже, то когда она пришла домой и что ей сказал отец :) ?

Это арифметика по модулю 12. Двадцать три по модулю 12 равно 11

            (10+13) mod 12=23 mod 12=11 mod 12

            10+13º11 (mod 12)

Матрицы

Метод Крамера решения СЛАУ

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

Описание метода

Для системы линейных алгебраических уравнений

вычисляется определитель матрицы системы

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

после чего находим корни по формулам

                                                                              

Определители 3-го порядка и выше

Метод вычисления детерминанта 3 порядка (формула Сарюса):

Для нахождения определителей матриц более высокого порядка можно использовать встроенную функцию МОПРЕД

Демонстрация применения метода Крамера на уроке информатики

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

Важно!

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

Элементы линейной алгебры

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

• Операции с матрицами (сложение, вычитание, умножение)
• Нахождение обратной матрицы

Типовые задачи с матрицами на уроке информатики

• Поиск наибольшего и наименьшего элементов
• Седловая точка

Элементы дифференциального и интегрального исчисления

Производные

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

Нам нужно лишь вспомнить, что производная – это предел отношения приращения функции к приращению аргумента, когда оно стремится к нулю:

                       

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

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

Вычисление определенных интегралов

1. Геометрический смысл

Известно, что определенный интеграл  функции y=f(x) численно представляет собой площадь криволинейной трапеции S, ограниченной кривыми: y=0, x=a, x=b и y=f(x). В случаях, когда функцию затруднительно проинтегрировать аналитическим путем, можно воспользоваться численными методами.

2. Геометрический метод

Вычислить интеграл:

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

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

3. Суть метода трапеций

xn

Площадь криволинейной трапеции S приближенно можно вычислить, сведя ее к нескольким прямолинейным трапециям. Для этого разобьем отрезок [a; b] на n равных частей. Очевидно, что чем мельче будет разбиение отрезка [a; b], тем ближе будет площадь S к сумме площадей S Sn . Каждая из площадей этих прямолинейных трапеций рассчитывается по формуле в итоге получаем

,

где D - длина интервалов, на которые разбивается отрезок.

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

Комбинаторика

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

Пример задачи

Пусть некоторое агентство недвижимости располагает базой данных из n записей. Требуется найти все пары таких записей, в которых предложение первой строки совпадает с запросом второй. (На бытовом языке это называется подбором вариантов обмена). Допустим, что 1 вариант проверяется 1 мс. При «лобовом» алгоритме поиска вариантов (каждую запись сравнивать с каждой) потребуется

                                   

вариантов. Для 100 записей ответ будет получен за 4,95 с, но для 100000 – 1389 ЧАСОВ. А ведь возможны еще варианты, когда число участников сделки больше двух!

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

—  Упрощение перебора, сокращение циклических итераций

—  Криптостойкость систем (оценка сложности алгоритмов, определение количества попыток перебора паролей, времени взлома и т.д.)

◦       Подбор пароля длины m из формального алфавита n символов – n^m попыток (размещения с повторениями)

◦       количество всех перестановок из множества  X = {x₁, x₂, …, x_k} равно k!

—  Сжатие информации в базах данных

Порождение и перебор комбинаторных объектов

Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе ВСЕХ возможных вариантов и сравнении их между собой. Поэтому так важно для нас научиться строить алгоритмы ПЕРЕБОРА различных комбинаторных объектов - последовательностей, перестановок, подмножеств и т.д.

Схема перебора всегда будет одинакова:

- во-первых, надо установить ПОРЯДОК на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);

- во-вторых, научиться переходить от произвольного элемента к НЕПОСРЕДСТВЕННО СЛЕДУЮЩЕМУ за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1<x2 и между x1 и x2 нет других элементов).

Наиболее естественным способом упорядочения составных объектов является ЛЕКСИКОГРАФИЧЕСКИЙ порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.) - именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать заново.

Комбинаторные задачи теории информации

Задача №1 (Флаги на мачтах)

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

Решение

Каждый способ развешивания флагов можно осуществить в два этапа. На первом этапе мы переставляем всеми возможными способами данные n флагов. Это можно сделать n! способами. После этого берем один из способов распределения n одинаковых флагов по k мачтам (число таких способов равно ). Пусть этот способ заключается в том, что на первую мачту надо повесить n₁ флагов, на вторую n₂ флагов, …, на k-ю n_k флагов, где . Тогда берем первые n₁ флагов данной перестановки, следующие n₂ развешиваем на второй мачте и т.д. Ясно, что используя все перестановки n флагов и все способы распределения n одинаковых флагов по k мачтам, мы получим все способы решения поставленной задачи.

 

Задача №2 (Полное число сигналов)

Найдем полное число сигналов, которые можно передать с помощью n сигнальных флагов, вывешиваемых на k мачтах.

Решение

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

           

Задача №3 (Передача сигналов по времени)

Сообщение передается с помощью сигналов нескольких типов. Длительность передачи сигнала первого типа равна t₁, второго типа t₂, …, k-го типа t_k единиц времени. Сколько различных сообщений можно передать с помощью этих сигналов за T единиц времени?

Решение

Обозначим число сообщений, которые можно передать за время T через f(T).

           

При этом f(T)=0, если T<0 и f(0)=1

Разложение функций в ряды

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

              

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

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

Некоторые олимпиадные задачи

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

Задача №1

Однажды мне встретилось интересное пятизначное число А.  Приписывая 1 впереди этого числа, я получил, конечно, число шестизначное: [1] [A]; приписывая 1 в конце его, я тоже получил шестизначное число: [A] [1]; но второе шестизначное число оказалось втрое больше первого.  Найдите это число А.

Математическая модель

Варианты решений

При простом переборе необходимо выполнить 99999 переборных итераций. Альтернативой такого подхода является составить и решить простое линейное уравнение

                        3×(10000+А)=А×10+1

Задача №2

На плоскости заданы координаты N точек

                       

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

Решение

1. Если точка находится внутри выпуклого многоугольника, то она находится внутри одного из треугольников, которые образованы его вершинами. То есть, можно свести задачу к более простой: проверить принадлежит ли точка треугольнику
2. Для точки А справедливо одно из утверждений

если точка А снаружи DPQR	если точка А внутри DPQR

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

Задача №3

Натуральные числа, кубы которых заканчиваются на 888 образуют последовательность. Найти элемент с номером N.

«Лобовой» подход

«Лобовой» подход заключается в простом переборе натуральных чисел для проверки, заканчивается ли его куб на 888. Начиная с 12 числа, тип данных не позволяет сохранять результат вычислений и с 1000 программа уже не выдерживает лимита времени.

Эмпирический подход

Написать программу для «лобового перебора» первых нескольких чисел и проанализировать их:

                        192, 442, 692, 942, 1192

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

           

Математический подход

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

Числа Фибоначчи и «Золотое сечение»

Числа Фибоначчи

Последовательность чисел Фибоначчи определяется простыми формулами:

для всех n>2

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

Табличный процессор	Язык программирования

Основы художественного восприятия

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

Что мы считаем красивым? Подчиняется ли наше восприятие математическим законам? Огромный интерес учащихся вызывает рассказ о «Золотом сечении».

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

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

Пропорции в теле человека

Додекаэдр Леонардо да Винчи

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

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

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

Не включенные в разбор темы

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

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

Инструментальные средства

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

Редактор формул

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

Подготовка наглядных пособий для уроков геометрии

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

Фрагменты ученической презентации сечений объемных фигур

Векторы

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

Разностные уравнения

Решение разностных уравнений, задаваемых рекуррентными соотношениями, например:

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

Теория графов

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

 

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