МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГБОУ ВО

«СГУ имени »

Механико-математический факультете



СОГЛАСОВАНО

заведующий кафедрой

____________

"__" ________________20___ г.

УТВЕРЖДАЮ

председатель НМС факультета

___

"__" ________________20___ г.


Фонд оценочных средств

текущего контроля и промежуточной аттестации по дисциплине

Комбинаторные алгоритмы

Направление подготовки магистратуры

01.04.02  - Прикладная математика и информатика

Профиль подготовки магистратуры

Математические и компьютерные методы обработки информации

Квалификация (степень) выпускника

Магистр

Форма обучения

очная

Саратов, 2016

       

Карта компетенций


Контролируемые компетенции

(шифр компетенции)

Планируемые результаты обучения

(знает, умеет, владеет, имеет навык)

ПК-3 - способность разрабатывать и при­менять математиче­ские методы, систем­ное и прикладное программное обеспе­чение для решения за­дач научной и проект­но-технологической деятельности

Знать: языки программирования, библиотеки и пакеты программ

Уметь: анализировать поставленную задачу и находить алгоритм ее решения.

Владеть: методами моделирования информационных процессов

ПК-4 - способность разрабатывать и реализовывать ал­горитмы решения не­стандартных задач в проектной и производственно-технологической дея­тельности

Знать: языки программирования, библиотеки и пакеты программ, быстрые алгоритмы и методы их получения

Уметь: разрабатывать и реализовывать алгоритмы цифровой обработки изображений, средств компьютерной графики, мультимедиа и автоматизированного проектирования

Владеть: методами разработки и реализации алгоритмов, вычислительных моделей и моделей данных для реализации элементов новых (или известных) сервисов систем информационных технологий


Показатели оценивания планируемых результатов обучения

НЕ нашли? Не то? Что вы ищете?

Семестр

Шкала оценивания

2

3

4

5

2

с

е

м

е

с

т

р

Не владеет основами язы­ков програм­мирования, библиотеками и пакетами программ_З (ПК-3) –I

Не имеет пред­ставления о поставленной задаче и алго­ритме ее реше­ния_У (ПК-3) –I

Не владеет ме­тодами моде­лирования ин­формационных процессов__В (ПК-3) –I

Поверхностно знает основы языков програм­мирования, биб­лиотеками и па­кетами про­грамм_З (ПК-3) –I

Не достаточно способен анали­зировать постав­ленную задачу и делает ошибки при выборе ал­горитма ее ре­шения _У (ПК-3) –I

Слабо владеет методами моде­лирования ин­формационных процессов__В (ПК-3) –I

Уверенно вла­деет языками  программиро­вания, библио­теками и паке­тами программ_З (ПК-3) –I

Способен гра­мотно анализи­ровать постав­ленную задачу и верно нахо­дить алгоритм ее решения_У (ПК-3) –I

Ориентируется в методах мо­делирования информацион­ных процес­сов__В (ПК-3) –I

Свободно вла­деет  языками программирова­ния, библио­теками и паке­тами программ_З (ПК-3) –I

Свободно ана­лизирует по­ставленную за­дачу и точно и грамотно нахо­ди алгоритм ее решения_У (ПК-3) –I

Уверенно вла­деет методами моделирования информацион­ных процессов__В (ПК-3) –I

Не имеет пред­ставления о современных методах циф­ровой обра­ботки изобра­жений и средств компьютерной графики

_З (ПК-3) –II

Не умеет выбирать

оптимальные системы программирования, наиболее подходящие для решения поставленной задачи_У (ПК-3) – II

Не способен работать над производствен­ным проектом в составе груп­пы научных специалистов__В (ПК-3) – II

Имеет поверх­ностное пред­ставления о современных методах цифро­вой обработки изображений и средств компью­терной графики

_З (ПК-3) –II

Не всегда выби­рает

оптимальные системы про­граммирования, подходящие для решения постав­ленной задачи_У (ПК-3) – II

Не уверенно ра­ботает над производствен­ным проектом в составе группы научных специа­листов__В (ПК-3) – II

Уверенно вла­деет современ­ными метода­ми цифровой обработки изображений и средства компьютерной графики

_З (ПК-3) –II

Свободно

выбирает опти­мальные систе­мы програм­мирования, наиболее под­ходящие для решения по­ставленной за­дачи_У (ПК-3) – II

Уверенно вла­деет навыками работы над производствен­ным проектом в составе груп­пы научных специалистов__В (ПК-3) – II

современными методами циф­ровой обра­ботки изобра­жений и сред­ства компью­терной графики

_З (ПК-3) –II

Самостоятельно

выбирает опти­мальные систе­мы програм­мирования, наи­более подходя­щие для реше­ния поставлен­ной задачи_У (ПК-3) – II

Квалифициро­ванно работает

над произ­водственным проектом в со­ставе группы научных специалистов __В (ПК-3) – II

