Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное
учреждение высшего образования
«Уральский государственный педагогический университет»
Институт математики, информатики и информационных технологий
Кафедра информатики, информационных технологий и методики обучения информатики
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
«Объектно-ориентированное программирование в
решении математических задач»
для ОПОП 44.03.05 «Педагогическое образование»
(с двумя профилями подготовки)
ИНФОРМАТИКА И МАТЕМАТИКА
Уровень бакалавриата
Екатеринбург 2016
Оборотная сторона титульного листа
Рабочая программа дисциплины «Объектно-ориентированное программирование в решении математических задач»
(наименование дисциплины)
Составитель: , д. п.н., доцент, зав. кафедрой Информатики, информационных технологий и методики обучения информатике
____________________________
(подпись)
Рабочая программа обсуждена на заседании кафедры Информатики, информационных технологий и методики обучения информатике УрГПУ
Протокол от 01.01.2001 г. № 7
Зав. кафедрой ИИТ и МОИ _______________
(подпись)
Директор ИМИ и ИТ ________________
(подпись)
Компоненты рабочей программы ДИСЦИПЛИНЫ
1. Пояснительная записка
1.1. Наименование дисциплины (модуля).
«Объектно-ориентированное программирование в решении математических задач».
1.2.Цели и задачи дисциплины (модуля).
Учитель информатики и математики со степенью бакалавра (бакалавр по направлению «Педагогическое образование» в предметных областях «Информатика» и «Математика») является тем специалистом, который обладает уникальной базовой подготовкой, позволяющей ему решать широкий спектр профессиональных задач в области планирования и осуществления педагогической деятельности. Учитель информатики занимается наряду с обучением, решением организационных задач по формированию образовательной среды для обеспечения качества образования (в том числе с применением информационных технологий); планированием проектной деятельности школьников; изучением возможностей, потребностей, достижений учащихся; использованием технологий, соответствующих возрастным особенностям обучающихся и отражающих специфику предметной области и т. п.
Эффективное решение этих задач невозможно без осуществления сомообразования и личностного роста, без привлечения и освоения современных технологий, таких как математическое, информационное и имитационное моделирование.
К числу таких технологий, безусловно, относятся технологии программирования. Современные технологии объектно-ориентированного программирования находят все большее применение в решении математических задач, на основе которых осуществляются: обработка учетных данных, создание баз данных и баз знаний, поддержка принятия управленческих решений, автоматизация распознавания текстовых документов и поиск информации, советующие системы. Это далеко не полный перечень задач, для решения которых используется объектно-ориентированное программирование.
Целью изучения учебного курса «Объектно-ориентированное программирование в решении математических задач» является формирование совместно с другими дисциплинами у студентов теоретической и практической базы для осуществления проектной и производственно-технологической деятельности.
Целью изучения курса, соотнесенной с общими целями ООП ВО, является: освоение знаний, развитие умений студентов в области использования фундаментальных алгоритмов обработки данных, типичных методов разработки эффективных алгоритмов, а также освоение современных методов исследования алгоритмов и оценки их алгоритмической сложности и тенденциями их развития. В частности, рассматриваются алгоритмы сортировки и поиска информации, алгоритмы для задач теории графов.
Задачи дисциплины состоят
- в формировании у студентов минимально необходимых знаний об эффективных алгоритмах решения типичных задач из различных разделов дискретной математики и программирования, в том числе эвристических алгоритмов;
- в формировании и развитии умений вычленять эффективные алгоритмы решения типичных математических задач при решении профессиональных задач;
- в выработке практических навыков аналитического и экспериментального исследования основных методов и средств, используемых в области, изучаемой в рамках данной дисциплины;
- в формировании у студентов общепрофессиональных знаний теории, методов, систем и средств для решения практических задач в области информационных технологий с использованием эффективных алгоритмов.
1.3. Место дисциплины в структуре ООП.
Дисциплина «Объектно-ориентированное программирование в решении математических задач» относится к вариативной части дисциплин и является дисциплиной по выбору (Б1.В. ДВ.9.1) для студентов ООП «44.03.01 Педагогическое образование» (профиль «Информатика и математика»). При реализации данной дисциплины учитываются ее роль и место в общей системе профессионального блока дисциплин будущего бакалавра-педагога. Так, содержательные линии ранее изученных курсов «Языки и технологии программирования», «Программное обеспечение информационных технологий», посвященные реализации методологии объектно-ориентированного программирования и информационных технологий при проектировании и создании баз данных создает основу для эффективного освоения дисциплины «Теория систем и системный анализ».
Требования к уровню предварительной подготовки студента отсутствуют. Изучение курса рассчитано на один семестр (6-й), поэтому входные знания могут оцениваться по мере освоения базовых дисциплин в предыдущих пяти семестрах.
Логика построения содержания учебного материала курса, логика его изложения и методика проведения лекционных и лабораторных занятий предусматривает освоение студентами учебного материала (при освоении ими дисциплин в соответствие с учебным планом) с нулевого уровня.
1.4. Перечень планируемых результатов обучения по дисциплине (модулю), соотнесенных с планируемыми результатами освоениями образовательной программы:
Процесс изучения дисциплины направлен на формирование следующих компетенций: В результате изучения дисциплины «Объектно-ориентированное программирование в решении математических задач» студент должен приобрести следующие профессиональные компетенции, соотнесенные с общими целями ОП ВПО:
Компетенции:
ПК-1 готовность реализовывать образовательные программы по учебному предмету в соответствие с требованиями образовательных стандартов.
1.5. Объем дисциплины (модуля) в зачетных единицах.
Общая трудоемкость дисциплины составляет 3 зачетных единицы, 108 часов.
1.6. Особенности реализации дисциплины (модуля).
Дисциплина «Объектно-ориентированное программирование в решении математических задач» реализуется на русском языке.
Для организации индивидуальной и самостоятельной работы студентов используется электронный ресурс: http://e-portal. uspu. ru .
2. Учебно-тематическое планирование
Учебно-тематический план очной формы обучения
№ п/п | Наименование | Всего трудоемкость | Аудиторные | Самостоя-тельная работа | |||
Всего | Лекции | Практи-ческие | Лабора-торные | ||||
1 | Основные понятия теории графов. | 32 | 18 | 8 | 10 | 14 | |
2 | Алгоритмы и их сложность. | 36 | 16 | 2 | 14 | 20 | |
3 | Поиск в графе. | 40 | 20 | 8 | 12 | 20 | |
Итого | 108 | 54 | 18 | 36 | 54 |
3. Содержание дисциплины
Перечень тем лекционных занятий
1. Раздел «Основные понятия теории графов».
Основные определения. Корневые и бинарные деревья. Понятие графа. Ориентированные и неориентированные графы. Маршруты, связность, циклы: цепь в графе / путь в орграфе; компоненты связности графа. Понятие дерева. Корневое дерево. Двоичное дерево. Понятие сети. Способы машинного представления графа (орграфа): матрица, списки, массив смежностей, ассоциированные с графом (орграфа).
2. Раздел «Алгоритмы и их сложность».
Алгоритмы. Запись алгоритмов. Критерии оценки качества алгоритмов. Понятие сложности алгоритма. Вычислительная сложность алгоритмов. Сортировка массивов как неотъемлемая часть алгоритмов решения математических задач. Постановка задачи сортировки. Алгоритм сортировки на основе двоичного дерева (сортирующего дерева массива).
3. Раздел «Поиск в графе»
Примеры дискретных оптимизационных задач: задача о кратчайшем пути: задача оптимального назначения, задача коммивояжера. Типы задач. Методы решения подобных задач. Алгоритмы дискретной оптимизации на сетях и графах: поиск в глубину, поиск в ширину. Нерекурсивная и рекурсивная версии алгоритмов. Пути в сетях. Понятие эвристики. Эвристические методы и алгоритмы для решения задач высокой вычислительной сложности. Эвристический поиск. Алгоритм Дейкcтры.
Темы лабораторных работ:
1. Раздел «Основные понятия теории графов».
Решение задач на формирование матрицы, списков, массива смежностей графа (орграфа). Сравнение ресурсоёмкости различных способов машинного представления графа (орграфа).
2. Раздел «Алгоритмы и их сложность».
Решение задач по оценке сложности рекурсивных алгоритмов, сравнению скорости роста функций. Решение задач на сортировку массивов.
Решение задач на прокрутку алгоритмов сортировки и поиска к-го наименьшего, на анализ сложности алгоритмов и разработку алгоритмов
3. Раздел «Поиск в графе»
Решение задач на анализ, применение и разработку алгоритмов на графах и сетях.
Примерные вопросы для контроля и самоконтроля.
1. Раздел «Основные понятия теории графов»
− Дайте определения понятиям: ориентированный граф, неориентированный граф; сеть; простая цепь, цикл; дерево; двоичное дерево.
− Какие вершины называются висячими, изолированными;
− Опишите способы машинного представления графа (орграфа).
2. Раздел «Алгоритмы и их сложность»
− Дайте определения понятию алгоритм.
− Перечислите критерии оценки качества алгоритмов.
− Как определить асимптотическую сложность алгоритма;
алгоритмов.
− Как формулируется задача сортировки.
3. Раздел «Поиск в графе»
− Как формулируются оптимизационные задачи: задача о кратчайшем пути: задача оптимального назначения, задача коммивояжера.
− Приведите примеры массовой и индивидуальной задач.
− Приведите алгоритмы поиска в глубину, поиска в ширину.
− Дайте понятие эвристики.
− Перечислите эвристические алгоритмы для решения задач высокой вычислительной сложности.
− Что такое эвристический поиск.
− Опишите алгоритм Дейкcтры.?
4. перечень учебно-методического обеспечения для самостоятельной работы обучающихся по
дисциплине (модулю)
1. Презентация по вышеописанным разделам.
2. Электронная версия (файл в pdf-формате) , , Дискретная математика: графы, матроиды, алгоритмы / Научно-издательский центр «Регулярная и хаотическая динамика», Ижевск, 2001., 287 с.
3. Электронная версия (файл в djvu-формате) Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн Алгоритмы: построение и анализ/ 2-е изд.
Перечень рекомендуемых тем, вынесенных на самостоятельное изучение
− Алгоритм отыскания блоков и точек сочленения.
− Алгоритм отыскания компонент сильной связности в орграфе.
− Алгоритмы решения задачи коммивояжера с гарантированной оценкой точности.
− Алгоритм Форда—Фалкерсона решения задачи о максимальном потоке.
5. Фонд оценочных средств для проведения промежуточной аттестации по дисциплине (модулю)
В результате оценочной деятельности проверяется освоение следующих основных структурных компонентов компетенций:
Название раздела | Содержательное описание компонентов (показателей) компетенции | Используемые оценочные средства |
ПК-1 | ||
Основные понятия теории графов | знания | |
базовые знания математики и информатики, концепции, теорий, связанной с фундаментальной информатикой и информационными технологиями | ОС1, ОС2, ОС3 | |
ОС1, ОС2, ОС3 | ||
умения | ||
использовать базовые знания математики и информатики, основные концепции теории, связанной с фундаментальной информатикой и информационными технологиями эффективно применять базовые математические знания и информационные технологии при решении прикладных задач | ОС1, ОС2, ОС3 | |
ОС1, ОС2, ОС3 | ||
владение | ||
основной концепцией теории графов, т. е. теории, связанной с фундаментальной информатикой базовыми математическими знаниями и информационными технологиями при решении прикладных задач, связанных с развитием и использованием информационных технологий | ОС1, ОС2, ОС3 | |
ОС1, ОС2, ОС3 | ||
Алгоритмы и их сложность | знания | |
математики и информатики, основные факты теории, связанной с фундаментальной информатикой и информационными технологиями о методах и механизмах оценки и анализа функционирования средств и систем информационных технологий | ОС1, ОС2, ОС3 | |
ОС1, ОС2, ОС3 | ||
умения | ||
использовать базовые знания математики и информатики применять в профессиональной деятельности современные языки программирования эффективно применять базовые математические знания и информационные технологии при решении прикладных задач, связанных с развитием и использованием информационных технологий применять методы и механизмы оценки и анализа функционирования средств и систем информационных технологий | ОС1, ОС2, ОС3 | |
ОС1, ОС2, ОС3 | ||
владение | ||
базовыми знаниями математики и информатики современными языками программирования базовыми математическими знаниями и информационными технологиями в аспекте их способами эффективного применения при решении прикладных задач методами и механизмами оценки и анализа функционирования средств и систем информационных технологий | ОС1, ОС2, ОС3 | |
ОС1, ОС2, ОС3 | ||
Поиск в графе | знания | |
базовые знания информатики, основные факты теории, связанной с фундаментальной информатикой и информационными технологиями; современных языков программирования информационных технологий, применяемых при решении прикладных задач | ОС1, ОС2, ОС3 | |
ОС1, ОС2, ОС3 | ||
умения | ||
использовать базовые знания информатики, основные факты теории, связанной с фундаментальной информатикой и информационными технологиями применять в профессиональной деятельности современные языки программирования эффективно применять базовые математические знания и информационные технологии при решении прикладных задач разрабатывать и реализовывать программное обеспечение | ОС1, ОС2, ОС3 | |
ОС1, ОС2, ОС3 | ||
владение | ||
базовыми знаниями информатики, основными фактами теории, связанной с фундаментальной информатикой и информационными технологиями современными языками программирования базовыми математическими знаниями и информационными технологиями в аспекте их способами эффективного применения при решении прикладных задач методами разработки и реализации программное обеспечение | ОС1, ОС2, ОС3 | |
ОС1, ОС2, ОС3 |
Для оценки результатов освоения дисциплины «Объектно-ориентированное программирование в решении математических задач» используются следующие оценочные средства:
ОС1 –задания на разработку алгоритмов задач по тематике разделов учебной дисциплины и реализации разработанных алгоритмов, т. е. их кодированию на основе объектно-ориентированного языка программирования (Object Pascal, Java, C++);
ОС2 –вопросы для устного опроса;
ОС3 – вопросы и практические задания для проведения зачета.
Текущий контроль осуществляется в форме отчетов о выполнении индивидуальных заданий, а также в форме устного опроса.
Итоговой контроль осуществляется в форме зачёта (в соответствии с учебным планом).
Критерий и шкала оценивания:
Результаты использования оценочных средств позволяют преподавателю судить о сформированности или несформированности каждой из выделенных компонент компетенций. В итоговой таблице диагностических результатов это отражается в виде балльной системы 0 (не сформирована) – 1 (сформирована).
Итоговый диагностический вывод формулируется на основе следующего правила: если сформировано более 70% составляющих компонентов компетенций (знаний, умений, владений), то делается вывод о сформированности соответствующей компетенции, в противном случае – о несформированности компетенции.
ОС1 – задания на разработку алгоритмов задач по тематике разделов учебной дисциплины и реализации разработанных алгоритмов, т. е. их кодированию на основе объектно-ориентированного языка программирования (Object Pascal, Java, C++);
Например.
Задачи на формирование матрицы, списков, массива смежностей графа (орграфа). Задач по оценке сложности рекурсивных алгоритмов, сравнению скорости роста функций. Задачи на сортировку массивов. Задачи на прокрутку алгоритмов сортировки и поиска к-го наименьшего. Задачи на анализ, применение и разработку алгоритмов на графах и сетях.
ОС2 –вопросы для устного опроса (представлены выше в разделе вопросы для контроля и самоконтроля).
ОС3 – (примерные) вопросы и практические задания для проведения зачёта.
1. Основные понятия теории графов, представление графов в ЭВМ.
- Сколько ребер имеется в дереве на n вершинах?
- Как проверить является ли заданный граф деревом?
- Сколько вершин нечетной степени может быть в графе?
- Какова сложность ответа на вопросы:
а) найти степень заданной вершины графа,
б) определить, имеется ли в графе ребро (v, w),?
в) удалить/добавить ребро к графу, если граф задан матрицей смежности или списками смежностей.
- Является ли дерево двудольным графом?
- Как поиском в глубину или в ширину определить является ли граф двудольным?
- Как проверить граф на ацикличность?
- Как найти все компоненты связности заданного графа?
- Как выглядит общая схема случайного поиска в графе? Почему поиск в ширину и поиск в глубину являются частными случаями случайного поиска?
2. Задача о минимальном остове.
- Какой из алгоритмов построения минимального остова использовать предпочтительнее для полных графов, а какой для разреженных?
- Какова максимальная степень вершины остовного дерева плоского Евклидового графа?
- Приведите примеры графов, в которых имеется несколько минимальных остовов.
3. Кратчайшие пути в сетях.
- Приведите пример графа (с отрицательными весами) для которого алгоритм Дейкстры дает неверный ответ.
- Пусть в графе имеются ребра отрицательного веса. Прибавим к весу каждого ребра одно и тоже большое положительное число так, чтобы веса всех ребер стали положительными. В таком графе решим задачу о кратчайшем пути, используя алгоритм Дейкстры. Объясните, почему такой метод может давать неправильный ответ для исходного графа.
- Как найти кратчайший путь от одного множества вершин до другого?
- Как решать задачу о наибольшем пути?
- Как решать maxmin и minmax задачи о кратчайшем пути?
- Как в заданном графе найти цепь наибольшей длины?
4. Задача коммивояжера. Приближенные алгоритмы.
- Постройте пример графа, в котором алгоритм «Ближайшая вставка» работает хуже чем алгоритм «Ближайший сосед».
- Постройте реализацию алгоритма «Ближайший сосед» сложности O(n2).
6. Учебно-методическое и ИНФОРМАЦИОННОЕ
обеспечение ДИСЦИПЛИНЫ
6.1. Рекомендуемая литература
Основная
1. Электронная версия (файл в pdf-формате) , , Дискретная математика: графы, матроиды, алгоритмы / Научно-издательский центр «Регулярная и хаотическая динамика», Ижевск, 2001., 287 с.
2. Электронная версия (файл в djvu-формате) Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн Алгоритмы: построение и анализ/ 2-е изд.
Дополнительная
1. Макконнелл, Дж. Основы современных алгоритмов [Текст] : учеб. Пособие по направлению «Информатика и вычислит. техника» / Дж. Макконнелл; пер. с англ. ; доп. .– 2-е доп. Изд. – М.: Техносфера, 2006. – 368 с. Рекомендован учёным советом Моск. гос. академии приборостроения и информ. (2 экз.)
2. Кнут, Э. Доналд. Искусство программирования [Текст] : учеб. пособие: в З т. / .; под общ. ред. . – 3-е изд. - М. : Вильямс, Т. 1 : Основные алгоритмы. - 2005. - 720 с. (5 экз.)
3. Кнут, Э. Доналд. Искусство программирования [Текст] : учеб. пособие: в З т. / .; под общ. ред. . – 3-е изд. - М. : Вильямс, Т.2 : Получисленные алгоритмы - 2005. - 832 с. (5 экз.)
4. Доналд. Искусство программирования [Текст] : учеб. пособие: в З т. / .; под общ. ред. . – 2-е изд. - М. : Вильямс, ТЗ. Сортировка и поиск. – 2005. - 824 с. (5 экз.)
5. . Основы алгоритмизации и программирования [Текст]:учеб. пособие для студентов учреждений сред. проф. образования по спец. "Информатика и вычисл. техника"/, .-3-е изд., испр. и доп.-М.:ФОРУМ,2010.-432 с.:ил.-(Профессиональное образование).-Библиогр. :-Допущено М-вом образования РФ. (5 экз.)
6. . Дискретная математика [Текст]:учеб. для студентов образоват. учреждений сред. проф. образования/, .-4-е изд., испр.-М.:Академия,2007.-368 с.:ил.-Допущено М-вом образования РФ. (26 экз.)
6.2. Информационное обеспечение дисциплины
В электронном виде представлены на учебном портале (http://e-portal. uspu. ru) и на сетевом диске (z:\ 4-й курс\ ООП в решении матзадач)
1. Презентация по вышеописанным разделам.
2. Электронная версия (файл в pdf-формате) , , Дискретная математика: графы, матроиды, алгоритмы / Научно-издательский центр «Регулярная и хаотическая динамика», Ижевск, 2001., 287 с.
3. Электронная версия (файл в djvu-формате) Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн Алгоритмы: построение и анализ/ 2-е изд.
6.3. Печатные и (или) электронные ресурсы
для лиц с ОВЗ
В процессе освоения дисциплины обучающимися с ограниченными возможностями здоровья используется специальное техническое и программное обеспечение, а также электронные образовательные ресурсы.
Оборудование:
· два компьютера с тактильным дисплеем Брайля PAC Mate 20, большой программируемой клавиатурой IntelliKeys USB
· универсальный мобильный лестничный подъемник «ПУМА-УНИ-130»
Программное обеспечение:
· программа экранного доступа JAWS for Windows версия 16.0. Pro;
· программа синтеза речи “Infovox 4”.
Электронные ресурсы:
· лекции в виде презентаций по всем темам курса (входят в состав электронного УМК по дисциплине).
7. Материально-техническое и дидактическое
обеспечение дисциплины
− персональные компьютеры (Pentium и выше);
− локальная компьютерная сеть;
− проекционное оборудование (цифровой проектор, экран, ноутбук).
− При изучении данной дисциплины рекомендуется использовать:
− мультимедийные презентации на лекционных занятиях;
− учебные пособия, практические и лабораторные работы, тесты и другие ресурсы, представленные в электронном виде на образовательном портале УрГПУ;
− примеры готовых приложений, демонстрирующих изучаемые объекты;
− примеры цифровых образовательных ресурсов, разработанные студентами за предшествующие годы освоения дисциплины.
8. СВЕДЕНИЯ ОБ авторЕ программы
Доктор педагогических наук
доцент
завкафедрой информатики, информационных технологий и методики обучения информатике
+7(343)3713527
