Учебно-методический комплекс по дисциплине «б в. 7»






НазваниеУчебно-методический комплекс по дисциплине «б в. 7»
страница4/11
Дата публикации04.12.2014
Размер1.36 Mb.
ТипУчебно-методический комплекс
top-bal.ru > Информатика > Учебно-методический комплекс
1   2   3   4   5   6   7   8   9   10   11
^
Лекция № 17, 18. Рандомизированные алгоритмы.

Понятие рандомизированного алгоритма и примеры использования. Генераторы случайных чисел (ГСЧ). Аппаратные ГСЧ. Программные ГСЧ.

Генерация случайных чисел Генерирование равномерно распределенных случайных чисел Линейный конгруэнтный метод.

Тестирование ГСЧ Критерий Хи-квадрат. Метод средних квадратов.

Применение ГСЧ. Метод Монте-Карло.

^
Лекция № 19. Ориентированные графы

Графы: определения и примеры. Упорядоченный граф. Представления графов: матрица инциденций, матрица смежности, список пар, структура смежности (списки инцидентности). Преобразования представлений.

Остовные деревья графа. Минимальное остовное дерево.
^
Лекция № 20, 21. Алгоритмы на графах

Поиск в графе: алгоритм пометок. Поиск в ширину. Поиск в глубину.

Связные компоненты. Алгоритм сложности О(m*log n) построения минимального остова. Построение и свойства остовных деревьев при поиске в глубину и в ширину. Поиск в глубину и топологическая сортировка.

Нахождение компонент двусвязности: точки сочленения графа и их свойства в глубинном остовном дереве. Алгоритм нахождения компонент двусвязности.

Сильная связность. Поиск в глубину в орграфе. Алгоритм нахождения сильно связных компонент.

Кратчайшие пути в графе. Кратчайшие пути от фиксированной вершины. Случай неотрицательных весов: алгоритм Дейкстры. Алгоритм Форда-Беллмана. Кратчайшие пути в бесконтурном графе.


4.7. 2.Содержание лабораторных работ
Лабораторная работа №1 (4 ч)

Тема: Основные типы данных

Содержание

  1. Переменные символьного и строкового типов.

  2. Отработка практических навыков составления программ по обработке символьных данных

  3. Отработка практических навыков составления алгоритмов по обработке строк.

  4. Реализация программы на ПЭВМ.

  5. Выполнение индивидуальных заданий

  6. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [5] c.37-50, [6] c.107-114, [12] c.7-15

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа №2 (4 ч)

Тема: Указатели. Динамическая память.

Содержание

  1. Переменные указательного типа.

  2. Отработка практических навыков составления программ с использованием указателей.

  3. Реализация программы на ПЭВМ.

  4. Выполнение индивидуальных заданий

  5. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [5] c.42-54, [7] c.17-24, [12] c.17-29

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 3(2 ч)

Тема: Стандартные массивы

Содержание

  1. Формирование линейных массивов.

  2. Формирование двухмерных массивов.

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

  4. Отработка практических навыков составления алгоритмов обработки массивов.

  5. Реализация программы на ПЭВМ.

  6. Выполнение индивидуальных заданий

  7. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [1] c.5-8, [9] c.17-20

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 4(2 ч)

Тема: Динамические массивы

Содержание

  1. Формирование динамических массивов.

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

  3. Отработка практических навыков составления алгоритмов обработки динамических массивов.

  4. Реализация программы на ПЭВМ.

  5. Выполнение индивидуальных заданий

  6. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [1] c.9-12, [9] c.21-25, [10] c.14-15

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 5(2 ч)

Тема: Записи и таблицы

Содержание

  1. Переменные типа запись.

  2. Отработка практических навыков составления программ с использованием записей.

  3. Реализация программы на ПЭВМ.

  4. Выполнение индивидуальных заданий

  5. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [1] c.15-18, [9] c.25-28, [10] c.18-26

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 6(2 ч)

Тема: Множенства

Содержание

  1. Тип данных множество.

  2. Отработка практических навыков составления программ с использованием множеств.

  3. Реализация программы на ПЭВМ.

  4. Выполнение индивидуальных заданий

  5. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [1] c.19-22, [9] c.31-35, [10] c.32-40

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 7(2 ч)

Тема: Списки

Содержание

  1. Решение задач на формирование структур данных на основе списков и принципы их обработки (создание, вставка, удаление и т.д.).

  2. Отработка практических навыков составления программ с использованием списков.

  3. Реализация программы на ПЭВМ.

  4. Выполнение индивидуальных заданий

  5. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [1] c.25-28, [9] c.35-38

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 8(2 ч)

