Что такое алгоритм в математике 5 класс?

12 ответов на вопрос “Что такое алгоритм в математике 5 класс?”

  1. XxPROxX Ответить

    Современные формы обучения, инновации в преподавании, введение новых
    технологий диктуют учителю необходимость постигать секреты мастерства, а значит,
    и совершенствовать методы обучения и воспитания учащихся.
    Исследования психологов и педагогов, опыт коллег показывают: чтобы научить
    детей самостоятельно учиться и проявлять творчество необходимо применение
    деятельностного подхода в обучении. Для этого учащихся нужно замотивировать и
    обучить их приемам и способам учебной деятельности, которые помогут сформировать
    необходимые знания, умения и навыки.
    Курс школьной математики имеет достаточно широкие возможности для применения
    различных приемов, методов и технологий. В последние годы в содержание школьного
    курса естественным образом закладывается алгоритмическая линия. Так как
    применение алгоритмов является приоритетным в моей работе, то нужно отметить
    что, между понятиями “прием” и “алгоритм” существует много общего, ни и есть
    принципиальные отличия, а именно:
    – прием – это рациональный способ работы, который состоит из отдельных
    действий, он может быть выражен в виде правил или инструкций, его можно
    перестроить и на его основе создать новый прием. Приемы деятельности допускают
    самостоятельный выбор учениками конкретных действий по решению учебных задач;
    – алгоритм – это общепонятное и однозначное предписание, которое определяет
    последовательность действий, позволяющее достичь искомый результат. Алгоритм
    предполагает жесткое выполнение шагов, а прием дает общее направление
    деятельности по решению учебных задач, не регламентируя каждый шаг. Поэтому я в
    своей работе выделяю два подхода: 1) обучение алгоритмам; 2) формирование
    приемов решения задач. Школьные задачи делятся на: алгоритмические,
    полуалгоритмические, полуэвристические и эвристические. Каждый тип задачи
    предполагает свои схемы решения, подходы, применение логики и изобретательности.
    На начальном этапе обучения математике применение алгоритмов способствует
    формированию и прочному усвоению навыков владения математическими методами.
    Также осуществляется подготовка к формированию первоначальных представлений о
    математическом моделировании. Уже в начальных классах прослеживается применение
    простейших алгоритмов выполнения арифметических операций, дети овладевают
    навыками выполнения последовательных действий. Решают задачи с составлением схем
    и кратких записей. Это можно рассматривать как пропедевтику операционного стиля
    мышления.
    Следующий уровень алгоритмической культуры учащихся – введение понятия
    алгоритма и формирование его основных свойств. Это происходит в среднем звене
    школы. Именно в этот период необходимо сочетания алгоритма и образца ответа, что
    дает возможность ученику, верно, ответить на поставленный вопрос, сопроводив его
    правильной речью. У учителя появляется возможность предлагать задачи с
    элементами творчества. А материал, предлагаемый в наших школьных учебниках,
    является хорошей базой для обучения составлению простейших алгоритмов и
    дальнейшей их записи в разных формах. Мы применяем табличную, графическую
    (блок-схема), словесную и формульную форму записи алгоритмов.
    В качестве примера, иллюстрирующего процесс алгоритмизации как средство
    обучения, можно указать на решение задач методом уравнений. Примером
    графического алгоритма является блок-схема для отыскания количества решений
    системы двух линейных уравнений с двумя неизвестными (см. Рисунок 1).
    Отыскания числа решений системы двух линейных уравнений (блок-схема)



    Рис. 1
    Графические алгоритмы
    Табличную форму алгоритма можно продемонстрировать на примере таблицы,
    составляемой для исследования функций и дальнейшего построения графиков (см.
    рис. 2).
    Исследование функции и построение графика
    Функция задана уравнением у = f(x). Исследовать
    функцию и построить ее график.
    1. Таблица исследования функции

    2. Построение графика

    Рис. 2
    Табличный алгоритм
    Пример формульного способа – последовательность нахождения компонентов при
    составлении уравнения касательной к графику той или иной функции (см. рис. 3).
    Уравнение касательной к графику функции

    Рис. 3
    Формульный способ
    Словесный алгоритм используется практически во всех правилах выполнения
    действий, например, правило сложения чисел с разными знаками (см. рис. 4).
    Алгоритм сложения чисел с разными знаками

    Рис. 4
    Словесный алгоритм
    В старших классах работа становится разнообразней и содержательней,
    появляется возможность включать упражнения разного типа и уровня сложности,
    предполагающее, что приемы деятельности могут быть разной степени сложности и
    обобщенности. Они состоят из большого числа действий, выполнение которых
    приводит к применению алгоритмов на отдельных этапах работы.
    Такой подход к преподаванию математики в основной школе определяет условия
    для формирования у учащихся навыков, позволяющих в старших классах успешно
    изучать базовый курс “Информатики и ИКТ”. Применение алгоритмов в старших
    классах, по мнению некоторых учителей, отбивает творческий подход к решению
    задач, но с другой стороны, твердое знание основных задач курса и умение их
    решать, является твердым фундаментом для активизации самостоятельной и
    творческой работы учащихся.
    Список литературы
    Кухарев Н.В. На пути к профессиональному совершенству. – М.:
    Просвещение, 1990.
    Епишева О.Б. Крутич В.И. Учить школьников учиться математике. –
    М.: Просвещение, 1990.
    Сост. Глейзер Г.Д. Повышение эффективности обучения математике в
    школе. – М.: Просвещение, 1991.
    Груденов Я.И. Совершенствование методики работы учителя
    математики. – М.: Просвещение, 1990.
    Байдак В.А. и др. Формирование алгоритмической культуры у
    учащихся. – М.: Просвещение, 1989.

  2. .:AISON:. Ответить

    Деятельность учителя
    Деятельность учащихся
    Приветствие, проверка готовности
    учащихся к уроку, отметка отсутствующих
    Приветствие
    Сегодня у нас новая тема, но ее изучение
    мы начнем с решения задачи. Дело в том, что лист,
    на котором написана тема урока, наше
    “сокровище”, разрезали на две части и спрятали в
    разных местах. Разделимся на две команды. Каждая
    команда выбирает капитана и 1 гонца, который и
    пойдет искать “сокровище” и помощника, который
    поможет собраться гонцу в дорогу.
    Формируют команды, выбирают капитана и
    гонца.
    Объясняет, что гонцы и помощники пойдут
    готовиться и команды их увидят только после
    возвращения с “сокровищем”. Объясняет, как
    гонцам и их помощникам “собраться в дорогу”:
    составить список необходимых вещей.
    Гонцы и их помощники уходят
    “собираться в дорогу”.
    Объявляет оставшимся учащимся, где
    лежат “сокровища” и ставит пред ними задачу:
    “объяснить” своим гонцам, как найти
    “сокровища”. При этом усложняет задачу одной из
    команд: их гонец не умеет читать.
    Команды на листах формата А3 пишут и
    рисуют план поиска сокровищ
    Повторение: какие виды информации вы
    использовали для инструкций своим гонцам? К
    какой классификации видов информации относятся
    эти два вида? Какие еще виды информации
    существуют в этой классификации? Какой другой
    подход к классификации видов информации вы
    знаете? Перечислите виды информации в этой
    классификации.
    Гонцы ищут сокровища. Остальные
    учащиеся повторяют пройденный материал, отвечая
    на вопросы учителя.
    Прикрепляет найденные части листа на
    доску. Что же обозначает это слово? Показывает
    третий слайд презентации.
    Гонцы приносят “сокровища”.
    Записывают тему в тетрадь.
    Вопросы: Что вы писали для гонцов? Что вы
    рисовали? Обобщить ответы словами: последовательность
    действий    .
    Так вот, алгоритм – это и есть запись
    последовательности действий. Давайте запишем
    определение.
    Записывают в тетрадь определение
    алгоритма: Алгоритм – это точное предписание
    последовательности действий, которые должны
    быть произведены для получения результата.
    Какие же способы записи алгоритмов
    существуют?
    Ответ: текстовый и графический
    А буду ли алгоритмом списки, которые
    составляли наши гонцы и их помощники? Обычно
    формулируют несколько свойств алгоритмов,
    позволяющих отличать алгоритмы от других
    инструкций.
    Нет
    Формулирует свойства алгоритма с
    пояснениями каждого.
    Записывают в тетрадь свойства
    алгоритма: дискретность, определенность,
    конечность, результативность и массовость.
    Посмотрите, у меня на слайде написан
    алгоритм открывания двери. Проверьте, всем ли
    свойствам он удовлетворяет? (Одиннадцатый
    слайд презентации    )
    Читают алгоритм, анализируют,
    высказывают мнения.
    Давайте еще раз прочитаем определение
    алгоритма. Это последовательность действий, а
    кто же выполняет эти действия?
    Человек
    Правильно. Человек – это исполнитель
    алгоритма. Скажите, человек может выполнить
    любой алгоритм?Значит, существуют и другие
    исполнители алгоритмов? Назовите их. Если
    учащиеся затрудняются с ответом, можно привести
    пример алгоритма для стиральной машины.
    Определение исполнителя алгоритма
    Нет.
    Записывают определение исполнителя:
    Исполнитель – объект, который выполняет
    действия, описанные в алгоритме
    Мы узнали много нового на сегодняшнем
    уроке. Давайте вспомним новые понятия.
    Краткое повторение изученных понятий.
    Домашнее задание
    Привести примеры алгоритмов, которые
    выполняют учащиеся на уроках, алгоритмов,
    которые выполняют машины

  3. Fordrelace Ответить

    Алгоритм Евклида
    Примеры
    Задача Тезея и алгоритм поиска чудовища
    Пример 1
    Пример 2
    Вывод
    Чтобы успешно применять современный анализ данных, нам нужно познакомиться с понятием алгоритма. Алгоритм – это основное понятие математики и современного анализа данных.
    Под алгоритмом понимается набор последовательных действий, которые направлены на достижение определенной цели.
    Алгоритмы используются не только в математике, но и во всех областях человеческой деятельности, даже часть творческой работы, например, создания скульптуры или картины, может быть алгоритмизирована, что мы наблюдаем в классических академических работах.
    Лучше всего познакомиться с понятием алгоритма на примерах.
    Мы начнем с классического примера – алгоритма Евклида.

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

    Пусть у вас имеется два натуральных числа a и b, например, 2014 и 15. Ваша цель – найти наибольший общий делитель этих чисел.
    Итак, нужно найти делитель, который должен быть, во-первых, общим для двух чисел, во-вторых, максимальным.
    Очевидно, различных задач такого типа существует столько, сколько различных пар чисел а, b.
    Нам необходимо найти последовательность действий, пригодную для всех натуральных чисел a и b.
    Попробуем осмыслить задачу и понять, как Евклид пришел к этому алгоритму.
    Очевидно, вначале он обозрел два числа и предположил, что одно из них больше другого, например, a > b.
    Далее можно предположить, что b является таким делителем.
    Вопрос: как это проверить?
    Деление – это обобщение вычитания, поэтому будем из числа a последовательно вычитать число b. Сделаем это несколько раз подряд, пока не получим 0.
    Если получили 0, то решение найдено, b и есть искомый наибольший делитель.
    Но пусть 0 не найден, а на определенном шаге у нас получается остаток – число b1 меньшее b, и мы не знаем, что делать дальше.
    Разумно сосредоточиться на этом остатке.
    У нас возникает предположение, что если есть общий делитель, то он должен находиться именно в этом остатке b1.
    Задача. Попробуйте доказать, что это действительно так!
    Поэтому мы можем продолжить наши действия с остатком b1, вычитая его из числа a, и повторить эту процедуру несколько раз.
    В итоге мы придем к заключению: либо общего делителя нет, либо найдем максимальный делитель двух чисел, процесс оборвется на конечном числе шагов.
    Мы применили эти действия к двум числам, предполагая, что a > b.
    Если это неравенство не выполняется, мы просто меняем числа местами и достигаем поставленной цели.
    Конечно, это не единственный способ нахождения максимального делителя, мы могли бы предложить простой перебор, последовательно подставляя числа от 1 до b и проверяя, делят они нацело исходные числа или нет.
    Очевидно, алгоритмы можно сравнивать по числу операций или усилий, которые вы затратили на достижение своей цели, а также на объем затраченных ресурсов.
    Анализ данных – это разложение сложного на простые элементы, натуральное число состоит из единиц, мы разделяем число на единицы, потом вновь собираем их. Также можно разбивать число на сомножители или другие элементы.
    Алгоритмы, в соответствии с которыми решение поставленных задач сводится к четырем арифметическим действиям, называются численными алгоритмами.
    Они играют важную роль в самых разнообразных областях математики.
    Например, пусть нужно решить систему двух уравнений первой степени с двумя неизвестными:


    Алгоритм решения этой системы дается формулами

    которых полностью выражен как состав действий, так и порядок их выполнения.
    В приведенных формулах предусмотрена одна и та же цепочка действий для всех задач данного типа (т. е. при любых коэффициентах ).
    Конечно, нам нужно предположить, что знаменатели не обращаются в 0.
    Можно написать последовательность действий, рассматривающую все варианты значений коэффициентов уравнений. Можно также по шагам исключить одно неизвестное, найти значение другого, как это делается в школе. Именно важен сам принцип алгоритмистики.
    Интересно, заметить, что, вообще говоря, число операций, предписываемых алгоритмом, заранее не бывает известным; оно зависит от конкретного выбора условий задачи и выясняется в процессе решения.
    В частности, так обстоит дело и в случае алгоритма Евклида, где число вычитаний, которые могут понадобиться, зависит от выбора той или иной пары чисел а, b.
    Точное число операций можно оценить и выбрать алгоритм с наименьшим числом операций или обладающий другими оптимальными свойствами, например, по количеству требуемой памяти.
    Широкое распространение численных алгоритмов обусловливается тем, что к четырем арифметическим действиям можно свести многие другие операции.
    Правда, такое сведение обычно не является исчерпывающе точным, но оно может быть осуществлено с любой наперед заданной точностью.
    Все это можно было бы иллюстрировать на примере алгоритма извлечения корня квадратного, который позволяет находить корень приближенно, но с любой наперед заданной точностью, при помощи последовательности делений, умножений и вычитаний.
    В специальной ветви современной математики (численные методы) разрабатываются аналогичные приемы сведения к арифметическим действиям и более сложных операций, как интегрирование, дифференцирование и т. д.
    В математике серия задач определенного типа считается решенной, когда для ее решения установлен алгоритм. Нахождение таких алгоритмов является естественной целью математики.
    Например, в алгебре установлены алгоритмы, которые по заданным коэффициентам алгебраического уравнения позволяют совершенно автоматически определить, сколько различных корней имеет данное уравнение (и какой кратности), и вычислить эти корни с любой наперед заданной точностью.
    Если же математик не обладает алгоритмом для решения всех задач данного типа, то хотя порою и удается решать некоторые единичные задачи этого типа, но в отдельных случаях приходится придумывать специальную процедуру, непригодную уже для большинства других случаев.

    Примеры

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

    где P является многочленом с целочисленными коэффициентами.
    Уравнения названы в честь древнегреческого математика Диофанта. Диофа?нт Александри?йский  — древнегреческий математик, живший предположительно в III веке н. э.
    Основное произведение Диофанта — Арифметика в 13 книгах, из которых сохранились только 6 первых книг из 13.
    Примеры диофантовых уравнений:


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

    Второе уравнение не имеет целочисленного решения, ибо для любого целого х легко устанавливается неравенство

    В 1901 году немецкий математик Давид Гильберт огласил список 20 трудных задач, среди них была и такая задача:
    требуется выработать алгоритм, позволяющий для любого диофантова уравнения выяснить, имеет ли оно целочисленное решение.
    Позднее эту задачу Гильберта решали многие математики, заключительное доказательство принадлежит советскому математику Ю.В.Матиясевичу (см. Ю. В. Матиясевич Диофантовость перечислимых множеств // Доклады Академии наук СССР. — 1970. — Т. 191. — № 2. — С. 279—282).
    Ю. В. Матиясевич Десятая проблема Гильберта. — М.: Наука: Физико-математическая литература, 1993. — 223 с. — (Математическая логика и основания математики; выпуск № 26). —ISBN 502014326X
    Для частного случая диофантова уравнения с одним неизвестным такой алгоритм известен.
    Рассмотрим уравнение

    с целочисленными коэффициентами.
    Если уравнение имеет целый корень , то обязательно делится на .
    Алгоритм нахождения такого корня простой: нужно перебрать все делители свободного члена приводит к цели:
    найти все делители числа (их конечное число);
    подставлять поочередно найденные делители в левую часть уравнения и вычислять численное значение ее;
    если при подстановке некоторого делителя левая часть уравнения приняла значение 0, то данный делитель является корнем уравнения
    если ни для какого делителя левая часть уравнения не обращается в 0, то уравнение не имеет целочисленных корней.
    Отметим общие свойства алгоритмов.
    Детерминированность алгоритма
    Требуется, чтобы метод вычисления можно было сообщить другому лицу в виде конечного числа указаний, как следует действовать на отдельных стадиях вычисления.
    При этом вычисления согласно этим указаниям не зависят от произвола вычисляющего лица и представляют собою определенный процесс, который может быть в любое время повторен и выполнен другим человеком.
    Алгоритм решает не индивидуальную задачу, а решает множество однотипных задач.
    Далее мы используем отрывки из увлекательной книги Б.А.Трахтенброта Алгоритмы и машинное решение задач и расскажем о некоторых интересных алгоритмах.

    Задача Тезея и алгоритм поиска чудовища

    Греческая мифология повествует о легендарном герое Тезее, который отважился проникнуть в лабиринт для того, чтобы разыскать в нем чудовищного Минотавра. Ему помогла выбраться из лабиринта Ариадна, давшая Тезею клубок ниток, один конец которых держала она сама. По мере углубления Тезея в лабиринт клубок наматывался; наматывая потом нитки, Тезей благополучно вернулся к выходу.
    Об этой древней легенде напомнила автоматическая игрушка «Мышь в лабиринте», созданная американским математиком и инженером Клодом Шэнноном.
    В одном месте специального лабиринта ставится вещь, условно именуемая куском сала, в другом — «мышь». Мышь начинает блуждать по лабиринту, делая при этом петли, пока находит «сало». Если повторно запустить «мышь» с того же места, то она уже прямо бежит к «пище», не делая петель.
    Лабиринт можно представить в виде конечной системы площадок, от которых расходятся коридоры, причем каждый коридор соединяет две площадки (такие площадки будем называть смежными), но не исключается существование таких площадок, из которых можно пройти только в один коридор (такие площадки будем называть тупиками).
    Геометрически лабиринт можно представить в виде системы точек А, В, С,… (изображающих площадки) и совокупности отрезков АВ, ВС, … (изображающих коридоры), соединяющих некоторые пары этих точек (рис. 1).

    Рисунок 1
    Будем говорить, что площадка Y достижима из площадки X, если существует путь, ведущий от X к Y через промежуточные коридоры и площадки.
    Точнее это означает, что либо X и Y—смежные площадки, либо существует последовательность площадок таких, что X и , и , и ,… и т. д. и, наконец, и Y смежны.
    Например, на, рис. 1 площадка H достижима из тупика A посредством пути АВ, ВС, CD, DE, EF, FD, DH, в то время как площадка K не достижима из А.
    Вместе с тем, если K вообще достижима из X, то она достижима и посредством простого пути, т. е. такого пути, в котором каждая площадка (а тем более и каждый коридор) проходится лишь один раз.
    В предыдущем примере пусть и не был простым, но, срезав петлю DB, EF, FD, мы получаем простой путь АВ, ВС, CD, DH.
    Предполагается, что Минотавр находится на одной из площадок лабиринта (обозначим ее через М), а Тезей, отправляясь на его поиски с площадки А, на которой его ждет Ариадна.
    Герой должен решить следующую задачу: достижим минотавра M из A или нет.
    Если Минотавр достижим, то нужно добраться до него по какому бы то ни было пути, но вернуться к Ариадне нужно уже по простому пути (не делая петель).
    Если же М не достижима, то вернуться к Ариадне.
    Различных лабиринтов может быть бесчисленное множество, а взаимное расположение в данном лабиринте площадок А и М также можно варьировать.
    Поскольку Тезею заранее ничего не известно об устройстве данного лабиринта и о местонахождении в нем Минотавра, то решение поставленной задачи мыслится в виде общего метода поисков пригодного при любом лабиринте и при любом расположении в нем площадок А и М.
    Иными словами, решение мыслится в виде алгоритма, решающего любую из задач данного типа.
    Для построения такого алгоритма рассмотрим один специальный метод поисков.
    На любой стадии процесса поиска в соответствии с этим методом приходится различать коридоры, еще ни разу не пройденные Тезеем (условно — зеленые), пройденные один раз (желтые), пройденные дважды (красные).
    Далее, находясь на какой-либо площадке, Тезей может попасть на одну из смежных площадок посредством одного из следующих ходов:
    Разматывание нити. Прохождение от данной площадки по любому зеленому коридору до смежной площадки. (При этом нить Ариадны разматывается вдоль этого коридора, который после прохождения уже считается желтым.)
    Наматывание нити. Возвращение от данной площадки по последнему пройденному желтому коридору до смежной площадки. При этом нить Ариадны, ранее размотанная вдоль этого коридора, обратно наматывается, а этот коридор уже объявляется красным.
    Предполагается, что Тезей делает какие-то пометки, позволяющие ему впоследствии различать красные коридоры от зеленых; желтые различимы тем, что по ним протянута нить Ариадны.
    Выбор того или иного хода зависит от обстановки, наблюдаемой Тезеем на той площадке, на которой он находится в данный момент.
    Эту обстановку можно охарактеризовать следующими признаками:
    Признак Минотавр. На данной площадке обнаружен Минотавр.
    Признак Петля. Через данную площадку уже протянута нить Ариадны; иными словами, от данной площадки расходятся по крайней мере два желтых коридора.
    Признак Зеленая улица. От данной площадки есть выход по крайней мере в один зеленый коридор.
    Признак Ариадна. На данной площадке находится Ариадна.
    Признак Пятый случай. Отсутствие всех предыдущих признаков.
    Метод поиска может быть теперь задан следующей схемой:
    №
    Признак
    Ход
    1 МинотаврОстановка
    2 ПетляНаматывание нити
    3 Зеленая улицаРазматывание нити
    4 АриаднаОстановка
    5 Пятый случайНаматывание нити
    Таблица 1
    Находясь на какой-нибудь площадке, Тезей делает очередной ход так: он проверяет по порядку номеров в соответствии с левым столбцом схемы, какой из перечисленных признаков имеет место; обнаружив первый такой признак, он (уже не проверяя остальные признаки) делает соответствующий ход (или остановку) из правого столбца.
    Такие ходы делаются до тех пор, пока не наступает остановка.
    Пригодность метода непосредственно вытекает из следующих трех утверждений:
    При любом взаимном расположении A и M в лабиринте после конечного числа ходов обязательно наступит остановка либо на площадке Минотавра, либо на площадке Ариадны.
    Если остановка наступила на площадке Минотавра, то Минотавр достижим. Более того, в этом случае нить Ариадны оказывается протянутой по простому пути, ведущему от А до М; наматывая нить, Тезей может теперь вернуться по этому пути к Ариадне.
    Если остановка наступила на площадке. Ариадны, то Минотавр не достижим.
    Прежде чем доказывать эти утверждения, покажем на двух примерах, как работает метод.

    Пример 1

    Пусть с площадки А лабиринта (рис. 1) начинается поиск Минотавра, который находится в F.
    Процесс поиска в соответствии с нашим методом удобно изобразить посредством схемы (в силу произвола при выборе зеленого коридора — это лишь одна из возможных схем), представленной на таблице 2.
    №
    Каким признаком руководствуется Тезей
    Ход
    Пройденный коридор
    Цвет коридора после его прохождения
    1 Зеленая улицаРазматывание нитиABЖелтый
    2 Зеленая улицаРазматывание нитиBCЖелтый
    3 Зеленая улицаРазматывание нитиCDЖелтый
    4 Зеленая улицаРазматывание нитиDHЖелтый
    5 Зеленая улицаРазматывание нити HJЖелтый
    6 Пятый случайНаматывание нитиJHКрасный
    7 Пятый случайНаматывание нити HDКрасный
    8 Зеленая улицаРазматывание нити DBЖелтый
    9 ПетляНаматывание нити BDКрасный
    10 Зеленая улицаРазматывание нити DFЖелтый
    11 МинотаврОстановка …,,,
    Таблица 2
    Мы видим, что в данном случае Минотавр достижим. Выделив в предпоследнем столбце те из коридоров, которые остались желтыми (в соответствии с показаниями последнего столбца), получим следующий простой путь, ведущий от A к F:
    АВ, ВС, CD, DF.

    Пример 2

    Если же поиск начинается с площадки K, то процесс поиска можно изобразить в схеме, представленной на таблице 2.
    Мы видим, что в этом случае Минотавр не достижим.
    Перейдем теперь к доказательству утверждений 1—3.
    Доказательство утверждения 1.
    Покажем методом индукции по числу ходов Тезея, что на любом этапе процесса поиска возникает следующая альтернатива (т. е. имеет место один из следующих двух случаев, взаимно исключающих друг друга):
    №
    Каким признаком руководствуется Тезкй
    Ход
    Пройденный коридор
    Цвет коридора после прохождения
    1 Зеленая улицаРазматываниеKNЖелтый
    2 Зеленая улицаРазматываниеNLЖелтый
    3 Зеленая улицаРазматываниеLMЖелтый
    4 Зеленая улицаРазматываниеMNЖелтый
    5 ПетляНаматывание NMКрасный
    6 Пятый случайНаматываниеMLКрасный
    7 Пятый случайНаматывание LNКрасный
    8 Пятый случайНаматывание NKКрасный
    9 АриаднаОстановка …,,,
    Таблица 3
    a) В лабиринте нет желтых коридоров; при этом Тезей находится на площадке А (Ариадны).
    b) В лабиринте имеются желтые коридоры, причем они, будучи рассмотрены в том порядке, в каком они были пройдены Тезеем, образуют путь, ведущий от А до площадки, на которой находится Тезей.
    Вместе с тем будет обнаружено, что Тезей никогда не проходит по красному коридору.
    Высказанные положения являются очевидными для начала процесса, когда Тезей еще находится на площадке А и никакой коридор еще не пройден (все коридоры — зеленые). Предположим теперь, что указанные альтернативы справедливы после (n—1)-го хода и покажем, что тогда они справедливы и после n-го хода (разумеется, если только (n— 1)-й ход еще не привел к остановке).
    Пусть после (n— 1)-го хода имеет место случай а.
    Тогда очередной ход может быть либо продвижением по зеленому коридору от А до некоторой смежной площадки K (после n-го хода возникает случай б с единственным желтым коридором AK), либо остановкой на площадке А (после n-го хода сохраняется случай a). Допустим теперь, что после (n— 1)-го хода имеет место случай б с s желтыми коридорами, образующими путь .
    В зависимости от того, каким признаком руководствуется Тезей при выборе очередного n-го хода, после n-го хода имеются следующие возможности:
    Минотавр. Происходит остановка на площадке K с сохранением прежних желтых коридоров (случай б после n-го хода).
    Петля. Тезей наматывает нить, т. е. отступает по желтому коридору , который теперь уже становится красным. Желтый путь укорачивается на один коридор; если число s коридоров в прежнем пути было больше 1, то после и-го хода будет иметь место случай б с (s—1) желтыми коридорами; если же s =1, то будет иметь место случай а.
    Зеленая улица. Тезей разматывает нить, т. е. продвигается по зеленому коридору, который теперь уже становится желтым. Имеет место случай б с s+1 желтым коридором.
    Ариадна. Этим признаком Тезей не будет руководствоваться, ибо если он даже и вернется на площадку Ариадны, идя по желтому пути   (т. е. если K = А), то в соответствии с принятым методом поиска он должен руководствоваться признаком петля.
    При отсутствии первых четырех признаков происходит наматывание нити, которое приводит так же, как и в случае петли, к случаю а (при s = 1) или к случаю б (при s > 1).
    Таким образом, полностью установлена упомянутая выше альтернатива, а также выяснено, что по каждому коридору Тезей проходит не более двух раз (по красному он никогда не проходит).
    Поскольку, кроме того, число всех коридоров в лабиринте конечно, то и последовательность ходов должна быть конечной; но эта последовательность может оборваться только при остановке Тезея на площадке Минотавра или на площадке Ариадны.
    Доказательство утверждения 2. В случае остановки на площадке Минотавра факт достижимости очевиден, причем нить Ариадны протянута вдоль желтого пути, существование которого было установлено выше.
    Отсутствие петель в нити обеспечивается тем, что каждый раз, когда в процессе блуждания Тезей обнаруживает петлю, он возвращается обратно и тем самым ликвидирует ее.
    Доказательство утверждения 3. Заметим, что в случае остановки на площадке Ариадны
    каждый коридор лабиринта либо пройден дважды (красный коридор), либо ни разу не пройден (зеленый коридор); иными словами, нить полностью намотана (желтых коридоров в лабиринте нет).
    все коридоры, выходящие из А, являются красными, ибо в соответствии с принятым соглашением признак Ариадна учитывается лишь в том случае, когда предшествующие ему в схеме три признака, среди которых и зеленая улица, не имеют места.
    Предположим теперь от противного, что Минотавр достижим и пусть   —путь, ведущий от А к М.
    Первый коридор в этом пути является красным, ибо он выходит из А, последний же является зеленым, ибо Тезей в своих поисках до Минотавра не добрался. Пусть — первый зеленый коридор в этой последовательности.
    Таким образом, к примыкают зеленые и красные коридоры.
    Рассмотрим теперь последнее прохождение Тезея через площадку ; оно, очевидно, произошло по одному из красных коридоров, примыкающих к
    Однако последнего быть не может, ибо из выходит зеленый коридор .
    Поэтому приходится допустить, что последнее прохождение через было связано с обнаружением петли. Однако это немедленно приводит к противоречию, чем и завершается доказательство утверждения 3.
    Именно, если бы в была обнаружена петля, то это означало бы, что из нее выходят по крайней мере два желтых коридора; сделав свой очередной ход, Тезей превратил бы один из этих желтых коридоров в красный, оставшийся же желтый коридор должен быть обязательно пройден впоследствии повторно, ибо желтых коридоров не должно оставаться; тогда же будет пройдена еще раз площадка .
    Это противоречит допущению, что рассматривается последнее прохождение через .
    Сделаем теперь следующее замечание. В предложенном нами предписании для поиска пути допускается известный элемент случайности.
    Именно, при условии зеленая улица очередной ход не определен однозначно, поскольку с данной площадки могут оказаться выходы в несколько зеленых коридоров, а наше предписание не предусматривает, какой из них нужно выбрать, точнее — оно допускает произвольный случайный выбор одного из них.
    Тем самым нарушается свойство детерминированности, о котором в предыдущем параграфе говорилось, что оно присуще всем алгоритмам.
    Этот элемент случайности можно устранить (и тем самым превратить рассмотренное предписание в алгоритм) хотя бы соглашением, что при наличии нескольких зеленых коридоров выбирается коридор по некоторому правилу.
    Например, выйдя на площадку, Тезей начинает ее обходить по часовой стрелке до появления первого зеленого коридора и далее следует по нему, или же каким-нибудь другим соглашением.

    Вывод

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

  4. Shaktikus Ответить

    Цель урока: Формирования у учащихся правильного понимания алгоритмов, их свойств, видов и практических навыков составления алгоритмов.
    Задачи урока:
    Дидактические: Обеспечить условия:
    для изучения и закрепления основных понятия по теме;
    для усвоения, закрепления темы.
    Воспитательные: Обеспечить условия:
    для воспитания чувства коллективизма и взаимопомощи, культуры общения;
    для критического отношения к своему труду, умение оценивать его.
    Развивающие: Обеспечить условия:
    для развития мыслительной деятельности учащихся, умения анализировать, сравнивать, обобщать и делать выводы;
    для развития самостоятельности, логического изложения мыслей.
    Демонстрационный материал к уроку:
    Мультимедийная презентация
    Портрет Мухаммеда Бен Муссы аль-Хорезми.

    Ход урока

    Организационный момент. (2 мин.)
    Актуализация знаний. Постановка учебной задачи. (3 мин.)
    Изложение нового материала. (30 мин.)
    Закрепление нового материала (10 мин.)

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

    Появление алгоритмов связывают с зарождением математики.
    Более 1000 лет назад (825 г.)ученый из города Хорезма Абдулла (или Абу Ждафар) Мухаммед бен Мусса аль-Хорезми создал книгу по математике, в тором описал способы выполнения арифметических действий над многозначными числами.
    Алгоритм – описание последовательности действий, исполнение которых приводит к решению поставленной задачи за конечное число шагов.
    Алгоритм — понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящих от исходных данных к искомому результату.

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

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

    Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
    Пример: Алгоритм «Зарядка»
    Потянитесь, лежа в постели.
    Сядьте на кровати, поставив ноги на пол.
    Нагнитесь вперед, пытаясь достать руками пальцы ног.
    Выгните спину дугой.
    Сосчитайте до 10.
    Вернитесь в исходное положение.
    При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий.
    Пусть, например, необходимо найти значение следующего выражения:
    у=2а-(х+6).
    Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:
    Ввести значения а и х.
    Сложить х и 6.
    Умножить а на 2.
    Вычесть из 2а сумму (х+6).
    Вывести у как результат вычисления выражения.
    При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.

    Виды алгоритма

    Линейный алгоритм – это такой, в котором все операции выполняются
    последовательно одна за другой.
    Пример: Алгоритм посадки дерева.
    Выкопать в земле ямку;
    Опустить в ямку саженец;
    Засыпать ямку с саженцем землей;
    Полить саженец водой.
    Разветвляющийся алгоритм – это алгоритм в котором выполняется либо одна, либо другая группа действий в зависимости от истинности или ложности условия.
    Полная форма
    Если , то , иначе
    Неполная форма
    Если , то

    Пример: Если на улице дождь, то останемся дома, а если нет то идем гулять.

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

    Цикл с известным числом повторений

    Цикл с известным числом повторений часто называют «циклом ДЛЯ»
    Пример: Алгоритм «Упражнение для глаз»
    Возьмите карандаш.
    Установите его в исходное положение у кончика носа
    Повторите 10 раз, следя за движение карандаша:
    Переместите карандаш на расстояние вытянутой руки;
    Верните карандаш в исходное положение
    Положите карандаш
    Конец алгоритма

    Цикл с постусловием

    Цикл с неизвестным числом повторений, в тором выход из цикла осуществляется при выполнении условия, принято называть «циклом с постусловием» или «циклом ПРИ»
    Алгоритм «Пульс»
    Удобно положите левую руку ладонью вверх.
    Два пальца правой руки положите на запястье левой руки.
    Заметьте положение секундной стрелки
    Сосчитайте очередной удар
    Посмотрите на часы
    Если секундная стрелка прошла полный круг, то закончите действия, иначе перейдите к п.4
    Конец алгоритма

    Цикл с предусловием

    Цикл с известным числом повторений, в котором цикл продолжается, пока выполняется условие, принято называть «циклом с предусловием» или «циклом ПОКА»
    Алгоритм «Бочка»
    Подойдите к бочке
    Если бочка неполна (есть место для воды) , то перейдите к п.3, иначе конец алгоритма.
    Наберите ведро воды
    Вылейте ведро в бочку
    Перейдите к п.2.
    Конец алгоритма

    Задания для закрепление материала

    Последовательность действий ученика 6 класса Васи: «Если Павлик дома, будем решать задачи по математике. В противном случае следует позвонить Марине и вместе готовить доклад по биологии. Если же Марины нет дома, то надо сесть за сочинение.»
    Последовательность действий ученика 6 класса Васи: «Если Павлик дома, будем решать задачи по математике. В противном случае следует позвонить Марине и вместе готовить доклад по биологии. Если же Марины нет дома, то надо сесть за сочинение.»
    Составить блок-схему действий школьника, которому перед вечерней прогулкой следует выполнить домашнее задание по математике.

  5. Bugrinn Ответить

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

    Алгоритм Евклида является универсальным способом, который позволяет вычислять наибольший общий делитель двух положительных целых чисел.
    Описание алгоритма нахождения НОД делением:
    1. Большее число делим на меньшее
    2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла). Если есть остаток, то большее число заменяем на остаток от деления.
    3. Переходим к пункту 1.
    Найти НОД для 40 и 15.
    40/15 = 2 (остаток 10)
    15/10 = 1 (остаток 5)
    10/5 = 2 (остаток 0). Конец: НОД – это делитель. НОД (40, 15) = 5
    Описание алгоритма нахождения НОД вычитанием:
    1. Из большего числа вычитаем меньшее
    2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла)
    3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания
    4. Переходим к пункту 1
    Пример:
    Найти НОД для 40 и 15.
    40 – 15 = 25
    25 – 15 = 10
    15 – 10 = 5
    10 – 5 = 5
    5 – 5 = 0 Конец: НОД – это уменьшаемое или вычитаемое. НОД (40, 15) = 5

    Решето Эратосфена

    Решето Эратосфена — это алгоритм нахождения простых чисел до заданного числа n. При исполнения данного алгоритма постепенно отсеиваются составные числа, кратные простым, начиная с числа 2.
    Описание алгоритма:
    1. Нужно выписать подряд все целые числа от двух до n (2, 3, 4, …, n)
    2. Пусть переменная p изначально равна двум — первому простому числу
    3. Нужно зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …)
    4. Найти первое незачеркнутое число в списке, большее, чем p, и присвоить значению переменной p это число
    5. Повторять шаги 3 и 4, пока это возможно
    Рисунок 2

    Алгоритм при решении уравнений

    3.3.1 Алгоритм нахождения неизвестного слагаемого
    Для того чтобы вычислить неизвестное слагаемое, необходимо из суммы вычесть известное слагаемое
    3.3.2 Алгоритм нахождения неизвестного уменьшаемого
    Для того чтобы вычислить неизвестное уменьшаемое, необходимо к разности прибавить вычитаемое
    3.3.3 Алгоритм нахождения неизвестного вычитаемого
    Для того чтобы вычислить неизвестное вычитаемое, необходимо из уменьшаемого вычесть разность
    3.3.4 Алгоритм нахождения неизвестного множителя
    Для того чтобы вычислить неизвестный множитель, необходимо произведение разделить на известный множитель
    3.3.5 Алгоритм нахождения неизвестного делимого
    Для того чтобы вычислить неизвестное делимое, необходимо частное умножить на делитель
    3.3.6 Алгоритм нахождения неизвестного делителя
    Для того чтобы вычислить неизвестный делитель, необходимо делимое разделить на частное

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

    3.4.1 Алгоритм сложения двух отрицательных чисел
    1. Определить, являются ли слагаемые отрицательными числами
    2. Сложить модули слагаемых
    3. Поставить перед полученной суммой знак «минус»
    3.4.2 Алгоритм сложения чисел с разными знаками
    1. Определить модуль какого из чисел больше
    2. Вычесть из большего модуля меньший
    3. Поставить перед полученным числом знак того слагаемого, модуль которого больше
    3.4.3 Алгоритм умножения чисел с разными знаками
    1. Определить, являются ли умножаемое и множитель отрицательными числами.
    2. Перемножить модули этих чисел
    3. Поставить перед полученным произведение знак «минус»
    3.4.4 Алгоритм деления отрицательного числа на отрицательное число
    1. Определить, являются ли делимое и делитель отрицательными
    2. Разделить модуль делимого на модуль делителя
    3.4.5 Алгоритм деления чисел с разными знаками
    1. Определить, являются ли делимое и делитель числами с разными знаками
    2. Разделить модуль делимого на модуль делителя
    3. Поставить перед полученным числом знак «минус»

Добавить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *