§ 7. Алгоритмы и их свойства
Большинство действий, совершаемых человеком, выполняются по определенным правилам. Их эффективность во многом зависит от того, насколько он представляет, что делать в каждый момент времени, в какой последовательности, каким должен быть итог его действий. Другими словами, результат деятельности человека непосредственно зависит от того, насколько он представляет алгоритмическую сущность своих действий.
Кроме того, применение в производстве и быту различных автоматов, компьютеров требует от человека строгого соблюдения определенной последовательности действий при их использовании, что, в свою очередь, невозможно без предварительного составления алгоритмов.
Таким образом, осмысление и разработка алгоритмов выполняемых действий становится существенным компонентом деятельности человека, составной частью его культуры мышления и поведения. Алгоритм – одно из фундаментальных понятий, которое используется в различных областях знания, но изучается оно в математике и информатике. Его освоение начинается уже в начальной школе на уроках математики, где ученики овладевают алгоритмами арифметических действий, знакомятся с правилами вычитания числа из суммы, суммы из числа и др.
Вообще формирование алгоритмического мышления у младших школьников в настоящее время является одной из важнейших задач учителя, и поэтому ему требуются определенные знания об алгоритмах, а также некоторые умения в их построении.
Понятие алгоритма
Происхождение термина «алгоритм» связано с математикой. История его возникновения такова. В IХ веке в Багдаде жил ученый ал(аль)-Хорезми (полное имя Мухаммед Бен Мусса ал-Хорезми, т.е. Мухаммед сын Мусы из Хорезма), математик, астроном, географ. В одном из своих трудов он описал десятичную систему счисления и впервые сформулировал правила выполнения арифметических действий над целыми числами и обыкновенными дробями. Арабский оригинал этой книги был утерян, но остался латинский перевод ХIIв., по которому Западная Европа ознакомилась с десятичной системой счисления и правилами выполнения арифметических действий.
Ал-Хорезми стремился к тому, чтобы сформулированные им правила были понятными. Достичь этого в IХ в., когда еще не была разработана математическая символика (знаки операций, скобки, буквенные обозначения и т.д.), было трудно. Однако ему удалось выработать четкий стиль строгого словесного предписания, который не давал читателю возможность уклониться от предписанного или пропустить какие-нибудь действия.
Правила в книгах ал-Хорезми в латинском переводе начинались словами «Алгоризми сказал». В других латинских переводах автор именовался как Алгоритмус. Со временем было забыто, что Алгоризми (Алгоритмус) – это автор правил, и эти правила стали называть алгоритмами. Многие столетия разрабатывались алгоритмы для решения все новых и новых классов задач, но само понятие алгоритма не имело точного математического определения.
В настоящее время понятие алгоритма уточнено, и сделано это в ХХ веке в рамках науки, называемой теорией алгоритмов.
Будем рассматривать алгоритм как программу действий для решения задач определенного типа.
Чтобы какую-либо программу действий можно было назвать алгоритмом, она должна удовлетворять ряду требований. Эти требования называют свойствами алгоритма.
1. Каждая программа, задающая алгоритм, должна состоять из конечного числа шагов, а каждый шаг должен быть точно и однозначно определен. Это свойство алгоритмов называется свойством определенности (или детерминированности).
Согласно этому свойству в алгоритмах не может быть таких, например, предписаний, как «сложить х с одним из данных чисел а или b», «привести два-три примера истинных и ложных высказываний» и т.д.
2. Шаги в алгоритме должны идти в определенной последовательности. Это означает, что в любом алгоритме для каждого шага (кроме последнего) можно указать единственный непосредственно следующий за ним шаг, т.е. такой, что между ними нет других шагов. Это свойство дискретности алгоритмов.
Дискретная структура алгоритмов хорошо вида в алгоритмах выполнения арифметических действий. Например, алгоритм нахождения суммы чисел 34 + 23 формулируется так:
1) Пишу десятки под десятками, а единицы под единицами.
2) Складываю единицы: 4 + 3 = 7, пишу 7 под единицами.
3) Складываю десятки: 3 + 2 = 5, пишу 5 под десятками.
4) Читаю ответ: сумма равна 57.
3. Каждый шаг программы, задающей алгоритм, должен состоять из выполнимых действий. Это означает, что предусмотренные действия были выполнимы теми исполнителями, которым она адресована. Так, например, задание «решить уравнение х + 9 = 17» один ученик уверенно выполняет и получает искомое значение переменной х, так как владеет всеми действиями, необходимыми для решения простейших уравнений.
1) прочитай уравнение;
2) вспомни правило, как найти значение неизвестного;
3) реши уравнение;
4) сделай проверку;
5) запиши ответ.
Другой не справляется с заданием или получает неверный ответ, так как не владеет хотя бы одним из действий, которые требуются для выполнения данного задания.
Как видно из примера, под словом «действие» понимаются не только математические операции, но оно имеет и более широкий смысл.
Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередного действия исполнителю неясно, какое из них должно выполняться на следующем этапе.
Все сказанное характеризует свойство алгоритма, называемое свойством понятности.
4. Программа, задающая алгоритм, должна быть направлена на получение определенного результата. Получение результата за конечное число шагов составляет свойство результативности алгоритма.
5. Программа, задающая алгоритм, должна быть применима к любой задаче рассматриваемого типа. Другими словами, каждый алгоритм решения линейного уравнения первой степени применяется для решения всех уравнений вида ах + b= 0. В этом состоит свойствомассовости алгоритма.
Задачи, для которых может быть составлен алгоритм, и в результате выполнения этого алгоритма получен ответ на вопрос (даже если ответ, что задача не имеет решения), называются алгоритмически разрешимыми.
Алгоритмы могут предназначаться как исполнителю-человеку, так и исполнителю-машине. И в связи с этим между ними могут быть различия. Действия, понятные человеку, могут быть не понятны машине (например, действие «вспомни правило»), и наоборот. Предписания для человека могут содержать желательные, но не обязательные действия, или их можно поменять местами. Например, чтобы определить значение истинности конъюнкции двух высказываний А и В, нужно:
1) определить значение истинности высказывания А;
2) определить значение истинности высказывания В;
3) определить значение истинности высказывания А ∧ В.
Так как операция конъюнкции коммутативна, т.е. А ∧ В⇔ В∧А, то пункты 1) и 2) можно поменять местами. Такой выбор последовательности шагов осуществляет исполнитель-человек, но не машина. Если свойства детерминированности и дискретности сохраняются с некоторой степенью точности, т.е. в программе возможна перестановка шагов или она содержит желательные, но не обязательные шаги, то мы имеем не алгоритм, а алгоритмическое предписание. Однако, несмотря на различия между этими понятиями, часто алгоритмические предписания называются алгоритмами.
Известны различные способы записи алгоритмов: словесная запись, формульная, табличная, на языке блок-схем или алгоритмическом языке.
Словесная запись – это форма представления алгоритмических предписаний. Она допускает употребление естественного языка и математической символики, что делает предписание понятным и доступным для усвоения. Форму словесной записи имеют многие «бытовые» алгоритмические предписания, часто применяемые в повседневной жизни: как испечь пирог, как пользоваться электроприбором, как получить книгу в библиотеке и т.д. Вообще в этой форме могут быть описаны любые предписания, в том числе и математические. Например, алгоритмическое предписание нахождения середины отрезка АВ может иметь вид:
поставить ножку циркуля в точку А;
установить раствор циркуля в точку А;
провести окружность;
поставить ножку циркуля в точку В;
провести окружность;
отметить точки пересечения окружностей;
через отмеченные точки провести прямую;
отметить точку пересечения прямой с отрезком АВ.
Алгоритмы, используемые для вычислений, могут быть записаны в формульной (т.е. с помощью формулы) или табличной (т.е. с помощью таблицы) формах. Например, для нахождения корней квадратного уравнения ах2 + bх + с = 0 (а 0) удобнее применять не словесную запись, а формулу:
х = (- b ± √ b - 4ac) : 2a
Запись алгоритма, используемого для вычислений, в форме таблицы удобно использовать, когда требуется найти не одно, а несколько значений одного и того же выражения для различных значений переменных, входящих в данное выражение.
Рассмотрим алгоритмическое предписание решения следующей задачи: «В одном куске 72 м ткани, а в другом в у раз больше. Сколько метров ткани во втором куске? Составь выражение и найди его значение, если у = 2, 4, 8».
Словесная запись алгоритма решения данной задачи такова:
составить выражение;
найти его значение для у = 2;
найти его значение для у = 4;
найти его значение для у = 8.
Если же оформить предписание в виде таблицы, то запись будет иметь вид:
Значение переменной | у | 2 | 4 | 8 |
Значение выражения | 72 - у |
|
|
|
Алгоритмы можно записывать на языке блок-схем. Такое их представление, состоящее из блоков и стрелок, выполняется следующим образом:
каждый шаг записывается в форме определенной геометрической фигуры (блока);
блок, соответствующий команде, предусматривающей выполнение некоторого действия, в результате которого образуется какой-то новый промежуточный или конечный результат, изображается в виде прямоугольника. Внутри него записывается выполняемое действие. Такие блоки называются арифметическими, или, в более общем виде, перерабатывающими информацию, так как не всегда выполняемые действия являются арифметическими;
блок, соответствующий команде, предусматривающей проверку некоторого условия, изображается в виде ромба. Проверяемое логическое условие записывается внутри него. Выполнение данной команды не приводит к новому результату, а лишь определяет дальнейший ход процесса решения. Такие блоки называются логическими;
если за шагом А непосредственно следует шаг В, то от блока А к блоку В проводится стрелка. От каждого арифметического блока исходит только одна стрелка; от каждого логического - две стрелки: одна с пометкой «да» (или «+»), идущая к блоку, следующему за логическим блоком, если условие выполняется, другая - с пометкой «нет» (или «-»), идущая к блоку, следующему за логическим, если условие не выполняется;
начало и конец алгоритма изображаются блоками в виде овалов, внутри которых записываются соответственно слова «Начало» и «Конец».
да
х + 24
нет
х выписать
Рис 61.
В соответствии с этой схемой устанавливаем, что если х = 15, то х + 24 не больше 40, следовательно, при этом значении х неравенство х + 24 > 40 верным не будет. Аналогично для х = 16. Если же х = 17, то х + 24 будет больше 40, и, значит, при этом значении х неравенство х + 24 > 40 будет верным. Аналогично и для х = 18.
Видим, что блок-схема наглядно представляет логику решения задачи. Поэтому запись алгоритмов в виде блок-схем имеет широкое распространение.
Еще один способ - это запись на определенном алгоритмическом языке. Она используется в том случае, когда исполнитель данного алгоритма - машина, причем каждая машина имеет свой, только ей понятный язык: фортран, паскаль, бейсик, лого и др.
В зависимости от порядка выполнения действий различают следующие виды алгоритмических процессов: линейные, разветвляющиеся, циклические.
Числа Кончились Да
Рис. 62
Примером линейного алгоритмического предписания является ранее рассмотренное нами предписание нахождения середины отрезка. На рисунке 61 в виде блок-схемы представлен разветвляющийся алгоритм выбора из данных чисел тех, которые удовлетворяют неравенству х + 24 > 40. Так как в этом алгоритмическом предписании последовательность действий должна повториться для каждого из данных чисел, то его можно сделать циклическим. Для организации цикла необходимо осуществить перебор всех значений и предусмотреть выход из цикла (рис. 62).
- 050708 (031200) Педагогика и методика начального образования дпп. Ф. 06. Математика
- Глава I. Элементы логики
- § 1. Множества и операции над ними
- 1. Понятие множества и элемента множества
- 2. Способы задания множеств
- 3. Отношения между множествами. Подмножество. Равные множества. Универсальное множество. Круги Эйлера. Числовые множества.
- 4. Пересечение множеств
- 5. Объединение множеств
- 6. Свойства пересечения и объединения множеств
- 7. Вычитание множеств. Дополнение множества до универсального
- 8. Понятие разбиения множества на классы с помощью одного, двух, трех свойств
- 9. Декартово произведение множеств
- 10. Число элементов в объединении и разности конечных множеств
- 11. Число элементов в декартовом произведении конечных множеств
- 12. Основные понятия:
- § 2. Математические понятия
- 3. Способы определения понятий
- 4. Основные выводы
- § 3. Математические предложения
- § 4. Математическое доказательство
- 26. Схемы дедуктивных умозаключений.
- §5. Текстовая задача и процесс ее решения
- 29. Структура текстовой задачи
- 30. Методы и способы решения текстовых задач
- 31. Этапы решения задачи и приемы их выполнения
- 2. Поиск и составление плана решения задачи
- 3. Осуществление плана решения задачи
- 4. Проверка решения задачи
- 5. Моделирование в процессе решения текстовых задач
- Упражнения
- 32. Решение задач «на части»
- Упражнения
- 33. Решение задач на движение
- Упражнения
- 34. Основные выводы.
- §6. Комбинаторные задачи и их решение
- § 7. Алгоритмы и их свойства
- Упражнения
- Упражнения
- Глава II. Элементы алгебры
- § 8. Соответствия между двумя множествами
- 41. Понятие соответствия. Способы задания соответствий
- 2. Граф и график соответствия. Соответствие, обратное данному. Виды соответствий.
- 3. Взаимно-однозначные соответствия
- Упражнения
- 42. Взаимно однозначные соответствия. Понятие взаимно однозначного отображения множества х на множество y
- 2. Равномощные множества. Способы установления равномощности множеств. Счетные и несчетные множества.
- Упражнения
- 43. Основные выводы § 8
- § 9. Числовые функции
- 44. Понятие функции. Способы задания функций
- 2. График функции. Свойство монотонности функции
- Упражнения
- 45. Прямая и обратная пропорциональности
- Упражнения
- 46. Основные выводы § 9
- §10. Отношения на множестве
- 47. Понятие отношения на множестве
- Упражнения
- 48. Свойства отношений
- R рефлексивно на х ↔ х r х для любого х € X.
- R симметрично на х ↔ (х r y →yRx).
- 49. Отношения эквивалентности и порядка
- Упражнения
- 50. Основные выводы § 10
- § 11. Алгебраические операции на множестве
- 51. Понятие алгебраической операции
- Упражнения
- 52. Свойства алгебраических операций
- Упражнения
- 53. Основные выводы § 11
- § 12. Выражения. Уравнения. Неравенства
- 54. Выражения и их тождественные преобразования
- Упражнения
- 55. Числовые равенства и неравенства
- Упражнения
- 56. Уравнения с одной переменной
- 2. Равносильные уравнения. Теоремы о равносильности уравнений
- 3. Решение уравнений с одной переменной
- Упражнения
- 57. Неравенства с одной переменной
- 2. Равносильные неравенства. Теоремы о равносильности неравенств
- 3. Решение неравенств с одной переменной
- Упражнения
- 58. Основные выводы § 12
- Упражнения
- Глава III. Натуральные числа и нуль
- § 13. Из истории возникновения понятия натурального числа
- § 14. Аксиоматическое построение системы натуральных чисел
- 59. Об аксиоматическом способе построения теории
- Упражнения
- 60. Основные понятия и аксиомы. Определение натурального числа
- Упражнения
- 61. Сложение
- 62. Умножение
- 63. Упорядоченность множества натуральных чисел
- Упражнения
- 64. Вычитание
- Упражнения
- 65. Деление
- 66. Множество целых неотрицательных чисел
- Упражнения
- 67. Метод математической индукции
- Упражнения
- 68. Количественные натуральные числа. Счет
- Упражнения
- 69. Основные выводы § 14
- 70. Теоретико-множественный смысл натурального числа, нуля и отношения «меньше»
- Упражнения
- Лекция 36. Теоретико-множественный подход в построении множества целых неотрицательных чисел.
- 71. Теоретико-множественный смысл суммы
- Упражнения
- 72. Теоретико-множественный смысл разности
- Упражнения
- 73. Теоретико-множественный смысл произведения
- Упражнения
- 74. Теоретико-множественный смысл частного натуральных чисел
- Упражнения
- 75. Основные выводы § 15
- §16. Натуральное число как мера величины
- 76. Понятие положительной скалярной величины и ее измерения
- Упражнения
- 77. Смысл натурального числа, полученного в результате измерения величины. Смысл суммы и разности
- Упражнения
- 78. Смысл произведения и частного натуральных чисел, полученных в результате измерения величин
- 79. Основные выводы § 16
- 80. Позиционные и непозиционные системы счисления
- 81. Запись числа в десятичной системе счисления
- Упражнения
- 82. Алгоритм сложения
- Упражнения
- 83. Алгоритм вычитания
- Упражнения
- 84. Алгоритм умножения
- Упражнения
- 85. Алгоритм деления
- 86. Позиционные системы счисления, отличные от десятичной
- 87. Основные выводы § 17
- § 18. Делимость натуральных чисел
- 88. Отношение делимости и его свойства
- 89. Признаки делимости
- 90. Наименьшее общее кратное и наибольший общий делитель
- 2. Основные свойства наименьшего общего кратного и наибольшего общего делителя чисел
- 3. Признак делимости на составное число
- Упражнения
- 91. Простые числа
- 92. Способы нахождения наибольшего общего делителя и наименьшего общего кратного чисел
- 93. Основные выводы § 18
- 3. Дистрибутивности:
- § 19. О расширении множества натуральных чисел
- 94. Понятие дроби
- Упражнения
- 95. Положительные рациональные числа
- 96. Множество положительных рациональных чисел как расширение
- 97. Запись положительных рациональных чисел в виде десятичных дробей
- 98. Действительные числа
- 99. Основные выводы § 19
- Глава IV. Геометрические фигуры и величины
- § 20. Из истории возникновения и развития геометрии
- 1. Сущность аксиоматического метода в построении теории
- 2. Возникновение геометрии. Геометрия Евклида и геометрия Лобачевского
- 3. Система геометрических понятий, изучаемых в школе. Основные свойства принадлежности точек и прямых, взаимного расположения точек на плоскости и прямой.
- § 21. Свойства геометрических фигур на плоскости
- § 22. Построение геометрических фигур
- 1. Элементарные задачи на построение
- 2. Этапы решения задачи на построение
- Упражнения
- 3. Методы решения задач на построение: преобразования геометрических фигур на плоскости: центральная, осевая симметрии, гомотетия, движение.
- Основные выводы
- §24. Изображение пространственных фигур на плоскости
- 1. Свойства параллельного проектирования
- 2. Многогранники и их изображение
- Тетраэдр Куб Октаэдр
- Упражнения
- 3. Шар, цилиндр, конус и их изображение
- Основные выводы
- § 25. Геометрические величины
- 1. Длина отрезка и ее измерение
- 1) Равные отрезки имеют равные длины;
- 2) Если отрезок состоит из двух отрезков, то его длина равна сумме длин его частей.
- Упражнения
- 2. Величина угла и ее измерение Каждый угол имеет величину. Специального названия для нее в
- 1) Равные углы имеют равные величины;
- 2) Если угол состоит из двух углов, то его величина равна сумме величин его частей.
- Упражнения
- 1) Равные фигуры имеют равные площади;
- 2) Если фигура состоит из двух частей, то ее площадь равна сумме площадей этих частей.
- 4. Площадь многоугольника
- 5. Площадь произвольной плоской фигуры и ее измерение
- Упражнения
- Основные выводы
- 1. Понятие положительной скалярной величины и ее измерение
- 1) Масса одинакова у тел, уравновешивающих друг друга на весах;
- 2) Масса складывается, когда тела соединяются вместе: масса нескольких тел, взятых вместе, равна сумме их масс.
- Заключение
- Список литературы