Проблема существования алгоритмов в математике реферат

Обновлено: 05.07.2024

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

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

Первые доказательства алгоритмической неразрешимости касались некоторых вопросов логики и самой теории алгоритмов. Оказалось, например, что неразрешима задача установления истинности произвольной формулы исчисления предикатов (т.е. исчисление предикатов неразрешимо) - эта теорема была доказана в 1936г. Черчем.

В 1946—47 гг. А.А. Марковым и Э. Постом независимо друг от друга доказали отсутствие алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении.

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

Многие слышали на уроке математики или информатики слово “алгоритм”. Это описание определенного порядка действий. Но ведь такие действия “по порядку” мы осуществляем каждый день в разных сферах нашей жизни, не задумываясь о них. С детства нас учили, как правильно чистить зубы, принять душ, одеться в школу, дойти до школы самым безопасным путем, как правильно оформить домашнее задание в тетради и многое другое. Значит, мы пользуемся алгоритмами ежедневно, даже ежеминутно. Этим алгоритмам нас учат взрослые. А можем ли мы сами разрабатывать свои алгоритмы? Можно ли научиться этому? Помогут ли они нам в жизни? Теоретически – да, ведь это облегчит, упорядочит нашу жизнь. Давайте проверим это предположение в данной работе.

Цель работы: узнать, что такое алгоритмы, где их применяют и зачем они так нам нужны.

В ходе работы используем следующие методы:

Анализ научно-исследовательских источников
Наблюдение
Сравнительный анализ
Эмпирические (эксперимент, сравнение, практическая работа)

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

Вложение	Размер
issledovatelskaya_rabota_na_temu_algoritmy_v_nashey_zhizni.docx	185.47 КБ

Предварительный просмотр:

Алгоритмы в нашей жизни Поторочина Ксения Андреевна Россия, Тюменская область, г. Тобольск, МАОУ “Лицей”, 4б класс

ХVII Городская научно-практическая конференция школьников

Алгоритмы в нашей жизни

Автор работы: Поторочина Ксения Андреевна

Место выполнения работы: МАОУ “Лицей”, 4б класс

Россия, Тюменская область, г. Тобольск

Научный руководитель: Вохмина Светлана Викторовна,

учитель начальных классов МАОУ “Лицей”

г. Тобольск, 2020

Цель работы: узнать, что такое алгоритмы, где их применяют и зачем они так нам нужны.

В ходе работы используем следующие методы :

Анализ научно-исследовательских источников
Наблюдение
Сравнительный анализ
Эмпирические (эксперимент, сравнение, практическая работа)

Тема исследования: Алгоритмы в нашей жизни

Предмет исследования: наша повседневная жизнь

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

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

Для достижения данной цели решим поэтапно следующие задачи :

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

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

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

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

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

Он должен работать за конечное количество времени. Если ваш алгоритм не может разобраться с проблемой, для которой он был создан, за конечное количество времени, то он бесполезен.
Он должен иметь чётко определённые инструкции. Каждый шаг алгоритма должен быть точно определён. Инструкции должны быть однозначны для каждого случая.
Он должен быть пригодным к использованию. Алгоритм должен решать проблему, для решения которой он был написан.

Общий вид блок-схемы алгоритма представлен в Приложении №1

Со временем слово algorism (или algorismus ), неизменно присутствовавшее в названиях математических сочинений, обрело значение способа выполнения арифметических действий посредством арабских цифр, то есть на бумаге. Именно в таком значении оно вошло во многие европейские языки .

Алгоритм Евклида.

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

В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары. Евклид предложил алгоритм только для натуральных чисел и геометрических величин (длин, площадей, объёмов). Наглядное объяснение сути алгоритма Евклида приведено в Приложении №3.

С тех пор человечество разработало огромное количество алгоритмов.

Выделяют три основных вида:

Рассмотрим более детально, как они работают.

Линейный.

Наиболее простым считается линейный алгоритм. Он предполагает строгую последовательность выполнения команд или действий. Например, алгоритм “Заварить чай”:

Вымыть заварной чайник от старой заварки и высушить его.
Набрать в чайник свежую воду, и вскипятить ее.
Ополоснуть заварной чайник 3-4 раза закипевшей водой, чтобы согреть его.
В согретый и немного влажный заварной чайник насыпать сухой чай в расчете одна чайная ложка чая на одну чашку воды, входящую в чайник, и плюс еще одна ложка на сам чайник. Приготовленный таким образом чай будет средней крепости.
Дать сухому чаю в заварном чайнике разбухнуть в течение нескольких секунд.
В заварной чайник налить воды, чуть остывшей до 80-85 градусов. Закрыть его крышкой и сверху салфеткой таким образом, чтобы закрылись отверстия в крышке и носике.
Дать чаю настояться 4-5 минут.

Блок-схема приведена в Приложении №4

Разветвлённый.

Данный вид предполагает наличие условия, при котором в случае его соблюдения, действия выполняются в одном порядке, а в противном случае – в другом. Например, возьмем следующую ситуацию – “Переход дороги пешеходом”.

Подходим к светофору.
Смотрим на сигнал светофора.
Он должен быть зеленым (это условие).

Если условие выполняется, мы переходим дорогу.
Если нет – ждем, пока загорится зеленый.

Переходим дорогу.
Конец алгоритма.

Блок-схема приведена в Приложении №5

Циклический.

1. Берем число 1.

2. Проверяем, меньше ли оно 10.

3. Если да, проверяем простое ли это число.

4. Если условие выполняется, записываем его.

5. Берем число 2.

6. Проверяем, меньше ли оно 10.

7. Проверяем, простое ли оно…

…Таким образом, перебираем все числа до 10. Как видите, шаги 1 – 4 будут повторяться некоторое число раз.