Не владеет: ме­тодами разра­ботки и реали­зации алгорит­мов, вычисли­тельных моде­лей и моделей данных для реа­лизации элементов но­вых (или из­вестных) сер­висов систем информацион­ных техноло­гий;

Не умеет: раз­рабатывать и реализовывать алгоритмы цифровой обработки изображений, средств компьютерной графики, мультимедиа и автоматизированного проектирования;

Не знает:

языки программирования, библиоте­ки и пакеты программ, бы­стрые алгорит­мы и методы их получения;

Не всегда вла­деет: методами разработки и реализации ал­горитмов, вы­числительных моделей и моде­лей данных для реализации эле­ментов новых (или известных) сервисов систем информацион­ных технологий;

Слабо умеет: разрабатывать и реализовывать алгоритмы циф­ровой обработки изображений, средств компьютерной графики, мультимедиа и автоматизированного проектирования;

Поверхностно знает: языки программирова­ния, библиотеки и пакеты про­грамм, быстрые алгоритмы и ме­тоды их получе­ния;

Уверенно вла­деет:

методами раз­работки и реа­лизации алго­ритмов, вычис­лительных мо­делей и моде­лей данных для реализации элементов но­вых (или из­вестных) сер­висов систем информацион­ных техноло­гий;

Понимает как разрабатывать и реализовы­вать алгоритмы цифровой об­работки изоб­ражений, средств компьютерной графики, мультимедиа и автоматизиро­ванного проек­тирования;

Хорошо знает: языки программирования, библиоте­ки и пакеты программ, бы­стрые алгорит­мы и методы их получения;

Полностью вла­деет:

методами раз­работки и реа­лизации алго­ритмов, вычис­лительных мо­делей и моде­лей данных для реализации эле­ментов новых (или известных) сервисов си­стем информа­ционных техно­логий;

В совершенстве умеет:

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

Отлично знает:

языки програм­мирования, библиотеки и пакеты про­грамм, быстрые алгоритмы и методы их по­лучения;

3. Оценочные средства

Задания для текущего контроля

Контрольная работа

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

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

Критерии оценки

Оценка «5»

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

Оценка «4»

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

Оценка «3»

    наблюдается усвоение основного материала; в решении присутствуют неточности; нарушение последовательности в изложении программного материала.

Оценка «2»

    незнание программного материала; при решении возникают ошибки.

Примерные варианты контрольной работы

Вариант1.

1. Сравнительный анализ простых сортировок: обменом, вставками, выбором.

2. Для заданного связного графа найти минимальное остовное дерево. Данные для графа должны быть прочитаны из файла.

3. Обзор оценок сложности алгоритмов.

Вариант 2.

1. Сортировка Шелла и сортировка с помощью дерева. Их реализация, анализ и сравнение.

2. Хэш-функции и хеширование.

3.Структуры данных для представления графов в компьютере (матрица смежности, матрица инцидентности, список списков, совокупность двух списков: список вершин, список рёбер).

Вариант 3.

1. Быстрая сортировка. Сортировка слиянием. Их анализ и сравнение.

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

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

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


Анализ верхней и средней оценок сложности алгоритмов; сравнение наилучших, средних и наихудших оценок. Стратегии алгоритмов. Рекурсия и цикл; полный перебор; метод “разделяй и властвуй”; “жадные” алгоритмы; бэктрекинг (перебор с возвратами); метод ветвей и границ; эвристический поиск; поиск по образцу, алгоритмы обработки строк. Данные линейной и нелинейной структур. Их рекурсивная и нерекурсивная обработка. Сортировка за квадратичное время. Сортировка за линейное время. Алгоритмы последовательного и бинарного поиска. Элементарные структуры данных. Хеширование и хеш-таблицы. Бинарные деревья поиска. Три варианта обхода бинарного дерева. Сильно ветвящиеся деревья. Красно-черные деревья. Динамическое программирование. Жадные алгоритмы. B-деревья. Граф как наиболее общая структура данных. Основные понятия теории графов. Представление графа в математике и на языках программирования. Программное обеспечение для визуализации графов. Элементарные алгоритмы для работы с графами. Алгоритмы установления изоморфизма графов. Минимальные остовные деревья. Кратчайшие пути из одной вершины. Кратчайшие пути между всеми парами вершин. Алгоритм построения транзитивного замыкания. Задача о максимальном потоке. Задача коммивояжёра: определение, алгоритм Литтла, алгоритм Кристофидиса, алгоритмы, заимствованные у природы (генетические алгоритмы, муравьиные алгоритмы). Распределённые алгоритмы. Прикладные задачи на графах: Транспортные сети, социальные сети, семантические сети, конечные автоматы​, турниры. Алгоритмы раскрашивания графов.

ФОС для проведения промежуточной аттестации одобрен на заседании кафедры математического и компьютерного моделирования (протокол № ____ от _____________ 20____года).

Автор:

к. ф-м. н., доцент