Исследовательская работа по информатике на тему "Алгоритмы в современном мире"

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

Теория алгоритмов является самостоятельной наукой, которая готова служить всем наукам, и имеет свое лицо, свой предмет.

Тему "Алгоритмов" мы начали изучать еще с 6 класса, где мы рассматривали примеры алгоритмов в сказках и пословицах. В этом году мы снова изучаем данную тему, но уже используем алгоритмы для составления программ на языке программирования Паскаль. И мы решили больше узнать об алгоритмах и их роли в жизни людей.

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

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

Проблема: Алгоритмы определяют жизнь человека или человек определяет алгоритмы?

Актуальность: проникновение понятия "алгоритм" в различные сферы жизни человека.

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

Объект исследования: алгоритмы.

Предмет исследования: алгоритмы на упаковках и других вещах.

Цель проекта - изучение алгоритма в сферах жизни человека.

План работы:

  1. Узнать больше об алгоритмах.
  2. Изучить для чего нужны алгоритмы.
  3. Создать брошюру.

Глава 1. Что такое алгоритм?

Понятие алгоритма

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

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

Таким образом вычисление существует само по себе, при этом оно может быть описано разными способами, с помощью разных алгоритмов.

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

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

История возникновения теории алгоритмов

Важно понять, как возникла эта дисциплина, зачем понадобилось формально определять, что такое вычисление. Один из самых известных алгоритмов — алгоритм Евклида - был описан на рубеже четвертого и третьего веков до н.э. С тех пор человечество разработало огромное количество алгоритмов, но вплоть до первой трети XX века никто не задумывался о необходимости формального определения.

Чуть позже мы поговорим о том, что понимали под алгоритмами все это время, но сейчас важнее другое. История теории алгоритмов берет свое начало в 1900 году, когда крупнейший математик того времени Давид Гильберт на математическом конгрессе в Париже огласил список из 23 нерешенных математических проблем. В некоторых проблемах Гильберт просил найти "механическую процедуру" отыскания решения задачи, то есть фактически он просил найти алгоритм.

К примеру, Десятая проблема Гильберта касалась отыскания общего метода решения диофантовых уравнений. Эта проблема, кстати, была окончательно решена только в 1970 году советским российским математиком Ю.В. Матиясевичем.

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

Более того, в 1928 году он сформулировал еще одну знаменитую проблему, так называемую "проблему разрешения" Гильберт просил найти алгоритм (механическую процедуру), который принимал бы на вход описание некоторой формальной системы (набор аксиом и правил вывода) и конкретное утверждение в этой системе, а возвращал бы "да" или "нет" в зависимости от того, можно ли доказать это утверждение в данной формальной системе.

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

Заметьте важное отличие: либо мы пока не придумали такой алгоритм (не хватило знаний, умений, математической интуиции), либо его вообще невозможно придумать. Но как доказать,что чего-то не существует?

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

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

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

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

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

Мы можем говорить о задаче вычисления чего бы тонибыло как о числовой функции. Скажем, даже рисование в Paint в конечном итоге приводит к преобразованию действий пользователя (последовательность сигналов от мыши и клавиатуры, легко кодируемых числами) в файл с изображением, также кодируемый с помощью чисел. Любое другое вычисление также можно представить подобным образом, задав некоторым специальным образом числовое кодирование сущностей, участвующих в вычислении.

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

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

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

Создание алгоритмов

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

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

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

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

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

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

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

Разновидности, свойства и способы алгоритмов

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

Существует три способа задания алгоритмов:

  1. описательный (словесный);
  2. графический (блок-схемный);
  3. операторный (программный).

Разновидность алгоритмов

Выделяют следующие виды алгоритмов:

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

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

● Алгоритмы циклической структуры Циклическим называется алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий. Эту последовательность многократно повторяемых действий называют циклом.

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

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

Практическая часть

Создание продукта

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

  1. Войти в почту Gmail.
  2. Посмотреть в верхний правый угол, в котором будет 9 квадратиков.
  3. Нажать на них.
  4. После откроется мини окно в котором можно будет увидеть некоторые вспомогательные функции
  5. Выбираем нужную и создаем вопрос

Результаты опроса привели к тому, что больше 50% опрошенных знаю о сути и самой алгоритмизации, о ее роли в жизни. Опрос был составлен на 10 вопросов в которых все было связано с алгоритмами. Сейчас вы увидите статистику и саму форму опроса :

Знаете ли вы что такое алгоритм?
Да 84.6%
Нет -
Затрудняюсь ответить 15.4%

Играет ли важную роль алгоритмизация в жизни людей?
Да 69,2%
Нет -
Затрудняюсь ответить 23,1%

Есть ли алгоритмизация в информатике и математике?
Да 100%
Нет -
Затрудняюсь ответить -

Знаете ли вы базовые структуры алгоритмов?
Да 46.2%
Нет 30.8%
Затрудняюсь ответить 23.1%

Встречаем ли мы виды алгоритмов каждый день?
Да 92.3%
Нет -
Затрудняюсь ответить 7.7%

Есть ли отдельный язык алгоритмов?
Да 30,8%
Нет -
Затрудняюсь ответить 69,2%

Знаете ли как выглядят блок схемы алгоритмов?
Да 38,5%
Нет 23,1%
Затрудняюсь ответить 38,5%

Может ли любой человек создать свой алгоритм?
Да 92,3%
Нет -
Затрудняюсь ответить 7,7%

Нужна ли геометрия в алгоритмических схемах?
Да 53,8%
Нет -
Затрудняюсь ответить 46,2%

Как вы думаете, вы ответили правильно?
Да 23,1%
Нет 7.7%
Затрудняюсь ответить 69.2%

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

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

На основании результатов опроса я решила сделать информационную брошюру-буклет на тему "Алгоритмы".

Заключение

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

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

Алгоритм - это понятное и точное предписание, исполнительно совершить последовательность действий, направленных на достижение цели.

Для разработки алгоритмов и программ используется алгоритмизация - процесс систематического составления алгоритмов для решения поставленных прикладных задач. Алгоритмизация считается обязательным этапом в процессе разработки программ и решении задач на ЭВМ.

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

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

Например, для описания алгоритма применяются блок-схемы. Другим вариантом описания, не зависимым от языка программирования, является псевдокод.

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

В связи с этим вводят такие понятия как сложность алгоритма: временная, по размеру программы, вычислительная и др.

Размер:
33.5 Kb
Скачали:
22