Элективный курс “Анализ эффективных алгоритмов”

# “Анализ эффективности алгоритмов”

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Количество часов: 17

Образовательная область: информатика

Профиль: Физико-математический профиль

Классы: 10-11

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

Задачи курса:

> - ознакомление учащихся с понятием алгоритма, его свойствами и основными конструкциями алгоритмов;
> - ознакомление учащихся с алгоритмами решения различных задач;
> - ознакомление учащихся с понятием "эффективный алгоритм" и критериями эффективности;
> - формирование умения распознавать задачи, решать их с помощью разных алгоритмов, проводить анализ результатов;
> - развитие логического и алгоритмического мышления школьников;
> - совершенствование навыков построения и решения алгоритмов.

Данный элективный курс относится к предметным курсам, задача которых - углубление и расширение знаний по предметам, входящих в базисный учебный план школы, в частности, углубление изучения отдельных разделов основного курса, входящих в обязательную программу конкретного предмета. В данном случае предполагается углубление изучение раздела «Основы алгоритмизации» примерной программы обучения информатике. Курс рассчитан на 17 часов, которые проводятся в течение учебного времени по 1 часу в неделю.

Курс «Анализ эффективности алгоритмов» рекомендуется учащимся 10-11 классов. К этому времени многие из них уже имеют достаточно высокий уровень развития абстрактного мышления, умеют строить модели задач в рамках некоторой математической теории, имеют навыки алгоритмизации и сформированные познавательные интересы.

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

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

Теория (9,5 ч)

1 Обработка информации. (1 ч)

Виды обработки информации. Понятие алгоритма. Свойства алгоритма. Основные этапы построения алгоритма. Язык программирования алгоритмических машин. Система команд исполнителя.

2. Эффективность алгоритмов.(1 ч)

Принцип анализа алгоритмов. Понятие эффективности. Ограничение финитности.

3. Машина Поста(0,5 ч)

Алгоритмическая машина Поста. Команды машины Поста. Составляющие машины Поста.

4.Динамическое программирование. (3 ч)

Понятие динамического программирования. Оптимальное решение. Перекрещивающиеся подзадачи. Подходы динамического программирования.

5. Задача коммивояжера (0,5)

Жадный алгоритм решения задачи, деревянный алгоритм решения задачи, Метод "ветвей и границ".

6. Линейное программирование. (2 ч)

Максимальное паросочетание. Максимальный поток. Транспортная задача. Симплекс-метод.

7. Потоки в сетях. (1.5 ч)

Транспортная сеть. Допустимый поток. Величина потока. Полный поток. Насыщенность дуг.

Практика (7,5 ч)

1. Машна Поста (0,5 ч)

2. Динамическое программирование. (4 ч)

3. Задача коммивояжера. (0,5 ч)

4. Линейное программирование. (1 ч)

5. Потоки в сетях (0,5 ч)

6. Решение задач. (1 ч)

Тематическое планирование

№ | Раздел | Темы | Время
всего | теория | практика
1 | Введение в теорию алгоритмов | Информация. Алгоритм | 1 | 1 | -
Эффективность алгоритмов | 1 | 1 | -
Машина Поста. | 1 | 0,5 | 0,5
2 | Динамическое программирование | Понятие динамического программирования. Подходы динамического программирования. | 1 | 1 | -
Числа Фибоначчи | 1 | 0,5 | 0,5
Наибольшая подпоследовательность | 1 | 0,5 | 0,5
Задачи на нахождение длины пути | 1 | - | 1
Возрастающая подпоследовательность | 1 | 0,5 | 0,5
Задача о рюкзаке | 1 | 0,5 | 0,5
Решение задачи о рюкзаке | 1 | - | 1
3 | Транспортная логистика | Методы оптимального планирования | 1 | 0,5 | 0,5
Потоки в сетях | 1 | 1 | -
Транспортная задача | 1 | 0,5 | 0,5
4 | Линейное программирование | Задача линейного программирования | 1 | 1 | -
Симплекс метод | 1 | 1 | -
Программа решения задачи линейного программирования | 1 | - | 1
5 | Итоговая работа | Решение задач пройденного курса | 1 | - | 1
| Итого: | - | 17 | 9,5 | 7,5

Требования к уровню подготовки учащихся:

После изучения элективного курса "Анализ эффективности алгоритмов" учащиеся должны:

знать/понимать:

- Знать понятие алгоритма;

- Знать свойства алгоритма;

- Знать основные конструкции построения алгоритмов;

- Иметь представление о технологии алгоритмизации задач;

- Знать основные алгоритмы решения различных задач.

Уметь:

- Уметь подбирать наиболее эффективный алгоритм для решения задачи;

- Уметь строить алгоритмы решения задачи;

- Уметь находить решение задачи с помощью разных алгоритмов;

- Уметь проводить анализ результатов работы алгоритмов.

Использовать приобретенные знания и умения для:

- эффективной организации индивидуального информационного пространства;

- эффективного распределения времени и ресурсов связанных с дальнейшей профессиональной ориентацией.

Программа рассчитана на определенный уровень подготовки учащихся:

- Базовые знания по информатике;

- Владение базовыми понятиями в области программирования.

