Лекции 8




Скачать 233.98 Kb.
НазваниеЛекции 8
страница1/3
Дата публикации21.07.2013
Размер233.98 Kb.
ТипДокументы
zadocs.ru > Математика > Документы
  1   2   3
ТЕМА ЛЕКЦИИ 8.Разработка алгоритмов и программ с элементами деловой игры. Игры «Группа разработчиков», «Сценка»,«Улитка», «Японский рисунок» , «Спортлото»,. (лекция- 4 часа)

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

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

Для этого, путем комбинирования самостоятельной и коллективной работы студентов вырабатываются навыки взаимопомощи при программировании, что способствует быстроте усвоения материала. Игра должна быть интересна и охватывать всех студентов.
Игра «Группа разработчиков». Все студенты делятся на три группы. Каждая группа получает задание написать алгоритм нахождения максимума (минимума), алгоритм, сортирующий элементы массива по возрастанию (по убыванию), алгоритм, суммирующий элементы массива. После написания алгоритмов группы студентов заменяют одного из своих разработчиков представителем другой группы и совмещают два составленных алгоритма. После второго обмена представителями в каждой группе должны получиться одинаковые алгоритмы, выполняющие три поставленные изначально задачи.
Кроме того, принцип работы алгоритма на перестановку элементов массива в порядке возрастания, поиска максимального (минимального) элемента удобно продемонстрировать с помощью ролевого исполнения алгоритма, примером которого является игра «Сценка».
Игра «Сценка». Выбирается N количество студентов в зависимости от количества переменных в алгоритме. Каждому студенту раздается соответствующая роль и его начальное значение: переменная Счетчик (1 ученик), ячейки массива (количество студент зависит от размерности массива), переменная Максимум (1 студент), переменная Минимум (1 ученик), переменная Сумма (1 студент), а также ученик, записывающий на доске код программы. Задание: найти сумму максимального и минимального элементов массива. При этом на доске чертится массив из N элементов, отводится место для записи значения переменных. Далее студенты проигрывают алгоритм по ролям: если переменная счетчик увеличивает свое значение, то студент, отвечающий за соответствующую ячейку массива, должен сказать значение своей ячейки или сравнить его со значением соседней ячейки и изменить его, если это соответствует алгоритму решения задачи, который один из учащихся записывает на доске. При этом за каждый правильный шаг начисляется бонус, а за неверный отнимается.
Немаловажной составляющей успешного решения алгоритмических задач является частично самостоятельная работа студента с возможностью проверить результаты своей деятельности.
Игра «Улитка». Заранее готовиться плакат с изображением пустого массива в виде спирали размерностью N. Студенты по очереди бросают кубики, при этом выпавшие числа последовательно записывают в ячейки массива. Когда массив будет заполнен, студент получают задание отсортировать массив в порядке возрастания (убывания) таким образом, чтобы каждое число повторялось в массиве только один раз. При этом после написания каждого элемента программы один из студентов проверяет его, внося при этом нужные коррективы в рисунок на плакате.
Зависимость качественного результата совместной работы студента от эффективного труда каждого студента положительно влияет на ответственный подход студента к решению алгоритмической задачи.
Игра «Японский рисунок». На доске имеется поле, размерностью N×M клеток. Каждый учащийся получает многомерный массив, который содержит значения только 1 и 0. Задача каждого студента заключается в том, чтобы составить верный алгоритма подсчета количества нулей и единиц в своем массиве, и зарисовать на доске клетку, координаты которой по горизонтали и по вертикали равны соответственно количеству нулей и единиц в своем массиве. Если все подсчеты будут выполнены правильно, то из зарисованных клеток на доске сложится определенный рисунок.
Мотивационную составляющую решения любой алгоритмической задачи определяет правильно поставленная цель выполнения работы и ее дальнейшее применение.
Игра «Спортлото». Студенты получают задание написать алгоритм, который бы обнулял те стоки многомерного массива N×M, которые содержат указанное число. Затем каждый студент получает свой лотерейный билет (файл, содержащий многомерный массив N×M). Учащиеся по очереди вытягивают бочонки с номерами, которые последовательно вводят в написанную ранее программу. Таким образом, победителем станет тот студент, у которого раньше других будут вычеркнуты все строки его лотерейного билета, т.е. обнуляться все строки многомерного массива.
Разработанные игры «Группа разработчиков», «Сценка», «Улитка», «Японский рисунок», «Спортлото» могут применяться при изучении структурного типа данных массив .
Вывод: таким образом, применение игровых форм в обучении основам алгоритмизации и программирования способствует повышению эффективности традиционных методов обучения за счет усиления доли исследовательских, информационно-поисковых методов работы с информацией, а также стимулирования познавательного интереса и творческой активности студентов.