Тема: Стек

Содержание

  1. Решение задач на формирование структур данных на основе стеков и принципы их обработки (создание, вставка, удаление и т.д.).

  2. Отработка практических навыков составления программ с использованием списков.

  3. Реализация программы на ПЭВМ.

  4. Выполнение индивидуальных заданий

  5. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [1] c.35-40, [9] c.54-58, [10] c.68-74

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 9(2 ч)

Тема: Очередь

Содержание

  1. Решение задач на формирование структур данных на основе очереди и принципы их обработки (создание, вставка, удаление и т.д.).

  2. Отработка практических навыков составления программ с использованием списков.

  3. Реализация программы на ПЭВМ.

  4. Выполнение индивидуальных заданий

  5. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [1] c.35-40, [9] c.54-58, [10] c.68-74

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 10(2 ч)

Тема: Рекурсивные алгоритмы.

Содержание

  1. Решение задач на построение рекурсивных функций и процедур для рекуррентных отношений, возведение любого числа в любую степень, вычисление факториала, построение фракталов.

  2. Отработка практических навыков по составлению программ в среде Turbo Pascal с использованием рекурсии.

  3. Реализация программы на ПЭВМ.

  4. Выполнение индивидуальных заданий

  5. Анализ выполненных заданий.

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [2] c.5-8, [9] c.103-105, [10] c.97-101

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 11(4 ч)

Тема: Алгоритмы поиска данных

Содержание

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

  2. Реализация программы на ПЭВМ.

  3. Выполнение индивидуальных заданий

  4. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [2] c.8-10, [9] c.103-105, [10] c.97-101

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 12(6 ч)

Тема: Алгоритмы сортировки данных

Содержание

  1. Медленные алгоритмы сортировки: пузырьковая сортировка, шейкер-сортировка, сортировка методом выбора, сортировка методом вставок. Быстрые алгоритмы сортировки: сортировка методом Шелла, сортировка слиянием, быстрая сортировка.

  2. Решение задач на сортировку линейных массивов.

  3. Реализация программы на ПЭВМ.

  4. Выполнение индивидуальных заданий

  5. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [2] c.12-15, [8] c.103-105, [10] c.97-101

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 13(4 ч)

Тема: Рандомизированные алгоритмы.

Содержание

  1. Моделирование генераторов случайных чисел.

  2. Отработка практических навыков по разработке алгоритмов моделирования случайных процессов

  3. Реализация программы на ПЭВМ.

  4. Выполнение индивидуальных заданий

  5. Анализ выполненных заданий

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [5] c.137-154, [6] c.127-134

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы, выполнить тест для самоконтроля.
Лабораторная работа № 14(6 ч)

Тема: Алгоритмы на графах.

Содержание

  1. Поиск в графе: алгоритм пометок. Поиск в ширину. Поиск в глубину. Алгоритм порождения клик графа. Алгоритм Дейкстры. Алгоритм Форда-Беллмана.

  2. Отработка практических навыков составления алгоритмов поиска в графе.

  3. Реализация программы на ПЭВМ.

  4. Выполнение индивидуальных заданий

  5. Анализ выполненных заданий.

Методические рекомендации для подготовки к занятию

1.Литература для подготовки к занятию: [5] c.144-154, [6] c.137-144, [12] c.117-125

2. Задания для СРС: изучить лекционный материал, ответить на контрольные вопросы.

^ 4.8. Методическое обеспечение самостоятельной работы студентов.

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

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

Особое значение имеет самостоятельная работа студентов в компьютерном классе, где они должны получить прочные навыки реализации составленной программы на ЭВМ, умения по набору, редактированию и запуску программы. Одним из результатов самостоятельной работы за ЭВМ является развитие навыков по проведению анализа результатов выполнения программы, умения доказывать правильность составленного алгоритма.

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

Предусмотрены два коллоквиума - по материалу первого модуля (вопросы коллоквиума 1) и по материалу второго модуля (вопросы коллоквиума 2).

Для самоконтроля усвоения материала может быть банк тестовых заданий, предполагающий компьютерный вариант тестирования.
^ Содержание СРС

Тема

(раздел)

Содержание заданий,

выносимых на СРС

Количество часов, отводимых на выполнение заданий

Сроки проверки результатов СРС

Основные типы и структуры данных.

Коллоквиум.


6

24-25 уч.недели

Алгоритмы обработки данных

Коллоквиум.

Защита творческого проекта

6

12

27-28 уч.недели
30-31 уч.недели


^ 4.9. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины


      1. Организация текущего контроля

