Интуитивное понятие алгоритма



Скачать 115.92 Kb.
Дата23.12.2012
Размер115.92 Kb.
ТипУрок

УРОК №1-2
ТЕМА «Интуитивное понятие алгоритма»


Цель урока:

повторение понятия алгоритма, обобщение и систематизация знаний.

Задачи урока:

образовательные:

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

развивающие:

развитие алгоритмического мышления, способностей к формализации, элементов системного мышления;

воспитательные:

воспитание чувства ответственности за результаты своего труда.

Материалы и оборудование к уроку:

ПК, презентация "Элементы теоретического программирования - 1 - Что такое алгоритм.ppt".

Тип урока:

лекция.

Форма проведения урока:

беседа.

План урока:

УРОК №1-2
ТЕМА «Интуитивное понятие алгоритма»

1. Вступление.

2. Что такое алгоритм?

3. Откуда взялось слово «алгоритм»?

4. Интуитивное понятие алгоритма

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

6. Задачи.

Ход урока:

1. Вступление.


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

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

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

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

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

Один из создателей математических теорий алгоритмов советский математик А. А. Марков (1903—1979) считал, что это было допустимо, пока термин «алгоритм» встречался в математике лишь в высказываниях следующего типа: «Для решения таких-то задач имеется алгоритм, и вот в чем он состоит».

По той же причине интуитивное понятие алгоритма достаточно и когда ставится вопрос о переводе уже имеющегося алгоритма в программу для решения задачи на ЭВМ. Программа — это лишь запись алгоритма на языке, понимаемом данной ЭВМ.

В математике часто возникают так называемые алгоритмические проблемы, когда требуется найти единый метод (алгоритм) для решения любой задачи из данного класса однотипных задач. Алгоритмические проблемы возникали и решались в различных областях математики на протяжении всей ее истории. Однако в первые десятилетия XX века накопилось много классов задач, для решения которых алгоритма найти не удавалось. Усилия, прилагавшиеся к нахождению алгоритмов решения этих классов задач, привели к мысли: а вдруг для того или иного класса просто невозможно найти алгоритм, т. е. искомый алгоритм не существует?

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

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

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

2. Что такое алгоритм?


Задача: "Делится ли натуральное число a на натуральное число b?"

Мы имеем здесь не одну, а бесконечный класс однотипных задач (столько, сколько существует пар натуральных чисел (a; b)). Иногда класс однотипных задач называют иначе общей задачей, а получаемые путем подстановки вместо a и b конкретных натуральных чисел задачи этого класса называют частными. Так, например, частными задачами рассматриваемого класса задач (или рассматриваемой общей задачи) являются следующие: «делится ли 21 564 на 132?», «делится ли 1056 на 24?» и т. п.

Естественно возникает вопрос: существует ли общий метод, позволяющий для любой частной задачи этого класса в конечное число шагов дать требуемый ответ (в виде «да» или «нет»)?
Задача: "Имеет ли уравнение ax2+bx+c=0, где a,b,c  Q, вещественные корни?"

Здесь мы опять имеем общую задачу, или бесконечный класс однотипных частных задач (столько задач, сколько имеется троек (a; b; c) рациональных чисел или сколько имеется квадратных уравнений с рациональными коэффициентами). И опять возникает, тот же вопрос: существует ли общий метод, позволяющий для любой частной задачи этого класса в конечное число шагов дать требуемый ответ в виде «да» или «нет»?
Мы рассмотрели два класса задач, требующих ответа вида «да» или «нет». Вопрос, который мы дважды поставили, существует ли общий метод, позволяющий для любой задачи данного класса в конечное число шагов дать ответ «да» или «нет», называют проблемой разрешения для этого класса задач, а общий метод, если он существует, называется разрешающей процедурой, разрешающим алгоритмом или просто алгоритмом.
В математике встречаются, однако, не только такие классы задач, которые требуют ответа вида «да» или «нет». Имеется большое разнообразие классов задач, требующих в качестве ответа предъявления некоторого объекта (числа, множества чисел, функции и др.).

Формулировка таких задач начинается обычно словом «найти» или словами «чему равно?» и т.п.

Задача: «Чему равна сумма двух натуральных чисел a и b?».

Здесь опять имеем бесконечный класс однотипных частных задач, требующих в качестве ответа предъявления определенного натурального числа (суммы данных двух натуральных чисел). И здесь возникает тот же вопрос: существует ли общий метод, позволяющий для любой частной задачи этого класса в конечное число шагов дать требуемый ответ, т. е. предъявить натуральное число, являющееся суммой двух данных натуральных чисел?

Задача: «Найти множество вещественных решений системы неравенств , где a, b  Z».