ТЕМА ЛЕКЦИИ 9.Методы решения трансцендентных уравнений с одним неизвестным Метод дихотомии (бисекций).. Метод хорд. Метод Ньютона (касательных). Метод секущих. Метод простых итераций ( лекция -2 часа)

Пусть задана непрерывная функция f(x). Требуется найти корни уравнения f(x) = 0 численными методами – это и является постановкой задачи. Численное решение уравнения распадается на несколько подзадач:

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

  • единственный корень;

  • бесконечное множество решений;

  • корней нет;

  • имеется несколько решений, как действительных, так и мнимых (например, для полинома степени n). Корни четной кратности выявить сложно.

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

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

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

Метод дихотомии (бисекций).

Иначе называется методом половинного деления. Пусть задан начальный интервал [x0, x1], на котором f(x0)f(x1) ≤ 0 (т.е. внутри имеется не менее чем один корень). Найдем x2 = ½ (x0 + x1) и вычислим f(x2). Если f(x0)f(x2) ≤ 0, используем для дальнейшего деления отрезок [x0, x2], если > 0 – используем для дальнейшего деления отрезок [x1, x2], и продолжаем деление пополам.

Итерации продолжаются, пока длина отрезка не станет меньше 2ξ ­– заданной точности. Тогда середина последнего отрезка даст значение корня с требуемой точностью. В качестве иного критерия можно взять | f(x)| ≤ ξy.

Скорость сходимости метода невелика, однако он прост и надежен. Метод неприменим к корням четной кратности. Если на отрезке несколько корней, то заранее неизвестно, к какому из них сойдется процесс.

Если на заданном интервале предполагается несколько корней, то существует возможность последовательно исключать найденные корни из рассмотрения. 01Для этого воспользуемся вспомогательной функцией , где – только что найденный корень. Для функций f(x) и g(x) совпадают все корни, за исключением (в этой точке полюс функции g(x)). Для достижения требуемой точности рекомендуется грубо приблизиться к корню по функции g(x), а затем уточнить его, используя f(x).

Метод хорд.

Идея метода проиллюстрирована рисунком. Задается интервал [x0, x1], на котором f(x0)f(x1) ≤ 0, между точками x0 и x1 строится хорда, стягивающая f(x). Очередное приближение берется в точке x2, где хорда пересекает ось абсцисс. В качестве нового интервала для продолжения итерационного процесса выбирается тот, на концах которого функция имеет разные знаки. Условия выхода из итерационного цикла: или

| f(x)| ≤ ξy.

Для вывода итерационной формулы процесса найдем точку пересечения хорды (описываемой уравнением прямой) с осью абсцисс: ax2 + b = 0, где ; b = f(x0) ­­– ax0.

Отсюда легко выразить .

Метод хорд в большинстве случаев работает быстрее, чем метод дихотомии. Недостатки метода те же, что и в предыдущем случае.

Метод Ньютона (касательных).

Пусть x0 – начальное приближение к корню, а f(x) имеет непрерывную производную. Следующее приближение к корню найдем в точке x1, где касательная к функции f(x), проведенная из точки (x0, f0), пересекает ось абсцисс. Затем точно так же обрабатываем точку (x1, f1), организуя итерационный процесс. Выход из итерационного процесса по условию .