Требования к уровню компетентности

| Уровень I | Уровень II | Уровень III
Решение проблем | Имеет представление об алгоритмах. Демонстрирует понимание необходимости применения различных алгоритмов. | Планирует реализацию задачи с помощью конкретного алгоритма; оценивает результаты решения задачи с помощью использованного алгоритма | Ставит проблему, анализирует ее и предлагает способ решения; анализирует адекватность и точность результата по сравнению с поставленной целью; анализирует ход работы и корректирует выбранные методы написания алгоритма
Работа с информацией | Демонстрирует понимание предложенного учителем способа деятельности; | Аргументировано поясняет точку зрения по поводу интерпретации алгоритма; выделяет в процессе построения алгоритма неоднозначные вопросы; выявляет пункты, которые могут быть реализованы различными способами | Проводит сравнительный анализ различных методов сбора информации по проблеме; планирует этапы по сбору информации о модели; делает выводы о степени целостности полученной информационной картины и устраняет при необходимости ее недостатки
Коммуникация | Соблюдает нормы речи при изложении мыслей; Придерживается предложенной схемой описания алгоритма для формулирования описания собственного алгоритма | Соблюдает нормы общения в группе; взаимодействует при описании алгоритма; соблюдает нормы общения в аргументированной дискуссии | Организует работу команды по сбору, обработке и преобразованию информации; использует эффективные приемы общения для постановки цели и задач деятельности; логически выстраивает схему деятельности во внешнем и внутреннем плане.

Критерии оценки уровня сформированности ключевых компетентностей

Решение проблем

| Уровень I | Уровень II | Уровень III
| 3 | 4 | 5 | 6 | 7 | 8
Постановка проблемы | Ученик согласен с наличием проблемы в ситуации, сформулированной учителем | Ученик объяснил цель построения алгоритма | Ученик формулирует цель написания определённого алгоритма и корректирует ее с помощью учителя | Ученик формулирует цель построения алгоритма и разбивает ее на задачи | Ученик выделяет из проблемной ситуации объект прогнозирования и определяет цель прогнозирования | Ученик определяет главную цель задачи, формулирует данные для написания алгоритма
планирование Процесс решения | Ученик после построения описывает, что было сделано | Ученик описал задачу одним из предложенных алгоритмов | Ученик описал алгоритм с учетом заранее заданных критериев ее оценки | Ученик обосновано назвал потенциальных потребителей и области использования прогноза | Ученик по готовому алгоритму доказывает эффективность его использования | Ученик представляет собственный алгоритм и доказывает верность его описания
Оценка результата | Ученик высказал оценочное отношение к полученному алгоритму | Ученик назвал трудности, с которыми он столкнулся при разработке алгоритма | Ученик описывает слабые стороны работы над построением алгоритмом | Ученик оценивает вклад каждого участника в решение задачи построения алгоритма и анализ результатов | Ученик предложил способ(ы) преодоления трудностей, с которыми он столкнулся при построении алгоритма | Ученик аргументировал возможность использовать освоенные в ходе работы над построением алгоритма умения в других видах деятельности

Обработка информации

| Уровень I | Уровень II | Уровень III
| 3 | 4 | 5 | 6 | 7 | 8
Поиск информации | Ученик указывает на необходимость дополнительной информации для построения алгоритма | Ученик указывает конкретные цели поиска информации | Ученик выделяет вопросы, которые необходимо разрешить для построения алгоритма | Ученик предлагает способы для подбора дополнительной информации для построения оптимального (эффективного) алгоритма | Ученик определил круг вопросов по которым нужно пользоваться несколькими источниками | Ученик самостоятельно организует поиск дополнительного материала т.о., что получает описанный в цели результат
Обработка информации | Ученик изложил полученную информацию об алгоритме | Ученик предпринял действия по интерпретации алгоритма, основываясь на полученной информации | Ученик сделал вывод на основе полученной информации и привел несколько аргументов или данных для его подтверждения | Ученик выстроил в собственной логике совокупность аргументов, подтверждающих вывод по результатам решения алгоритма | Ученик проанализировал несколько точек зрения по проблеме, лежащей в основе построения алгоритма | Ученик самостоятельно переработал и реализовал алгоритм решения задачи

Коммуникация

| Уровень I | Уровень II | Уровень III
3 | 4 | 5 | 6 | 7 | 8
Устная коммуникативная | Ученик передает в устной речи основные этапы реализации построения алгоритма | Ученик характеризует этапы реализации описания алгоритма | Ученик изложил план действий при построении алгоритма | Ученик конкретизирует действия постановкой промежуточных целей | Ученик описывает общую схему построения алгоритма во время планирования | Ученик формулирует свою схему построения алгоритма на основе предложенной для достижения наиболее эффективного результата
Письменная коммуникативная | Ученик фиксирует план построения алгоритма во время работы | Ученик описывает пояснения к плану по ходу работы над построением алгоритма | Ученик конкретизирует этапы построения и описания алгоритма определениями, формулами, мат. объектами | Ученик поясняет значение формул и мат.объектов | Ученик формулирует цель построения алгоритма с помощью алгоритмических конструкций | Ученик формулирует схему описания алгоритма на естественном и математическом языке