Ф-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине "Алгоритмизация"




Скачать 43.14 Kb.
НазваниеФ-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине "Алгоритмизация"
Дата публикации09.08.2013
Размер43.14 Kb.
ТипРабочая программа
zadocs.ru > Информатика > Рабочая программа

Федеральное агентство по образованию

Ульяновский государственный университет

Форма



Ф-Рабочая программа по дисциплине







Примерный перечень вопросов к экзамену

по дисциплине "Алгоритмизация"


1. Основные понятия теории алгоритмов (^ Алгоритм, свойства алгоритма. Формы представления алгоритмов. Основные алгоритмические конструкции)

2. Формализация понятия алгоритма (Массовая и индивидуальная задачи. Алгоритм. Направления основных формализмов теории алгоритмов. Способы описания алгоритма: машины Поста)

3. Основные этапы решения алгоритмической задачи (Понимание задачи. Выбор вычислительных средств, структуры данных, методик проектирования алгоритма. разработка алгоритма. Оценка корректности алгоритма. Анализ алгоритма. Реализация алгоритма)

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

5. Классы эффективности алгоритмов (Порядок роста функции трудоемкости. Асимптотические классы эффективности. Классификация алгоритмов по типу зависимости функции трудоемкости от характеристик входных данных. Сложностные классы задач. Общий план анализа нерекурсивных алгоритмов. Общий план анализа рекурсивных алгоритмов. Эмпирический анализ алгоритмов. Визуализация алгоритмов)

6. Методика «грубой силы» разработки алгоритмов (Определение. Алгоритмы и задачи: сортировка выбором, пузырьковая сортировка, последовательный поиск, поиск подстроки, задача о паре двух ближайших точек, задача о выпуклой оболочке, задача коммивояжера, задача о рюкзаке, задача о назначениях)

7. Методика декомпозиции (^ Определение. Алгоритмы и задачи: сортировка слиянием, бинарный поиск, быстрая сортировка, задача о паре двух ближайших точек, задача о выпуклой оболочке)

8. Методика уменьшения размерности (Определение. Алгоритмы и задачи: сортировка вставкой, задача поиска фальшивой монеты, задача Иосифа)

9. Методика преобразования (Определение. Алгоритмы и задачи: схема Горнера вычисления значения полинома в точке, бинарное возведение в степень, пирамидальная сортировка, приведение задач, задача линейного программирования, задача целочисленного линейного программирования)

10. Методика пространственно-временного компромисса (^ Определение. Алгоритмы и задачи: алгоритмы Бойера-Мура и Хорспула поиска подстроки)

11. Методика динамического программирования (Определение. Алгоритмы и задачи: вычисление биномиальных коэффициентов, алгоритм Флойда)

12. Методика «жадные алгоритмы» (Определение. Алгоритмы и задачи : задача о размене денег)

13. Методика поиска с возвратом» (Определение. Алгоритмы и задачи: задача о n-ферзях)

14. Методика ветвей и границ (Определение. Алгоритмы и задачи: задача о рюкзаке)

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

17. Эфективность применения генетических алгоритмов (Области применения. Основные характеристики ГА: скорость и устойчивость. Способы повышения скорости генетического алгоритма: распараллеливание, кластеризация. Способы повышения устойчивости генетического алгоритма: родительское воспроизводство с рекомбинацией и мутацией, одноточечный, двухточечный и равномерный операторы скрещивания, стратегия разнообразия оператора мутации, рангово-пропорциональный отбор родителей, удаление наихудших в операторе редукции. Адаптивные генетические алгоритмы)

18. Графы (Представление графов в виде: матрицы смежности, списочными структурами с двумя адресными полями, массива списков смежных вершин, матрицы смежности для взвешенных графов. Операции над графами. Алгоритмы обхода графа в глубину, в ширину. Подсчет путей в графе. Алгоритм Прима-Дейкстры построения минимального остовного дерева взвешенного графа. Алгоритм Крускала построения минимального остовного дерева взвешенного графа.)

19. Деревья общего вида (Основные понятия: определение, степень узла, степень дерева, лист, уровень узла, предок, потомок, высота дерева, полное дерево. Основные свойства деревьев. Представление дерева списочной структурой)
20. Алгоритм Штрассена для умножения матриц

21. Генерация перестановок

22. Генерация подмножеств

23. Топологическая сортировка

24. Пирамидальная сортировка

25. Алгоритм Хорспула поиска подстрок

26. Алгоритм Бойера-Мура поиска подстрок

27. Алгоритм открытого хеширования реализации словарей

28. Алгоритм закрытого хеширования реализации словарей

29. Алгоритм Воршалла вычисления транзитивного замыкания орграфа

30. Алгоритм Флойда поиска кратчайшего (их) пути (ей) в графе

31. Деревья Хаффмана кодирования текста

32. Симплекс-метод решения задач линейного программирования

33. Венгерский метод решения задачи о назначениях

34. Сортировка Шелла

35. Интерполяционный поиск

36. Приближенный алгоритм решения задачи коммивояжера

37. Приближенные алгоритмы решения задачи о рюкзаке


Доцент Чекал Е.Г.

Форма А Страница из

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

Похожие:

Ф-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине \"Алгоритмизация\" iconПримерный перечень вопросов к экзамену по дисциплине «Психология профессиональной деятельности»

Ф-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине \"Алгоритмизация\" iconПримерный перечень вопросов для подготовки к экзамену по дисциплине...

Ф-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине \"Алгоритмизация\" iconОсновные направления правоохранительной деятельности
Примерный перечень вопросов для подготовки к экзамену по дисциплине «Правоохранительные органы рф»

Ф-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине \"Алгоритмизация\" iconПримерный перечень вопросов к экзамену по дисциплине «Конституционное право»
Сущность, функции и юридические свойства (признаки) конституции как основного источника конституционного права

Ф-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине \"Алгоритмизация\" iconПримерный перечень вопросов для подготовки к экзамену по дисциплине «Макроэкономика»
Характерные особенности макроэкономики как науки. Особенности макроэкономического анализа

Ф-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине \"Алгоритмизация\" iconА. А. Ходусов примерный перечень вопросов к экзамену по дисциплине «Уголовное право»
Уголовная ответственность как вид юридической ответственности. Основание уголовной ответственности

Ф-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине \"Алгоритмизация\" iconПримерный перечень экзаменационных вопросов по дисциплине «Политология»

Ф-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине \"Алгоритмизация\" iconПримерный Перечень вопросов для подготовки к экзамену по учебной...
Полномочия, функции, структура, кадровое и материальное обеспечение органов предварительного следствия в системе мвд россии

Ф-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине \"Алгоритмизация\" iconПримерный перечень вопросов теста к экзамену по дисциплине «Компьютерные...
Значок на рабочем столе Windows, который предоставляет доступ к ресурсам компьютера (дискам, папкам, принтерам) это

Ф-рабочая программа по дисциплине Примерный перечень вопросов к экзамену по дисциплине \"Алгоритмизация\" iconПримерный перечень вопросов к экзамену
Основные понятия электронных таблиц: рабочая книга, рабочий лист, строка, столбец, ячейка, адрес ячейки

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


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

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