8 класс -№1

Алгоритм

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

                Известно, что в раннем Средневековье слово algorism использовали для обозначения способа арифметических вычислений на бумаге без применения счетных досок (абаков). Именно в таком значении оно вошло в некоторые европейские языки. Например, в авторитетном словаре английского языка «Webster’s New World Dictionary», изданном в 1957 году., оно снабжено пометкой «устаревшее» и объясняется как выполнение арифметических действий с помощью арабских цифр. Несмотря на то что известно, когда появился термин «алгоритм», лингвисты по-разному пытались толковать его происхождение. Одни выводили algorism из греческих «альгирос» - больной и «арифмом» - число. Правда, не понятно, почему числа «больные»? Другие склонялись к еще более экстравагантному объяснению, связывая слово с неким мифическим древним испанским правителем King Algor of Castil. Свой вариант предлагает и Энциклопедический словарь Брокгауза и Эфрона (1890 г.) В нем «алгорифм» (кстати, до революции использовалось и написание «алгори?м», через «фиту») производится от арабского слова «Аль-Горетм», т.е. корень.
            Но истину удалось установить не лингвистам, а историкам математики. Они доказали, что слово происходит от имени великого среднеазиатского ученого, автора популярнейшего на протяжении многих веков учебника по математике аль – Хорезми, жившего в первой половине IX века. Он написал ряд трактатов по арифметике и алгебре, в том числе книгу "Арифметика индусскими цифрами" – о счете с помощью десяти цифр и правилах арифметических действий с числами.  В латинской транскрипции его имя записывается как Abu’Abd Allah Muhammad ibn Musa al-Khwarismi и означает «Мухаммад, сын Мусы, отец Абдуллы, родом из Хорезма». Хорезм – это историческая область на территории современного Узбекистана, центром которой является город Хива.

Свойства алгоритма

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

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

Формы представления алгоритмов:

• Словестная
• Графическая

o   Рисунки

o   Графы, схемы

o   Блок-схемы

• Программная
• Табличная

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

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

Граф – геометрический объект, состоящий из вершин и соединяющих вершины линий-дуг.

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

Разветвляющийся алгоритм – алгоритм, содержащий структура ветвления.

Циклический алгоритм – алгоритм, содержащий типовую конструкция «цикл».

Тело цикла – описание действий, повторяющихся в цикле. 

Типы циклов:

• С известным числом повторений
• С неизвестным  числом повторений

o   С постусловием

o   С предусловием

Задание №1 

Имеется Исполнитель алгоритма, который может передвигаться по числовой оси. Система команд Исполнителя алгоритма:

1.       «Вперед N»

2.       «Назад M»

Переменные N и M могут принимать любые целые положительные значения. Известно, что Исполнитель алгоритма выполнил программу из 50 команд, в которой команд «Назад 2» на 14 больше, чем команд «Вперед 4». Других команд в программе не было.

Какой одной командой можно заменить эту программу, чтобы Исполнитель алгоритма оказался в той же точке, что и после выполнения программы?
Ответ напишите в тетради!