Для организации текущего контроля знаний по дисциплине «Структуры и алгоритмы обработки данных» по каждому модулю изучаемой дисциплины определены контрольные точки.
Первый модуль «Основные типы и структуры данных»:

  1. Защита лабораторных работ. Проводит преподаватель, ведущий лабораторные занятия.

  2. Компьютерное тестирование. Проводит преподаватель, ведущий лабораторные занятия.

  3. Коллоквиум. Проводит лектор


Второй модуль «Алгоритмы обработки данных»:

  1. Защита лабораторных работ. Проводит преподаватель, ведущий лабораторные занятия.

  2. Контрольная работа. Проводит и проверяет преподаватель, ведущий лабораторные занятия.

  3. Компьютерное тестирование. Проводит преподаватель, ведущий лабораторные занятия.

  4. Коллоквиум. Проводит лектор

  5. Защита творческого проекта. Проводит лектор.


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


      1. ^ Промежуточная аттестация по дисциплине

Промежуточная аттестация в первом семестре проводится в форме зачета. Зачет выставляется на основе балльно – рейтинговой системы. Нижняя граница баллов для выставления зачета равна 45 баллов.

Во втором семестре итоговой аттестацией по дисциплине является экзамен.
^ А. Формы промежуточного, рубежного и итогового контроля по дисциплине.

Тема

(раздел)

Формы контроля

Сроки контроля

Основные типы и структуры данных

Защита лабораторных работ. Компьютерное тестирование.

Коллоквиум

24-25 уч.недели

Алгоритмы обработки данных

Защита лабораторных работ. Контрольные работы.

Компьютерное тестирование.
Защита творческого проекта Коллоквиум.


27-28 уч.недели
30-31 уч.недели

Экзамен

Во время зимней сессии

Б. Примерные вопросы к экзамену.

  1. Понятие данных и структуры данных. Логическая и физическая структура данных.

  2. Классификация структур данных.

  3. Целый тип данных: диапазон допустимых значений, представление в памяти ЭВМ, допустимые операции.

  4. Вещественный тип данных: диапазон допустимых значений, представление в памяти ЭВМ, допустимые операции.

  5. Символьный и логический типы: диапазон допустимых значений, представление в памяти ЭВМ, допустимые операции.

  6. Перечисляемый тип данных: описание,  примеры использования.

  7. Интервальный тип пользователя данных: описание,  примеры использования.

  8. Составные статические структуры данных. Вектор. Физическая структура вектора.

  9. Двумерный массив и его представление в памяти.

  10. Операции над структурами данных.

  11. Записи и таблицы. Представление их в памяти ЭВМ.

  12. Множества. Операции над множествами.

  13. Строки и их представление в памяти ЭВМ.

  14. Указательный тип данных. Типизированные и не типизированные указатели.

  15. Динамическая память. Основные процедуры и функции работы с динамическими переменными.

  16. Списки. Однонаправленные списки. Типовые операции над однонаправленными списками

  17. Двунаправленные списки. Вставка и удаление элементов в двунаправленном списке

  18. Понятие стека. Стек на основе однонаправленных списков. Типовые операции над стеком.

  19. Понятие очереди. Очередь на основе однонаправленных списков. Типовые операции над очередями

  20. Эффективность алгоритмов.

  21. Классификация алгоритмов по их эффективности

  22. Понятие рекурсии. Преимущества и недостатки использования рекурсии. Примеры рекурсивных алгоритмов.

  23. Поиск данных. Алгоритм линейного поиска и оценка его эффективности

  24. Алгоритм бинарного поиска и оценка его эффективности

  25. Алгоритм  сортировки выбором и оценка его эффективности.

  26. Алгоритмы сортировки обменом и оценка его эффективности.

  27. Алгоритм сортировки вставками и оценка его эффективности.

  28. Алгоритм быстрой сортировки и оценка его эффективности.

  29. Рандомизированныеалгоритмы. Аппаратные и программные генераторы случайных чисел. Линейныеконгруэнтные ГСЧ.

  30. Применение ГСЧ. Метод Монте-Карло.


Д. Тематика и содержание контрольных работ
Контрольная работа 1.

Тема: Рекурсия. Алгоритмы поиска данных
Вариант 1.

  1. Составить рекурсивную функцию вычисления n-го члена последовательности: а1= 1, ai = ai-1*i. Найти сумму 2-го и 5-го членов последовательности.

  2. Сформировать массив a[1..n], элементы которого выбираются случайным образом из интервала [10, 90]. Определить, содержит ли он заданное число. Если элемент найден, то вставить перед ним элемент, вдвое больший найденного.

  3. Сформировать массив a[1..n], упорядоченный по возрастанию. Определить, содержит ли он заданное число. Если элемент не найден, то вставить его в массив на первое место.