Среди циклических выделяют алгоритмы с предусловием, когда условие проверяется в начале цикла, или с постусловием, когда проверка идет в конце цикла.

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

Снимаем выстиранные и высохшие вещи
Оцениваем ткань, из которой изготовлена вещь (мнущаяся она или нет - условие)

Если не мнется, то ее нужно убрать в шкаф
Если условие выполняется, мы переходим к ряду действий

Достать гладильную доску
Достать утюг
Привести вещь в хорошее состояние
Убрать в шкаф

Циклический алгоритм с постусловием встречается при стирке испачканной вещи. Действия – постирать, прополоскать. Условие – отстирались ли пятна. Если да – конец алгоритма. Если нет – действия повторяются.

Блок-схема приведена в Приложении №6

Мы провели небольшой эксперимент среди моих одноклассников. Предложили сыграть в игру с конфетами (игра Буше).

В вазочке 11 конфет (это не обязательно конфеты, и их количество может быть 11, 15, 19 и т.д.). Соперники ходят по очереди, и за каждый ход любой из игроков может взять 1,2 или 3 конфеты. Проигрывает тот, кто вынужден брать последнюю конфету.

Большинство, не зная правильного способа решения этой задачи, проигрывали. Одной девочке повезло, но, как она сама призналась, это была просто удача. Результаты внесли в Таблицу 1 (Приложение 7).

Решение же этой задачки довольно простое, если знаешь этот алгоритм:

Первый ход. Взять два предмета.
Второй и все последующие ходы. Брать столько предметов, чтобы количество предметов, взятых вместе с соперником за очередной ход, в сумме составляло 4.

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

В следующий раз мы выдали каждому кубик Рубика. Цвета на гранях были уже перемешаны. Предстояло выяснить, кто справится со сборкой за наименьшее время. Один мальчик умел его собирать, это его увлечение. Он собрал кубик за 2 минуты и 9 секунд. Остальные ребята вернули кубики, не справившись с заданием. Результат в Таблице 2 (Приложение 8).

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

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

Мы сортируем вещи, книги, тетради и даже людей! Ведь мы сами выбираем с кем дружить, с кем пойти гулять и т.д.

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

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

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

Алгоритмы управляют всем. Без алгоритмов нашего мира не было бы совсем.

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

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

Собрала для вас похожие темы рефератов, посмотрите, почитайте:

Введение

Алгоритм — точная инструкция исполнителю выполнить определенную последовательность действий для достижения цели в ограниченном количестве шагов.

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

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

Такие качества:

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

Во-первых, неправильно связывать алгоритм с решением проблемы. Алгоритм может вообще не решить проблему.

Типы алгоритмов

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

Линейный алгоритм — набор команд (инструкций), которые выполняются одна за другой во времени.

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

Циклический алгоритм — алгоритм, обеспечивающий многократное повторение одного и того же действия (одних и тех же операций) для новых исходных данных. На циклических алгоритмах сокращено большинство методов вычислений, поиск вариантов.

Цикл программы — это последовательность инструкций (серия, тело цикла), которую можно выполнять много раз (для новых исходных данных) до тех пор, пока не будет выполнено определенное условие.

Вспомогательный алгоритм (алгоритм slave) — алгоритм, который был ранее разработан и полностью использован при алгоритмизации конкретной задачи. В некоторых случаях, когда существуют одинаковые последовательности инструкций (команд) для разных данных, чтобы сократить набор данных, также назначается вспомогательный алгоритм.

На всех этапах подготовки к алгоритмизации задачи часто используется структурное представление алгоритма.

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

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

Требования к алгоритму

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

Третье правило — усмотрение. Алгоритм состоит из отдельных шагов (действий, операций, команд). Множество шагов, из которых алгоритм естественно составлен.

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

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

Заключение

Список литературы

Образовательный сайт для студентов и школьников

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

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

Рассмотрим в качестве примера задачу о диофантовых уравнениях.

Диофантовы уравнения (названы в память греческого математика Диофанта, жившего в III в. н. э.) имеют вид

где Р и Q – полиномы, например:

ax 2 + bx + c = y 2 ; ax n + bx n = cz n ; ax 3 + bx 2 y + cxy 2 + dy 3 = 1.

Коэффициенты a, b, c и степень n – целые числа; решения – значения x, y, z – также должны быть целыми числами. Конечно, решения не всегда существуют: вспомним хотя бы известную теорему Ферма о том, что уравнение x n + y n = z n , n > 2, не имеет целочисленных решений. Теорема была сформулирована Пьером де Ферма в середине XVII в. без доказательства и доказана Эндрю Уайлсом в 1995 г.

Эта задача распознавания проще, чем задача нахождения решения, т.е. определения числовых значений x, y, z, …, удовлетворяющих диофантову уравнению. Но все равно она достаточно амбициозна, если учесть тот срок, который потребовался математикам для ответа на такой же вопрос, сформулированный в теореме Ферма.

Неудивительно, что на решение 10-й проблемы Гильберта ушло 70 лет, и ответ был неожиданным: Ю.Матиясевич доказал, что такого алгоритма не существует!

Общая задача определяется:

1) списком параметров lp – свободных переменных, конкретные значения которых не определены;

2) формулировкой условий – свойств, которыми должен обладать ответ (решение задачи).

Решением такой задачи z(lp) со списком параметров lp является алгоритм (lp) – тоже кодируемый строкой символов, интерпретируемой (выполняемой) некоторым вычислителем, причем важно то, что некоторые участки строки интерпретируются многократно (циклически) потенциально неограниченное число раз. Более точно можно сказать, что решением массовой задачи являются алгоритм + вычислитель.

Частная задача получается из общей задачи, если всем параметрам общей задачи придать конкретные значения (задать исходные данные).

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

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

Читайте также: