Развитие понятия «Алгоритм»
презентация к уроку

Слайд 2

Цели и задачи проекта Цель проекта – это ознакомление с историей развития понятия «алгоритм». В наш век информационных технологий люди ежедневно выполняют свод инструкций, созданных до них другими людьми, ведь техника требует точного исполнения ряда действий. Важная задача в современном мире – это уметь пользоваться алгоритмами, быстро схватывать и изменять уже существующие правила в соответствии со сложившейся ситуацией. Алгоритмы формируют приёмы логического мышления, способствуют воспитанию аккуратности и точности. Алгоритм является одним из тех понятий, которое изучается на уроке математики и информатики в каждой школе. Мы думаем, что высказывание Михаила Васильевича Ломоносова: «Народ, не знающий своего прошлого, не имеет будущего» можно вполне отнести и к научной деятельности человека.

Слайд 3

Авторы : Ставрати Олег Геннадьевич Романюк Андрей Павлович Руководитель: Каверина Ирина Александровна Развитие понятия «Алгоритм»

Слайд 4

«Алгоритм» в повседневной жизни В повседневной жизни каждый человек сталкивается с необходимостью решения задач разной сложности. Некоторые требуют длительных размышлений для поиска решений, другие привычны и решаются автоматически. Многие наши действия регламентированы определенным алгоритмом - чёткой системой инструкций. Например, при входе в магазин "Универсам" следуем алгоритму: взять корзину, пройти в торговый зал, заполнить корзину продуктами, оплатить покупку в кассе, переложить продукты в сумку, вернуть корзину, покинуть магазин. И, например, если мы никогда раньше не пекли торт, то, получив рецепт (алгоритм) его приготовления, постараемся выполнить всё в указанной последовательности.

Слайд 5

Алгоритм - это точное предписание исполнителю совеpшить определённую последовательность действий для достижения поставленной цели за конечное число шагов. Алгоритм одно из самых основных понятий вычислительной математики. Это понятие возникло в связи с поисками общих методов решения однотипных задач. Основные свойства алгоритма: Дискретность (прерывность) - разбиение алгоритма на шаги; Результативность - получение из исходных данных результата за конечное число шагов; Массовость - пригодность для решения не какой-либо одной, а целого класса задач; Детерминированность (определённость) - выполнение команд алгоритма в строго определённой последовательности; Выполнимость и понятность - каждый шаг алгоритма должен быть понятен исполнителю. И всё же алгоритм – это одно из основных понятий математики. Алгоритмами являются, например, известные из начальной школы правила сложения, вычитания, умножения и деления столбиком. Вообще, под алгоритмом понимается всякое точное предписание, которое задаёт вычислительный процесс (называемый в этом случае алгоритмическим).

Слайд 6

Найденные археологами глиняные таблички времён Хаммурапи (XVIII в. до н.э.) с теоремой Пифагора и её применениями, а также ещё более древние таблички с вычислением обратных чисел свидетельствуют о реальном появлении алгоритмов у древних шумеров. В Древнем Китае (213 г. до н.э. ) трактат «Математика в девяти книгах» содержал уже много различных алгоритмов. В индийских «Ведах» ( VI в. до н.э. ) , уже есть алгоритмы нахождения арифметических и геометрических прогрессий. Б олее 4000 лет тому назад в Египте из папируса Ахмеса следует, что у египтян существовал алгоритм представления любой положительной рациональной дроби в виде суммы простых дробей, т.е. дробей вида 1/n, где n – натуральное число. Истоки П оявление алгоритмов восходит к глубокой древности .

Слайд 7

Алгоритм Евклида Первым дошедшим до нас алгоритмом в его интуитивном понимании –последовательности элементарных действий, решающих поставленную задачу, считается алгоритм Евклида. Это алгоритм нахождения наибольшего общего делителя двух чисел. Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже у Аристотеля. Первое описание алгоритма находится в «Началах» древнегреческого математика Евклида (около 300 лет до н. э. ), что делает его одним из старейших численных алгоритмов, используемых в наше время. «Начала» - это главный труд Евклида, посвящённый систематическому построению геометрии. Считается вершиной античной геометрии и античной математики вообще. Евклид

Слайд 8

Аль-Хорезми Слово «алгоритм» происходит от имени великого среднеазиатского математика, астронома, историка, географа - одного из крупнейших учёных средневековья Абу Абдаллах Мухаммеда ибн Муса аль-Хорезми (783–850 гг.) Аль-Хорезми написал трактат по арифметике, который назывался «Об индийском счёте». Для того времени эта книга оказалась таким же «усилителем интеллекта», каким в двадцатом веке стал компьютер. Им были разработаны правила четырёх арифметических действий над многозначными числами. В Европе эти правила стали называть алгоритмами от латинской формы написания имени автора – Alchorismi или Algorithmi. Переводы арифметического трактата Аль-Хорезми с арабского содержали описание индийской позиционной системы счисления и искусства счета в этой системе. Примером может служить алгоритм сложения «столбиком». Он был первым, описавшим понятие, известное сейчас как “алгоритм”, которое означает “постоянный процесс расчета”. Памятник Абу Абдаллах Мухаммеда ибн Муса аль-Хорезми в г. Хива, Хорезмская область, Узбекистан

Слайд 9

В 1684 году немецкий философ, математик, физик, языковед Готфрид Лейбниц впервые использовал слово «алгоритм». Пользовался словом «алгоритм» и швейцарский математик, механик, физик, астроном Леонард Эйлер. Понимание Эйлером алгоритма как синонима способа решения задачи уже очень близко к современному. Древнерусское сочинение «Счётная мудрость» (1691 г.). восходит к ещё более древним рукописям XVI в. По ним можно проследить, как знание арабских цифр и правил действий с ними постепенно распространялось на Руси. Таким образом, слово «алгоритм» понималось первыми русскими математиками так же, как и в Западной Европе. Упоминания «алгоритма» в истории

Слайд 10

Потребность в определении понятия алгоритма На протяжении многих веков понятие алгоритма связывалось с числами и простыми действиями над ними, да и сама математика была, по большей части, наукой о вычислениях. Алгоритмы представлялись в виде математических формул. Порядок элементарных шагов алгоритма задавался расстановкой скобок, а сами шаги заключались в выполнении арифметических операций. Вычисления были громоздкими и трудоёмкими. У математиков не возникала потребность в строгом определении понятия алгоритма. В 1920-х годах задача точного определения понятия алгоритма стала одной из центральных проблем математики. В то время существовало две точки зрения на математические проблемы: Все проблемы алгоритмически разрешимы, но для некоторых алгоритм еще не найден. Есть проблемы, для которых алгоритм вообще не может существовать. Идея о существовании алгоритмически неразрешимых проблем оказалась верной, но для того, чтобы ее обосновать, необходимо было дать точное определение алгоритма. Возникла теория алгоритмов, в которую вошли труды математиков: К.Гедель, К.Черч, С.Клини, А.Тьюринг, Э.Пост, А.Марков, А.Колмогоров. Точное определение понятия алгоритма дало возможность доказать алгоритмическую неразрешимость многих математических проблем.

Слайд 11

Английский учёный Алан Тьюринг предложил модель такого исполнителя, получившую название «машина Тьюринга». Его «машина» является универсальным исполнителем обработки любых символьных последовательностей в любом алфавите. Одновременно с Тьюрингом (1936-1937 гг.) другую модель алгоритмической машины описал Эмиль Пост. Машина Поста работает с двоичным алфавитом и несколько проще в своем «устройстве». Машина Поста является частным случаем машины Тьюринга. Однако именно работа с двоичным алфавитом представляет наибольший интерес, поскольку современный компьютер тоже работает с двоичным алфавитом. На основании моделей Тьюринга и Поста учёные пришли к выводу о существовании алгоритмически неразрешимых задач . В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.

Слайд 12

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

Слайд 13

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

Слайд 14

Британская операция «Ультра» В этот же период Британия объявила старт операции «Ультра», целью которой являлось прослушивание разговоров немецких лётчиков и их расшифровка. Данным вопросом занимался расположенный в Блетчли-парке (Лондон) отдел правительственной Школы кодов и шифров. В штат криптоаналитиков набирались не кадровые разведчики, а специалисты самого широкого профиля: математики, лингвисты, шахматисты, египтологи, чемпионы по решению кроссвордов. В этот отдел попал и математик Алан Тьюринг.

Слайд 15