Вариант 2.

  1. Составить рекурсивную функцию вычисления n-го члена последовательности: а1= 0, ai = 2*ai-1+i. Найти произведение 3-го и 7-го членов последовательности.

  2. Сформировать массив a[1..n], элементы которого выбираются случайным образом из интервала [100, 500]. Определить, содержит ли он заданное число. Если элемент не найден, то вставить его на 3-е место.

  3. Сформировать массив a[1..n], упорядоченный по возрастанию. Определить, содержит ли он заданное число. Если элемент найден, то вставить перед ним два новых элемента.


Вариант 3.

  1. Составить рекурсивную функцию нахождения суммы n членов арифметической прогрессии 1, 3, …Найти сумму с 5-го по 10-й членов прогрессии

  2. Сформировать массив a[1..n], элементы которого выбираются случайным образом из интервала [100, 200]. Определить, содержит ли он заданное число. Если элемент не найден, то вставить его в конец массива.

  3. Сформировать массив b[1..n], упорядоченный по убыванию. Определить, содержит ли он заданное число. Если элемент не найден, то вставить его в массив с сохранением упорядоченности.


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

Тема: Алгоритмы сортировки данных
Вариант 1.

  1. Задан массив a[1..20], элементы которого выбираются случайным образом из отрезка [-50, 50]. Отсортировать все элементы, стоящие на нечетных местах по невозрастанию.

  2. Задана матрица NxN. Отсортировать четные строки по невозрастанию.


Вариант 2.

  1. Задан массив B[1..15], элементы которого выбираются случайным образом из отрезка [0, 70[. Отсортировать все элементы с n-го по k-ый по неубыванию.

  2. Задана матрица MxN. Отсортировать нечетные строки по неубыванию.


Вариант 3.

  1. Задана матрица NxN. Отсортировать все столбцы по невозрастанию.

  2. Задан массив X[1..20[, элементы которого выбираются случайным образом из отрезка [-30, 80]. Отсортировать все элементы с 5-го по 15-й по невозрастанию.
1   2   3   4   5   6   7   8   9   10   11

Похожие:

Учебно-методический комплекс по дисциплине «б в. 7» iconУчебно-методический комплекс курс по выбору по дисциплине « дв4»
Учебно-методический комплекс по дисциплине " Технические и аудиовизуальные средства обучения"

Учебно-методический комплекс по дисциплине «б в. 7» iconУчебно-методический комплекс по дисциплине « Б2»
Учебно-методический комплекс (далее умк) по дисциплине «Информатика» разработан в соответствии с требованиями фгос впо к обязательному...

Учебно-методический комплекс по дисциплине «б в. 7» iconУчебно-методический комплекс по дисциплине Инженерная графика
Данный учебно-методический комплекс рассмотрен и утвержден на заседании Учебно-методической комиссии роат. Протокол №4 от 01. 07....

Учебно-методический комплекс по дисциплине «б в. 7» iconУчебно-методический комплекс по дисциплине Инженерная графика
...

Учебно-методический комплекс по дисциплине «б в. 7» iconУчебно-методический комплекс по дисциплине «Информатика»
Учебно-методический комплекс по дисциплине «Использование современных информационных и коммуникационных технологий» разработан в...

Учебно-методический комплекс по дисциплине «б в. 7» iconУчебно-методический комплекс по дисциплине «Информатика»
Учебно-методический комплекс по дисциплине «Использование современных информационных и коммуникационных технологий» разработан в...

Учебно-методический комплекс по дисциплине «б в. 7» iconУчебно-методический комплекс по дисциплине « дв12»
Учебно-методический комплекс по дисциплине " Технические и аудиовизуальные средства обучения"

Учебно-методический комплекс по дисциплине «б в. 7» iconУчебно-методический комплекс по дисциплине « дв32»
Учебно-методический комплекс по дисциплине " Технические и аудиовизуальные средства обучения"

Учебно-методический комплекс по дисциплине «б в. 7» iconУчебно-методический комплекс по дисциплине по выбору Б3
Учебно-методический комплекс по дисциплине «Логическое программирование» разработан в соответствии с требованиями фгос впо к обязательному...

Учебно-методический комплекс по дисциплине «б в. 7» iconУчебно-методический комплекс по дисциплине « В. 3»
Учебно-методический комплекс (далее умк) по дисциплине «Профессиональные компьютерные программы» разработан в соответствии с требованиями...



Школьные материалы


При копировании материала укажите ссылку © 2018
контакты
top-bal.ru

Поиск