Алгоритмы и исполнители

Мухаммед ибн аль-Хорезми и понятие «Алгоритм»

Само слово «алгоритм» происходит от имени персидского учёного Абу Абдуллах  Муха ммеда ибн Муса аль-Хорезми (алгоритм — аль-Хорезми). Около 82 5 го да он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, персидский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал ци фр у 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII в е ка книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритмы о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алг е бра (алгебра — аль-джебр — сложение).

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

Одни выводили algorism из греческих algiros (больной) и arithmos (число). Из такого объяснения не очень ясно, почему числа именно «больные». Или же лингвистам больными казались люди, имеющие несчастье заниматься вычислениями? Своё объяснение предлагал и энциклопе дич еский словарь Брокгауза и Ефрона. В нём алгорифм (кстати, до революции использовалось написание алгориθм, через ф ит у) производится «от арабского слова Аль-Горетм, то есть корень». Разумеется, эти объяснения вряд ли можно счесть убедительными.

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

Про аль-Хорезми позднейшие авторы ничего не знали, но поскольку первый перевод книги начинается словами: «Dixit algorizmi: …» («Аль-Хорезми говорил: …»), всё ещё связывали это слово с именем конкретного человека. Очень распространённой была версия о греческом происхождении книги. В англо-норманнской рукописи XII I ве ка, написанной в стихах, читаем: «Алгоризм был придуман в Греции. Это часть арифметики. Придуман он был мастером по имени Алгоризм, который дал ему своё имя. И поскольку его звали Алгоризм, Он назвал свою книгу «Алгоризм».

Примеры игр для освоения темы «Алгоритмизация»

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

Кроме того, принцип работы алгоритма на перестановку элементов массива в порядке возрастания, поиска максимального (минимального) элемента удобно продемонстрировать с помощью ролевого исполнения алгоритма, примером которого является игра «Сценка».

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

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

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

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

Игра «Японский рисунок». На доске имеется поле, размерностью NЧM клеток. Каждый учащийся получает многомерный массив, который содержит значения только 1 и 0. Задача каждого ученика заключается в том, чтобы составить верный алгоритма подсчета количества нулей и единиц в своем массиве, и зарисовать на доске клетку, координаты которой по горизонтали и по вертикали равны соответственно количеству нулей и единиц в своем массиве. Если все подсчеты будут выполнены правильно, то из зарисованных клеток на доске сложится определенный рисунок.

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

Игра «Спортлото». Учащиеся получают задание написать алгоритм, который бы обнулял те стоки многомерного массива NхM, которые содержат указанное число. Затем каждый ученик получает свой лотерейный билет (файл, содержащий многомерный массив NЧM). Учащиеся по очереди вытягивают хбочонки с номерами, которые последовательно вводят в написанную ранее программу. Таким образом, победителем станет тот ученик, у которого раньше других будут вычеркнуты все строки его лотерейного билета, т.е. обнуляться все строки многомерного массива.