Тьюринг против «Энигмы» Отделу Тьюринга было поручено задание: работа с зашифрованными текстами, создаваемыми устройством «Энигма» - машиной, запатентованной в Голландии в 1917 году и изначально предназначенной для защиты банковских операций. Именно эти модели активно использовал Вермахт для передачи радиограмм в операциях, проводимых морским флотом и авиацией. Шифры «Энигмы» к началу Второй мировой войны являлись самыми сильными на планете. Считалось даже, что взломать их практически невозможно. Чтобы понять закодированный текст, требовалось обзавестись такой же машиной, знать ее первоначальные настройки, замкнуть определенным образом буквы в коммуникационной панели, и все это запустить в обратном направлении. При этом стоило иметь в виду, что принципы кодирования и ключи менялись раз в сутки. Шифровальщики Вермахта старались максимально усложнить процедурами передачи сам криптоанализ: длина сообщений не превышала 250 символов, и передавались они группами по 3-5 букв. Напряженная работа шифровальщиков под руководством Тьюринга увенчалась успехом: было создано устройство, способное расшифровать сигналы «Энигмы». Кроме математических ухищрений, в качестве подсказок использовались одни и те же стереотипные фразы, с помощью которых общались немцы, а также любые повторяющиеся тексты. Если подсказок было недостаточно, то противника на них провоцировали. К примеру, демонстративно минировали определенный участок моря, а потом прослушивали высказывания немцев по данному поводу.

Слайд 16

В 1940 году была создана криптоаналитическая машина Алана Тьюринга «Бомба», представляющая собой огромный шкаф (вес - одна тонна, передняя панель - 2 х 3 метра, 36 групп роторов на ней). Со временем было установлено более двух сотен таких машин, что позволяло расшифровывать около 2-3 тысяч сообщений в день. «Энигма» и другие шифровальные германские машины были взломаны, союзники получили возможность быть в курсе бесперебойного потока ценнейших разведданных. Немцы больше года не догадывались о существовании «Бомбы», а обнаружив утечку информации, приложили огромные усилия для максимального усложнения шифров. Тьюринг легко справился с новой проблемой, и уже через полтора месяца англичане получили доступ к вражеской информации. Абсолютная надежность шифра в годы войны не вызывала никаких сомнений у немцев, до самого конца искавших причины утечки ценной информации где угодно, только не в «Энигме». Раскрытие кода «Энигмы» кардинально изменило ход Второй мировой войны. Ценные сведения помогли не только обезопасить Британские острова, но и провести соответствующую подготовку к масштабным операциям на континенте, планируемым германской стороной. Успех британских шифровальщиков стал важным вкладом в победу над нацизмом, а Тьюринг в 1946 году получил в награду орден Британской империи.

Слайд 17

Также, ещё существует специализированная учебная программа симулирующая машину Тьюринга

Слайд 18

Современный взгляд на алгоритмизацию Двадцатый век в области науки и техники принёс человечеству много крупных достижений: радио, звуковое кино, телевидение, атомная энергия, космические полеты, электронные вычислительные машины, компьютеры. Но не всем известно, что крупнейшим достижением науки ХХ в. является теория алгоритмов – новая математическая дисциплина. Теория электронных вычислительных машин, теория и практика программирования, а также и математика не могут обойтись без неё. С развитием вычислительной техники и теории программирования возрастает необходимость построения новых экономичных алгоритмов, изменяются способы их построения, способы записи алгоритмов на языке, понятном исполнителю. Особый тип исполнителя алгоритмов – компьютер, поэтому необходимо создавать специальные средства, позволяющие, с одной стороны, разработчику в удобном виде записывать алгоритмы, а с другой – дающие компьютеру возможность понимать написанное. Такими средствами являются языки программирования или алгоритмические языки. В настоящее время понятие алгоритма - одно из фундаментальных понятий науки «информатика».

Слайд 19

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

Слайд 20

Вывод Понятие «алгоритм» вошло в наш обиход еще в IX веке и до сих пор является фундаментом для любых действий, как в точных науках, так и в обычной жизни. Это понятие входит в любую сферу деятельности человека. Способность выделять алгоритмическую сущность явлений и возводить методы - очень важно для человека любой специальности. Понятие алгоритма значимо не только практическим применением, но и имеет весомое общеобразовательное значение. Навыки алгоритмического мышления помогают формированию определенного стиля культуры человека, основу которого составляют: целеустремленность, сосредоточенность, объективность, точность, логичность, последовательность в планировании и исполнении своих действий, лаконичность в выражении собственных идей, быстрое ориентирование в стремительном потоке информации. Понятие алгоритма является не только центральным понятием теории алгоритмов, не только одним из главных понятий математики вообще, но одним из главных понятий современной науки. Более того, сегодня, с наступлением эры информатики, алгоритмы становятся одним из важнейших факторов цивилизации.

Слайд 21

Литература : Байдак В.А. и др. Формирование алгоритмической культуры у учащихся. – М.: Просвещение, 1989. 2) Одинец В.П. Зарисовки по истории компьютерных наук . Учебное издание - Редакционно-издательский отдел К оми государственного педагогического института , 2011. Интернет ресурсы: http://files.school-collection.edu.ru/ https://sibac.info/studconf/ http://letopisi.org/ http://fb.ru/ http://www.krugosvet.ru/