Конспект и презентация к уроку информатики "Динамическое программирование"; 11 класс


Разработка рекурсивных алгоритмов на языке программирования Python

для 11 класса

углублённого изучения предмета информатика



ТЕМА «ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ»

Предметные результаты:

  • Получить представление о динамическом программировании, рекуррентной формуле

  • Уметь составлять программы для практических задач с применением рекуррентной формулы на языке Python


Мета предметные результаты:

Регулятивные УУД:

Планирование – определение последовательности промежуточных целей с учётом конечного результата, составлдение плана и последовательности действий при создании динамической модели

Контроль за этапами выполнения задачи


Коммуникативные УУД:

Умение лаконично выражаться

Владение навыками письменной коммуникации


Познавательные УУД:

Умение определять понятия, делать выводы, обобщение, строить логические умозаключения

Устанавливать причинно-следственные связи


Личностные результаты:

Формирование устойчивого познавательного интереса

Повышение ответственности к обучению


Тип урока: Комбинированный








План:

  1. Неформальное определение динамического программирования

  2. Примеры задач применения ДП

  3. Описание идеи ДП

  4. Точное определение ДП

  5. Пример 1 (задача о числовом ряде)

  6. Пример 2 (задача и сдаче)

  7. Задача 3 (оптимальная сдача)

  8. Применение динамического программирования к решению КИМ 23 ЕГЭ.



  1. Организационный этап.

  2. Постановка цели и задач урока. Мотивация учебной деятельности учащихся (пункты 1-4)

  3. Первичная проверка понимания (пункт 5)

  4. Первичное закрепление (пункт 6-7)


  1. ДП – техника, позволяющая решать некоторые задачи комбинаторики, оптимизации, …, обладающие определённым свойством (со оптимальности).









  1. ПРИМЕРЫ ЗАДАЧ

задача

Целевая функция

Переменные выбора

А. оптимизация

Маршрут оптимальной длины

Цель: найти кратчайший путь

Целевая функция: минимизация расстояния

Куда повернуть

Замена машины (оборудования)

Задача: продать старую или купить новую

Целевая функция: минимизация расходов

Продать или оставить

Биржевой портфель

Целевая функция: максимизация среднего дохода

Сколько купить акций и какой фирмы

Составление плана производства (например, производство мебели)

Целевая функция: максимизация прибыли

Составляющий план:

  • Сколько столов

  • Сколько шкафов

Б. Комбинаторика

Графы, деревья



Количество способов вернуть сдачу





  1. Н еформальное объяснение













Отвлечься орт решения сразу всей задачи, а рассмотреть решение задачи только для Х1. Найти для неё оптимальное решение и с помощью этого решения найти решение для задачи Х1, Х2. Аналогично поступить для Х1, Х2, Х3 и т.д., пока не получим решение всей задачи.









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

  • Пример 1.

Применим к решению идеи ДП

F(1) =1

F(2) = F(1)+2 = 1+2= 3

F(3) = F(2)+3 = 3+3=6

F(n)= F(n-1)+anрекуррентная формула

Рекуррентная формула (от лат. recurrens, родительный падеж recurrentis - возвращающийся), формула приведения, формула, сводящая вычисление n-го члена какой-либо последовательности (чаще всего числовой) к вычислению нескольких предыдущих её членов.

def f(n):

if n== 0:

return 0

else:

return n + f(n-1)

n=int(input('введите значение n'))

print('сумма равна',f(n))

  • Задача 2 (задача о сдаче)

Задача: имеются копейки номиналом 1, 3, 5, 10

Вопрос: сколько существует способов вернуть сдачу номиналом n копеек? (порядок монет в сдаче важен)

4 копейки

1 способ: 1 1 1 1

2 способ: 1 3

3 способ: 3 1


1 копейка 1

0 копеек 1

Обозначим через F(i) – количество способов вернуть сдачу размерностью i


F(n) - ?



F(0) F(1) F(2) F(3) … F(n-1) F(n)




F(0)=1

F(1)=1

F(2)= F(1)=1


F(3)= F(2) + F(0)=2









F(4)= F(3)+ F(1)=3

F(5)= F(4)+ F(2) +F(0)=5

F(6)= F(5)+ F(3) + F(1)=8

{рассчитайте самостоятельно F(7) и F(10) }

F(7)= F(6)+ F(4) + F(2)=12

F(8)= F(7)+ F(5) + F(3)=12+5+2=19

F(9)= F(8)+ F(6) + F(4)=19+8+3=30

F(10)= F(9)+ F(7) + F(5)+ F(0)=30+12+5+1=48