Здесь опять имеем бесконечный класс однотипных задач (столько, сколько пар (a; b) целых чисел) и возникает тот же вопрос: существует ли общий метод, позволяющий для любой частной задачи этого класса в конечное число шагов дать ответ в виде некоторого множества вещественных чисел (множества решений системы)?
Поставленный для каждого из этих классов задач вопрос, «существует ли общий метод, позволяющий для каждой частной задачи данного класса в конечное число шагов дать требуемый ответ», называется проблемой вычисления, а искомый общий метод, если он существует, называется вычислительной процедурой, вычислительным алгоритмом или просто алгоритмом.
Примеры алгоритмов:

1. Рассмотрим класс задач "Решить уравнение ах = b (a, b  Q)".

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

1) Если а ≠ 0, то перейти к ук. 2, иначе — к ук. 3.

2) Уравнение имеет единственный корень х = b/a. Перейти к ук. 6.

3) Если b ≠ 0, то перейти к ук. 4, иначе — к ук. 5.

4) Уравнение не имеет корней. Перейти к ук. 6.

5) Любое число является корнем уравнения. Перейти к ук. 6.

6) Процесс решения окончен.
2. Рассмотрим класс задач "Чему равен наибольший общий делитель двух неравных натуральных чисел a, b (НОД (а, b) = ?)"

Рассмотрим вариант метода, использующий действие деления, известный поэтому и как метод последовательного деления. Он основан на свойстве: НОД (a, b) = НОД (b, r), где r — остаток от деления a на b.

1. Разделить a на b. Перейти к ук. 2.

2. Если остаток r = 0, то перейти к ук. 4, иначе — к ук. 3.

3. Присвоить a значение b, b — значение r. Перейти к ук. 1.

4. НОД (a, b) = b. Перейти к ук. 5.

5. Процесс окончен.
Задачи

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

2. Приведите примеры классов задач вида «чему равно?» и опишите соответствующие вычислительные алгоритмы.

3. Откуда взялось слово «алгоритм»?


см. файл "Откуда взялось слово алгоритм.doc"

4. Интуитивное понятие алгоритма


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

А что значит «точное предписание», «понятное предписание», «действие», «решить любую задачу», «класс однотипных задач»?

Объясним смысл этих слов.

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

2) Что означают слова «понятное предписание»? Это не только предписание, выраженное на понятном исполнителю языке. В конце концов, если оно написано на французском языке, его можно перевести на русский, английский и т. д. Главное состоит в том, чтобы предусмотренные предписанием действия были выполнимыми определенной категорией исполнителей, которым оно адресовано. Иначе говоря, чтобы эти действия принадлежали системе действий исполнителя. Под системой действий исполнителя понимают совокупность действий, которые он умеет выполнять. Чтобы предписание, задающее алгоритм, было понятным, оно должно быть конечным, т. е. выражено с помощью конечного текста. Бесконечно длинные предписания исключаются ввиду того, что они принципиально не допускают передачи исполнителю. Таким образом, говоря «понятное предписание», будем иметь в виду конечное предписание, предусматривающее действия, входящие в систему действий исполнителя.

3) Что понимают под словом «действие»? Это, разумеется, далеко не только арифметические или, вообще, математические операции. Ведь алгоритмы встречаются отнюдь не только в математике. Это слово применяется в весьма широком (и пока не-уточненном) смысле, охватывающем и действия токаря, изготовляющего деталь, и действия, человека, переходящего улицу, и действия медсестры, берущей кровь на анализ или делающей инъекцию. И можно назвать еще тысячи разновидностей действий.

4) Что означает «решить любую задачу» из данного класса однотипных задач? Во-первых, это означает, что каждый алгоритм предназначен для решения не одной единственной задачи, а любой задачи из некоторого бесконечного класса однотипных задач. Алгоритм является единым методом, позволяющим по любому исходному объекту из определенного бесконечного множества исходных объектов получить искомый результат. В этом состоит свойство массовости алгоритма.

Во-вторых, «решить задачу» означает решить ее «за конечное число шагов». Получение результата за конечное число шагов составляет свойство результативности алгоритма.

В-третьих, так как предписание, задающее алгоритм, обеспечивает получение результата за конечное число шагов, то это означает также, что всякий алгоритм представляет собой упорядоченное конечное множество шагов. А всякое такое множество обладает свойством дискретности. Этим свойством обладает множество N натуральных чисел, хотя оно и бесконечное. Это свойство состоит в том, что для каждого натурального числа можно указать единственное непосредственно следующее за ним натуральное число, т. е. такое, что между ними нет других натуральных чисел. В любом алгоритме для каждого шага (кроме, разумеется, последнего) можно указать единственный (при данном выборе исходных объектов), непосредственно следующий за ним шаг, т. е. такой, что между ними нет других шагов. Поэтому и говорят, что алгоритм обладает свойством дискретности или дискретной структурой.

