Составление алгоритмов. Различные подходы к формализации понятия алгоритма
Тема программы: Задачи и алгоритмы
Цели работы:
1) Обобщить теоретические знания по теме «Задачи и алгоритмы».
2) Рассмотреть алгоритмы решений заданий теме « Задачи и алгоритмы в программировании», решить задачи.
3) Формировать тактичность; терпимость; умение доказать свою точку зрения при работе в коллективе.
Теоретические основы
Понятие алгоритма, можно назвать понятием алгоритма в интуитивном смысле. Оно имеет нечеткий, неформальный характер, ссылается на некоторые точно не определенные, но интуитивно понятные вещи. Например, при определении и обсуждении свойств алгоритма мы исходили из возможностей некоторого исполнителя алгоритма. Его наличие предполагалось, но ничего определенного о нем не было известно. На основе обобщения свойств алгоритмов различной природы и имеют прикладной характер. Этих свойств достаточно для практического программирования, для создания обширного круга программ для компьютеров, станков с ЧПУ, промышленных роботов и т.д. Однако, как фундаментальное научное понятие алгоритм требует более обстоятельного изучения. Оно невозможно без уточнения понятия «алгоритм», более строгого его описания или, как еще говорят, без егоформализации.
Известно несколько подходов к формализации понятия «алгоритм»:
• теория конечных и бесконечных автоматов;
• теория вычислимых (рекурсивных) функций;
• λ-исчисление Черча.
|
|
|
Все эти возникшие исторически независимо друг от друга подходы оказались впоследствии эквивалентными. Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. Мы рассмотрим постановку этой проблемы и некоторые результаты теории алгоритмической разрешимости задач, но вначале обсудим формализацию понятия алгоритма в теории автоматов на примере машин Поста, Тьюринга, а также нормальных алгоритмов Маркова, а затем - основы теории рекурсивных функций. Идеи λ-исчислений Черча реализованы в языке программирования LISP.
Вместе с тем, формально определенный любым из известных способов алгоритм не может в практическом программировании заменить то, что мы называли алгоритмами. Основная причина состоит в том, что формальное определение резко сужает круг рассматриваемых задач, делая многие практически важные задачи недоступными для рассмотрения.
Этапы решения задачи на ЭВМ
Работа по решению любой задачи с использованием компьютера делится на следующие этапы:
1. Постановка задачи.
2. Формализация задачи.
3. Построение алгоритма.
4. Составление программы на языке программирования.
5. Отладка и тестирование программы.
6. Проведение расчетов и анализ полученных результатов.
|
|
|
Часто эту последовательность называют технологической цепочкой решения задачи на ЭВМ. Непосредственно к программированию в этом списке относятся пункты 3, 4, 5.
На этапе постановки задачи должно быть четко сформулировано, что дано и что требуется найти. Здесь очень важно определить полный набор исходных данных, необходимых для получения решения.
Второй этап — формализация задачи. Здесь чаще всего задача переводится на язык математических формул, уравнений, отношений. Если решение требует математического описания какого-то реального объекта, явления или процесса, то формализация равносильна получению соответствующей математической модели.
Третий этап — построение алгоритма. Опытные программисты часто сразу пишут программы на языках, не прибегая к каким-либо специальным способам описания алгоритмов (блок-схемам, псевдокодам). Однако в учебных целях полезно использовать эти средства, а затем переводить полученный алгоритм на язык программирования .
Первые три этапа предусматривают работу без компьютера. Дальше следует собственно программирование на определенном языке, в определенной системе программирования.
|
|
|
Последний (шестой) этап — это использование уже разработанной программы в практических целях.
Таким образом, программист должен обладать следующими знаниями и навыками:
1. уметь строить алгоритмы;
2. знать языки программирования;
3. уметь работать в соответствующей системе программирования.
Основой программистской грамотности является развитое алгоритмическое мышление.
Понятие алгоритма. Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi — латинского написания имени Мухаммеда аль-Хорезми (787 — 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел — вот первые алгоритмы в математике.
Правила алгебраических преобразований, способы вычислений корней уравнений также можно отнести к математическим алгоритмам.
|
|
|
В наше время понятие алгоритма трактуется шире. Алгоритм — это последовательность команд управления каким-либо исполнителем. В школьном курсе информатики с понятием алгоритма, с методами построения алгоритмов ученики знакомятся на примерах учебных исполнителей: Робота, Черепахи, Чертежника и т.д. Эти исполнители ничего не вычисляют. Они создают рисунки на экране, перемещаются в лабиринтах, перетаскивают предметы с места на место. Таких исполнителей принято называть исполнителями, работающими в обстановке.
Часто задача, которую требуется решить, сформулирована не на математическом языке. Для решения на компьютере ее сначала нужно привести к форме математической задачи, а потом уже программировать.
Работа по решению таких задач с использованием компьютера проходит через следующие этапы:
1. Постановка задачи.
2. Математическая формализация.
3. Построение алгоритма.
4. Составление программы на языке программирования.
5. Отладка и тестирование программы.
6. Проведение расчетов и анализ полученных результатов.
Эту последовательность называют технологией решения задачи на компьютере.
В чистом виде программированием, т. е. разработкой алгоритма и программы, здесь являются лишь 3-й, 4-й и 5-й этапы.
На этапе постановки задачи должно быть четко определено, что дано и что требуется найти.
Второй этап - математическая формализация. Здесь задача переводится на язык математических формул, уравнений, отношений. Далеко не всегда эти формулы очевидны. Нередко их приходится выводить самому или отыскивать в специальной литературе. Если решение задачи требует математического описания какого-то реального объекта, явления или процесса, то формализация равносильна получению соответствующей математической модели.
Третий этап - построение алгоритма. Вы знаете два способа описания алгоритмов: блок-схемы и Алгоритмический язык (АЯ).
Первые три этапа - это работа без компьютера. Дальше следует собственно программирование на определенном языке в определенной системе программирования. Последний (шестой) этап - это использование уже разработанной программы в практических целях.
Дата добавления: 2018-02-28; просмотров: 1177; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!