Секция Информатика
 Скачать 185.47 Kb.
|
|
ХVII Городская научно-практическая конференция школьников «Первые шаги- 2020» Секция: Информатика. Алгоритмы в нашей жизни Автор работы: Поторочина Ксения Андреевна Место выполнения работы: МАОУ “Лицей”, 4б класс Россия, Тюменская область, г. Тобольск Научный руководитель: Вохмина Светлана Викторовна, учитель начальных классов МАОУ “Лицей” г. Тобольск, 2020 Аннотация Многие слышали на уроке математики или информатики слово “алгоритм”. Это описание определенного порядка действий. Но ведь такие действия “по порядку” мы осуществляем каждый день в разных сферах нашей жизни, не задумываясь о них. С детства нас учили, как правильно чистить зубы, принять душ, одеться в школу, дойти до школы самым безопасным путем, как правильно оформить домашнее задание в тетради и многое другое. Значит, мы пользуемся алгоритмами ежедневно, даже ежеминутно. Этим алгоритмам нас учат взрослые. А можем ли мы сами разрабатывать свои алгоритмы? Можно ли научиться этому? Помогут ли они нам в жизни? Теоретически – да, ведь это облегчит, упорядочит нашу жизнь. Давайте проверим это предположение в данной работе. Цель работы: узнать, что такое алгоритмы, где их применяют и зачем они так нам нужны. В ходе работы используем следующие методы: Анализ научно-исследовательских источников Наблюдение Сравнительный анализ Эмпирические (эксперимент, сравнение, практическая работа) В ходе работы мы выяснили, что обучение принципам алгоритмизации играет важную роль в воспитании и образовании. Алгоритмическое мышление позволяет решить многие повседневные задачи быстрее, проще, с наилучшим эффектом. Человек становится сосредоточенным, способным логически планировать и выполнять свои действия. Он приобретает умение четко и последовательно выражать свои мысли, правильно ставить задачу и находить окончательные пути ее решения, быстро ориентироваться в стремительном потоке информации. План исследований Тема исследования: Алгоритмы в нашей жизни Предмет исследования: наша повседневная жизнь Объект исследования – алгоритмы Нами выдвинута гипотеза: жизнь современного человека невозможна без структурирования. Алгоритмы существенно облегчают нашу жизнь, многие повседневные проблемы можно решить с помощью них Для достижения данной цели решим поэтапно следующие задачи: Разберем, что такое алгоритмы Выясним, зачем нужны алгоритмы, какую функцию они выполняют Изучим историю возникновения понятия «алгоритм» Выделим основные виды алгоритмов Проведем эксперимент среди моих одноклассников – зафиксируем скорость решения таких задач, как “задача Буше” и кубик Рубика, с использованием алгоритмов и без них Найдем “повседневные” алгоритмы, разработаем подобные алгоритмы сами Актуальность: понятия «алгоритм» давно уже не только математическое, произошла алгоритмизация (техника разработки алгоритма для решения задач) каждой сферы нашей жизни. Они структурируют нашу жизнь, делают ее проще, прописывая оптимальные решения для самых распространенных ситуаций, с которыми мы можем столкнуться в нашей повседневной жизни. ????? СодержаниеЧто такое алгоритмы 5 История алгоритмов 6 История возникновения термина «Алгоритм» 6 Алгоритм Евклида. 7 Какие бывают алгоритмы. 7 Линейный. 8 Разветвлённый. 8 Циклический. 8 Эксперимент 10 Алгоритмы в моей жизни 10 Заключение 11 Источники информации 12 Приложения 13 Приложение №1 13 Приложение №2 14 Приложение №3 14 Приложение №4 16 Приложение №5 17 Приложение №6 18 Приложение №7 19 Приложение №8 19 Научная статья Что такое алгоритмыАлгори́тм - это набор инструкций, описывающих порядок действий исполнителя для достижения результата за конечное число действий. Любой алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Исполнитель — субъект, способный исполнять некоторый набор команд. Совокупность команд, которые исполнитель может понять и выполнить, называется системой команд исполнителя. Для выполнения алгоритма исполнителю недостаточно только самого алгоритма. Выполнить алгоритм — значит применить его к решению конкретной задачи, т. е. выполнить запланированные действия по отношению к определенным входным данным. Поэтому исполнителю необходимо иметь исходные (входные) данные — те, что задаются до начала алгоритма. В результате выполнения алгоритма исполнитель должен получить искомый результат — выходные данные, которые исполнитель выдает как результат выполненной работы. В процессе работы исполнитель может создавать и использовать данные, не являющиеся выходными, — промежуточные данные. Проще говоря, алгоритм представляет собой последовательность шагов, которая позволяет решить определённую задачу. Алгоритм должен обладать тремя важными характеристиками, чтобы иметь право так называться: Он должен работать за конечное количество времени. Если ваш алгоритм не может разобраться с проблемой, для которой он был создан, за конечное количество времени, то он бесполезен. Он должен иметь чётко определённые инструкции. Каждый шаг алгоритма должен быть точно определён. Инструкции должны быть однозначны для каждого случая. Он должен быть пригодным к использованию. Алгоритм должен решать проблему, для решения которой он был написан. Общий вид блок-схемы алгоритма представлен в Приложении №1 История алгоритмовИстория возникновения термина «Алгоритм»Само слово «алгоритм» происходит от имени хорезмского учёного аль-Хорезми. Около 825 года он написал сочинение Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»), из оригинального названия которого происходит слово «алгебра» (аль-джебр — восполнение)(см. Приложение №2) В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском») — таким образом, латинизированное имя среднеазиатского учёного было вынесено в заглавие книги. Сегодня считается, что слово «алгоритм» попало в европейские языки именно благодаря этому переводу. В течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр, и все они имели в названии слово algoritmi или algorismi. Со временем слово algorism (или algorismus), неизменно присутствовавшее в названиях математических сочинений, обрело значение способа выполнения арифметических действий посредством арабских цифр, то есть на бумаге. Именно в таком значении оно вошло во многие европейские языки. В 1684 году Готфрид Лейбниц в своём сочинение впервые использовал слово «алгоритм» в еще более широком смысле: как систематический способ решения проблем дифференциального исчисления. Пользовался словом «алгоритм» и еще один выдающийся математик- Леонард Эйлер. Он понимает понятие «алгоритм» в еще более широком смысле, а именно: как синоним способа решения задач. В 30-ые годы 20 века возникает научное направление «Теория алгоритмов». Наибольший вклад в эту теорию внесли английский математик Алан Тьюринг и русский математик Андрей Марков. Алан Тьюринг создал теорию «логических вычисляющих машин». А Андрей Марков ввёл понятие «нормального алгоритма». Что же касается людей, от математики далёких, то к началу сороковых годов это слово они могли услышать разве что во время учёбы в школе, в сочетании «алгоритм Евклида». Несмотря на это, алгоритм всё ещё воспринимался как термин сугубо специальный. Одновременно с развитием понятия алгоритма постепенно происходила и его проникновение из чистой математики в другие сферы. И начало ей положило появление компьютеров, благодаря которому слово «алгоритм» вошло в 1985 г. во все школьные учебники информатики и обрело новую жизнь. За последние два десятилетия компьютер стал неотъемлемым атрибутом нашей жизни, компьютерная лексика становится всё более привычной. Слово «алгоритм» в наши дни известно, вероятно, каждому. Оно уверенно шагнуло даже в разговорную речь. Алгоритм Евклида.Один из самых известных алгоритмов — алгоритм Евклида — был описан на рубеже четвёртого и третьего веков до н.э. Это эффективный алгоритм для нахождения наибольшего общего делителя двух целых цисел (или общей меры двух отрезков). Алгоритм хоть и назван в честь греческого математика Евклида, но не был им открыт. В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары. Евклид предложил алгоритм только для натуральных чисел и геометрических величин (длин, площадей, объёмов). Наглядное объяснение сути алгоритма Евклида приведено в Приложении №3. С тех пор человечество разработало огромное количество алгоритмов. Какие бывают алгоритмы.Выделяют три основных вида: 1.Линейный алгоритм. 2.Ветвящийся алгоритм. 3.Циклический алгоритм. Рассмотрим более детально, как они работают. Линейный.Наиболее простым считается линейный алгоритм. Он предполагает строгую последовательность выполнения команд или действий. Например, алгоритм “Заварить чай”: Вымыть заварной чайник от старой заварки и высушить его. Набрать в чайник свежую воду, и вскипятить ее. Ополоснуть заварной чайник 3-4 раза закипевшей водой, чтобы согреть его. В согретый и немного влажный заварной чайник насыпать сухой чай в расчете одна чайная ложка чая на одну чашку воды, входящую в чайник, и плюс еще одна ложка на сам чайник. Приготовленный таким образом чай будет средней крепости. Дать сухому чаю в заварном чайнике разбухнуть в течение нескольких секунд. В заварной чайник налить воды, чуть остывшей до 80-85 градусов. Закрыть его крышкой и сверху салфеткой таким образом, чтобы закрылись отверстия в крышке и носике. Дать чаю настояться 4-5 минут. Блок-схема приведена в Приложении №4 Разветвлённый.Данный вид предполагает наличие условия, при котором в случае его соблюдения, действия выполняются в одном порядке, а в противном случае – в другом. Например, возьмем следующую ситуацию – “Переход дороги пешеходом”. Подходим к светофору. Смотрим на сигнал светофора. Он должен быть зеленым (это условие). Если условие выполняется, мы переходим дорогу. Если нет – ждем, пока загорится зеленый. Переходим дорогу. Конец алгоритма. Блок-схема приведена в Приложении №5 Циклический.Алгоритм предполагает участок вычислений или действий, который выполняется до выполнения определенного условия. Возьмем простой пример. Есть ряд чисел от 1 до 10. Нам необходимо найти все простые числа, то есть те, которые делятся на единицу и себя. Назовем алгоритм «Простые числа». 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). Решение этой задачи намного сложнее, чем предыдущей. Но потренировавшись, собрать кубик Рубика сможет каждый. Алгоритмов по его сборке много, они довольно объёмные, и приводить их здесь мы не будем. Схемы и видео можно посмотреть в сети Интернет. Алгоритмы в моей жизниСамые распространенные алгоритмы- алгоритмы сортировки. Их мы используем при поиске чего-либо, расположенном в алфавитном порядке. Сортировка лежит в основе работы компьютеров. По сути, именно необходимость сортировки послужила причиной создания компьютера. Если слово, которое мы хотим найти, начинается с буквы «а», ищем его в начале данной таблицы, а если с буквы «ф» – ищем ближе к концу. Таким же образом, если слово начинается с буквосочетания «ва», мы найдем его в начале раздела слов на букву «в», а если с буквосочетания «ву» – ищем ближе к концу раздела. И далее следуем тому же правилу. Мы сортируем вещи, книги, тетради и даже людей! Ведь мы сами выбираем с кем дружить, с кем пойти гулять и т.д. Кеширование мы используем, разбирая свой шкаф в конце школьного года. Мы перебираем листы бумаги, тетради, книги и прочее. И выбрасываем то, что нам уже не пригодится или пришло в негодность. Мы группируем похожие вещи и решаем их судьбу, затем думаем над тем, как разложить оставшиеся в шкафу. По такому же принципу устроена и память человека. Постепенно более поздние воспоминания стираются, а те, что свежее – мы можем вспомнить детально. Это вытеснение по давности использования. Поэтому важно повторять пройденный материал перед контрольной работой, экзаменом. К планированию мы прибегаем каждый день. Расставляя приоритеты в задачах по степени важности и сроку исполнения. ЗаключениеАлгоритмы управляют всем. Без алгоритмов нашего мира не было бы совсем. С помощью алгоритмов можно решить многие бытовые задачи, их можно применить ко всем жизненным ситуациям, в которых мы сталкиваемся с вопросом нахождения оптимального решения. Выполнив исследовательскую работу, я ознакомилась с историей возникновения понятия «алгоритм», принципом самого старого алгоритма - “алгоритма Евклида”, разобрала, чем отличаются основные виды. С удивлением узнала, что многие повседневные вещи и есть алгоритмы (например, рецепты), а наши ежедневные действия подчиняются принципам алгоритмизации. Интересно было научиться такому фокусу, как “игра Буше”. А еще я наконец-то научилась собирать кубик Рубика! В ходе нашего эксперимента стало ясно, что алгоритмы могут решить такие задачи, которые без них кажутся абсолютно невыполнимыми. Поэтому учиться понимать, составлять их, активно применять в повседневной жизни – очень важно. Это серьезный инструмент для улучшения нашей жизни. Я не смогла понять сути сложных видов алгоритмов, но теперь я очень жду, когда подрасту и познакомлюсь с ними на уроках информатики и математики. Это действительно интересно! Источники информацииВикипедия Фильм BBC “Тайные правила современной жизни: Алгоритмы” (2015 год) “Алгоритмы для жизни: Простые способы принимать верные решения” Брайан Кристиан, Том Гриффитс Что такое алгоритм? Час кода на Учи.ру. Вебинар Сергея Шашкова Джордж Дворских “10 алгоритмов, которые правят миром” ПриложенияПриложение №1Общий вид блок-схемы алгоритма   Приложение №2Страница из «Алгебры» аль-Хорезми — хорезмскогоматематика, от имени которого происходит слово алгоритм.  Приложение №3Алгоритм Евклида Это способ нахождения наибольшего общего делителя. Пример:
В данном случае это число 4. И 12, и 8 делятся на него без остатка. Общий делитель легко найти для небольших чисел. Но с большими все гораздо сложнее. Допустим, у нас есть пол прямоугольной формы.  Ч И нам нужно найти наиболее эффективный способ замостить его напольной плиткой без остатка. То есть размеры пола – это два числа, сторона квадратной плитки – наибольший общий делитель.  1 шаг алгоритма Заполняем прямоугольник квадратами со стороной, равной наименьшей стороне прямоугольника 2 шаг Далее делаем тоже самое с оставшимся прямоугольником  3 шаг  И снова повторяем действия 4 шаг  Теперь квадратная плитка полностью заполнила имеющееся место. Размер розовых квадратов и есть размер подходящей нам напольной плитки. Алгоритм Евклида позволил найти наименьший общий делитель для сторон нашего изначального прямоугольника. Приложение №4Линейный алгоритм      КОНЕЦ Приложение №5Разветвляющийся алгоритм    ДА НЕТ  ДЕЙСТВИЕ 2 ДЕЙСТВИЕ 1  Приложение №6Циклический алгоритм  Цикл с предусловием    ДА НЕТ КОНЕЦ Цикл с постусловием  НАЧАЛО    СЕРИЯ ДЕЙСТВИЙ СЕРИЯ ДЕЙСТВИЙ  НЕТНЕТ   УСЛОВИЕ  ДА КОНЕЦ Приложение №7Таблица 1
Приложение №8Таблица 2
|