5) Что означает «класс однотипных задач»? Класс однотипных задач или общая задача обычно формулируется (в математике) с использованием некоторых переменных — параметров. Например, общая задача «Решить уравнение ax2+bx+c=0, где a,b,c  Q содержит три параметра (a, b, с), при этом задается область значений параметров (Q). Подставляя вместо а, b, с в формулировке общей задачи любую тройку рациональных чисел, получаем частную задачу этого класса. Таким образом мы можем получить столько однотипных частных задач, сколько существует различных троек рациональных чисел, т. е. бесконечное множество. Исходным объектом для соответствующего алгоритма является любая тройка рациональных чисел.

6) И еще одно свойство, присущее любому алгоритму. Исходные объекты, промежуточные и окончательные результаты — конструктивные объекты. Эти объекты могут быть построены целиком или допускают кодирование посредством слов в некоторых конечных алфавитах. Например, натуральное число — конструктивный объект, так как любое натуральное число можно закодировать с помощью слова в алфавите {0, 1, 2, ..., 9} десятичной системы счисления или с помощью слова в алфавите {0, 1} двоичной системы счисления и т.п.

Целые числа можно выразить словами в алфавите {0, 1, 2, ..., 9, –}.

Рациональные — словами в алфавите {0, 1, 2, ..., 9, –, /}.

Арифметические выражения, составленные из чисел, знаков арифметических действий и скобок, можно рассматривать как слова в алфавите {0, 1, 2, ..., 9, +, –, , /, (, )}.

Многочлены с рациональными коэффициентами и одной переменной х можно рассматривать как слова в алфавите {0, 1, 2, ..., 9, +, –, , /, x}.

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

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

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

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

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


  1. Словесная форма;

  2. Блок-схема;

  3. Алгоритмическая запись (или запись на языке программирования).


Задача "Чему равен наибольший общий делитель двух неравных натуральных чисел a, b (НОД (а, b) = ?)"

1. Словесная форма. См. выше

2. Блок-схема.



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

3. Запись на языке программирования. Сделать самостоятельно.

6. Задачи.


  1. Постройте алгоритм (в словесной форме, блок-схему, программу на алгоритмическом языке) для решения класса задач: "Решить уравнение ax2+bx+c=0, a, b, c  Q"

  2. Постройте алгоритм (в словесной форме, блок-схему, программу на алгоритмическом языке) для решения класса задач: "Решить неравенство ax

  3. В прямоугольной системе координат задан центр A(x1,y1) круга радиуса R и точка M(x2,y2). Составить алгоритм, определяющий, принадлежит ли точка M заданному кругу.


Литература:

  1. Макаренков Ю.А., Столяр А.А. Что такое алгоритм? Беседы со старшеклассниками. Мн.: Народна асвета, 1989.

  2. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 2-е изд., испр. М.:МЦНМО, 2002, 192 с.

Похожие:

Интуитивное понятие алгоритма iconТема: Алгоритм, свойства алгоритма.
Понятие алгоритма так же фундаментально для информатики, как и понятие информации
Интуитивное понятие алгоритма iconПонятие алгоритма и его характерные черты
Понятие алгоритма принадлежит к числу основных понятий математики. Примерами алгоритмов являются
Интуитивное понятие алгоритма icon6. Теория алгоритмов Понятие алгоритма
Алгоритм это строгое предписание по выполнению последовательности шагов, приводящее к решению задачи данного типа. Понятие алгоритма...
Интуитивное понятие алгоритма iconПонятие алгоритма, его свойства, логические теории алгоритмов
Алгоритм может представлять собой некоторую последовательность вычислений, а может последовательность действий нематематического...
Интуитивное понятие алгоритма iconПрограмма государственного экзамена по направлению «бизнес-информатика»
Понятие алгоритма. Способы записи алгоритма. Принципы оценки эффективности алгоритмов (иллюстрация на примерах)
Интуитивное понятие алгоритма iconТеория алгоритмов
Они определяют порядок выполнения действий для получения желаемого результата. Это можно трактовать как первоначальное или интуитивное...
Интуитивное понятие алгоритма iconСравнительный анализ модификаций алгоритма муравья
Показано, что начальные параметры алгоритма (количество феромона, видимость, коэффициент испарения) существенно влияют на результат...
Интуитивное понятие алгоритма iconКонтроллер промышленный комбинированный (кпк) гамма-11
Понятие данных, параметров настройки, исполняемого алгоритма, данных и параметров настройки алгоритма кпк
Интуитивное понятие алгоритма icon2 Понятие сложности задачи
Известно, что интуитивное представление о сложности задачи не всегда адекватно, а если поставлена существенно незнакомая проблема,...
Интуитивное понятие алгоритма icon8. Теория алгоритмов. 1 Понятие алгоритмической системы
С давних времен в математике сложилось интуитивное представление об алгоритме как формальном предписании, которое определяет совокупность...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org