i

0

1

2

3

4

5

6

7

8

9

10

F(i)

1

1

1

2

3

5

8

12

19

30

48

Рекуррентные формулы:


при 1<к<3: F(k)= F(k-1)

при 3≤к<5: F(k)= F(k-1)+ F(k-3)

при 5≤к<10: F(k)= F(k-1)+ F(k-3)+ F(k-5)

при к≥10: F(k)= F(k-1)+ F(k-3)+ F(k-5)+ F(k-10)


Основные этапы решения:

  • Определили целевую функцию, ввели обозначения

  • Составили рекуррентную формулу

  • Вычислили F(0), F(1), F(2), …, F(n)

  • Нашли общее решение F(n)


Программа:


def f(n):

if n==0:

return 1

if n==1:

return 1

if n>1 and n<3:

return f(n-1)

if n>=3 and n<5:

return f(n-1)+f(n-3)

if n>=5 and n<10:

return f(n-1)+f(n-3)+f(n-5)

if n>=10:

return f(n-1)+f(n-3)+f(n-5)+f(n-10)

k=int(input('введите '))

print('для номиналом',' ',k,' ','копеек существует', ' ', f(k),' ','способ(а/ов)')



VII. Задача 3 (оптимальная сдача)

Определить минимальное количество монет (номиналом 1,3,5,10) необходимых для возврата сдачи

Обозначим F(n)= минимальное количество монет (номиналом 1,3,5,10) необходимых для возврата сдачи

сдача

0

1

2

3

4

5

6

7

8

9

10

F

0

1

2

1 (3)

2 (1,3)

1 (5)

2 (3,3) или (5,1)

3 (1,1,3)

2 (3,5)

3 (1,3,5)

1 (10)



  1. Наивно решение (правильное, но не эффективное)

Рассмотреть всевозможные способы вернуть сдачу n и выбрать тот, который использует минимальное количество монет.

В чем проблема?

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

  1. «Жадное» решение (простое, эффективное, но не всегда верное)

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

  1. N-10, -10,-10 … пока N не станет N<10 (или n div 10)

  2. N-5,-5 …. N<5

Но существует набор монет, для которого этот алгоритм даёт неверное решение

Например, имеются монеты 10, 9, 1 и сдача n=18

  1. Применим идею динамического программирования

F(0)=0

F(1)=1



Найдём рекуррентную формулу

F(n)=1+ F(n-1);1+ F(n-3);1+ F(n-5); 1+F(n-10)

1 3 5 10

F(n)=1+min[F(n-1), F(n-3), F(n-5), F(n-10)]

In≥1 In≥3 In≥5 In≥10

П

11-10=1

ринятие решения какую монету выбрать

Р ассмотрим пример:

Цель F(12)

N

0

1

2

3

4

5

6

7

8

9

10

11

12

F(n)

0

1

2

1

2

1

2

3

2

3

1

2

3

какой монетой достигается минимум



1

3

1

5

1

2

1

3

10

10

1



F(2) = 1+min[F(1)]=1+1=1

F(3) = 1+min[F(2), F(0)]=1+0=1

F(4) = 1+min[F(3), F(1)]=1+1=2

F(5) = 1+min[F(4), F(2), F(0)]=1

Какие монеты нужны, чтобы вернуть F(12) с помощью трёх монет?

По таблице набрать все минимумы, начиная с конца: 1, 10, 1





Рассмотрение алгоритма решения задачи 23. (презентация прилагается)



З адача 4























Слайд 1
Решение заданий КИМ23 с помощью Python «Динамическое Динамическое программирование» Подготовила: учитель информатики МОУ гимназии №20 Нагорная Ю.А.
Слайд 2
Слайд 3
Способы решения: 1. Графический – долгий, легко запутаться
Слайд 4
2. С помощью электронных таблиц – можно использовать, если в результате необходимо получить довольно небольшое число
Слайд 5
3.Автоматизированный (с помощью Python)
Слайд 6
Слайд 7
Слайд 8
Слайд 9
Слайд 10
Слайд 11
Слайд 12
Слайд 13
Слайд 14
Программа

Полный текст материала Конспект и презентация к уроку информатики "Динамическое программирование"; 11 класс смотрите в скачиваемом файле.
На странице приведен фрагмент.
Автор: Нагорная Юлия Александровна  Публикатор
28.11.2022 0 156 14

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



А вы знали?

Интересные инструкции по ПК

Лучшие материалы сайта для вас
Оставьте отзыв к материалу:
Всего: 0