Уравнение касательной, проведенной из точки (x0, f0): y(x) = f /(x0)(x–x0) + f(x0) дает для y(x1) = 0 следующее выражение:

, (1)

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

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

Недостатком метода можно указать необходимость знать явный вид первой и второй производных, так как их численный расчет приведет к уменьшению скорости сходимости метода. Иногда, ради упрощения расчетов, используют т.н. модифицированный метод Ньютона, в котором значение f /(x) вычисляется только в точке x0, при этом число итераций увеличивается, но расчеты на каждой итерации упрощаются.

Метод секущих.

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

.

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

Сходимость может быть немонотонной даже вблизи корня. При этом вблизи корня может происходить потеря точности, т.н. «разболтка решения», особенно значительная в случае кратных корней. От разболтки страхуются приемом Гарвика: выбирают некоторое ξx и ведут итерации до выполнения условия . Затем продолжают расчет, пока убывает. Первое же возрастание может свидетельствовать о начале разболтки, а значит, расчет следует прекратить, а последнюю итерацию не использовать.

Метод простых итераций.

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

f(x) = 0 (2)

к эквивалентному уравнению x = φ (x). Этот переход можно осуществить разными способами, в зависимости от вида f(x). Например, можно положить

φ (x) = x + bf(x), (3)

где b = const, при этом корни исходного уравнения (2) не изменятся.

Если известно начальное приближение к корню x0, то новое приближение x1 = φ (x0), т.е. общая схема итерационного процесса:

xk+1 = φ (xk). (4)

Наиболее простой критерий окончания процесса .

Критерий сходимости метода простых итераций: если вблизи корня |φ/(x)| < 1, то итерации сходятся. Если указанное условие справедливо для любого x, то итерации сходятся при любом начальном приближении. Исследуем выбор константы b в функции (3) с точки зрения обеспечения максимальной скорости сходимости. В соответствии с критерием сходимости наибольшая скорость сходимости обеспечивается при |φ/(x)| = 0. При этом, исходя из (3),

b = –1/f /(x), и итерационная формула (4) переходит в

,

т.е. в формулу метода Ньютона (1). Таким образом, метод Ньютона является частным случаем метода простых итераций, обеспечивающим самую высокую скорость сходимости из всех возможных вариантов выбора функции φ (x).

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

^ ТЕМА ЛЕКЦИИ 10.Методы нахождения минимума функции одной переменной. Метод дробления. Метод золотого сечения. Метод парабол.

(лекция -2 часа).

Определения.

Функция f(x) имеет локальный минимум при некотором , если существует некоторая конечная ξ-окрестность этого элемента, в которой , . Требуется, чтобы на множестве X функция f(x) была по крайней мере кусочно-непрерывной.

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

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

Методы поиска минимума по нахождению корней уравнений.

Если функция f(x) аналитически дифференцируема, то решаем f /(x) = 0 методами, изложенными в предыдущих главах. При этом условие f //(x) > 0 в найденной точке указывает нам на минимум. Для использования этих методов необходимо знать либо аналитический вид первой и второй производных, либо рассчитать их численно, если это не приведет к потере точности.

Метод дробления.

Наиболее простой метод поиска минимума. Пусть дана начальная точка x0, а также величина и знак шага h, определяющие движение из этой точки в сторону предполагаемого минимума f(x). Метод заключается в последовательном дроблении исходного шага h с изменением его знака при выполнении условия f(xk+1) > f(xk), где k – порядковый номер вычисляемой точки. Например, как только очередное значение функции стало больше предыдущего, выполняется h = – h/3 и процесс продолжается до тех пор, пока

|xk+1 – xk| ≤ ξ . (1)

Данный метод является одним из самых медленных для поиска минимума. Основное достоинство данного алгоритма – возможность использования в программах управления экспериментальными исследованиями, когда значения функции f(x) последовательно измеряются с шагом h ≥ hmin.

Метод золотого сечения.

Пусть f(x) задана и кусочно-непрерывна на [xL, xR], и имеет на этом отрезке только один локальный минимум. Золотое сечение, о котором упоминал ещё Евклид, состоит в разбиении интервала [xL, xR] точкой x1 на две части таким образом, что отношение длины всего отрезка к его большей части равно отношению большей части к меньшей:

. (2)

Таким образом, возьмем на отрезке две точки x1 и x2, симметрично относительно границ делящие исходный отрезок в отношении золотого сечения:

,

,

где коэффициент .

Если f(x1) < f(x2), мы должны сузить отрезок справа, т.е. новое значение xR = x2, в противном случае xL = x1. Оставшаяся внутри нового отрезка точка является первым приближением к минимуму и делит этот отрезок в отношении золотого сечения. Таким образом, на каждой итерации приближения к минимуму (см. рисунок) нам нужно ставить только одну точку (x1 или x2), в которой считать значение функции и сравнивать его с предыдущим. Условием выхода из итерационного процесса будет, подобно предыдущему случаю, условие |x2 – x1| ≤ ξ.

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

Метод парабол.

Пусть f(x) имеет первую и вторую производную. Разложим f(x) в ряд Тейлора в некоторой точке xk, ограничиваясь при этом тремя членами разложения:

. (3)

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

Обычно в практических реализациях данного метода не используют аналитический вид первой и второй производных f(x). Их заменяют конечно-разностными аппроксимациями. Наиболее часто берут симметричные разности с постоянным шагом h:

;

.

Это эквивалентно аппроксимации функции параболой, проходящей через три близкие точки xk+h, xk, xk–h. Окончательное выражение, по которому можно строить итерационный процесс, таково:

. (4)

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

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

. Если это не так, то от xk следует сделать шаг с τ = ½. Если и при этом условие убывания не выполнено, уменьшают τ и вновь делают шаг.
  1   2   3

Добавить документ в свой блог или на сайт

Похожие:

Лекции 8 iconЛекции: Контроль за техническим состоянием мкд
Цель лекции: дать обучающимся современные, целостные, взаимосвязанные знания по теме лекции, дать направление для самостоятельной...

Лекции 8 iconЛекции: Техническое обслуживание объектов общедомового имущества...
Цель лекции: дать обучающимся современные, целостные, взаимосвязанные знания по теме лекции, дать направление для самостоятельной...

Лекции 8 iconТематика кср по курсу «Педагогическая этика»
Ознакомиться с текстом лекции 1 «Профессиональная этика в системе этического знания» и лекции 2 «Сущностные характеристики профессиональной...

Лекции 8 iconМ. В. Карапетян лекции по теоретической грамматике английского языка владимир
Предлагаемые в пособии лекции разрабатывались автором с 2004 года и читались во Владимирском государственном университете студентам,...

Лекции 8 iconЛекции 1, 3,12: Введение: зачем знания по иммунобиологии нужны небиологам?
Лекции 1, 3,12: «Введение: зачем знания по иммунобиологии нужны небиологам?», «Врожденный иммунитет – от бактерий до человека», «Нерешенные...

Лекции 8 iconКурс читается в 7 семестре для студентов специальности "Геофизика"(заочное...
Объем курса – 20,9 часов: лекции 12 часов. Написание реферата по выбранной теме

Лекции 8 icon7. Лекция: Тупики в лекции рассматриваются вопросы взаимоблокировок,...
В лекции рассматриваются вопросы взаимоблокировок, тупиковых ситуаций и "зависаний" системы

Лекции 8 iconС. Л. Дударев статьи, заметки, лекции по истории вып. VI армавир 2007
Дударев С. Л. Статьи, заметки, лекции по истории. Вып. VI. – Армавир, 2007. 178 с

Лекции 8 iconЛекция №28 Тема лекции : Электронные генераторы

Лекции 8 iconЛекция 16. Первая мировая война 12. 11. 2003 13: 44 | Николай рудн...
В. И. Батюк "Лекции по истории международных отношений в новое время" Лекция 16. Первая мировая война

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов