- •Санкт-Петербург – 2011
- •Раздел 1. Характеристики, структура и содержание учебных занятий
- •Цели и результаты учебных занятий.
- •Требования к подготовленности обучающегося к освоению содержания учебных занятий (пререквизиты).
- •Перечень формируемых компетенций (результаты обучения)
- •Знания, умения, навыки, осваиваемые обучающимся.
- •Перечень и объём активных и интерактивных форм учебных занятий.
- •Организация учебных занятий.
- •1.6.1. Трудоёмкость, объёмы учебной работы и наполняемость
- •1.6.2. Виды, формы и сроки текущего контроля успеваемости и промежуточной аттестации
- •1.7. Структура и содержание учебных занятий
- •Раздел 2. Обеспечение учебной дисциплины
- •2.1. Методическое обеспечение
- •2.1.1. Методическое обеспечение аудиторной работы
- •2.1.2. Методическое обеспечение самостоятельной работы
- •2.1.3. Методика проведения текущего контроля успеваемости, промежуточной аттестации и критерия оценивания
- •2.3.2. Требования к аудиторному оборудованию, в том числе к неспециализированному компьютерному оборудованию и программному обеспечению общего пользования
- •2.4.2. Список дополнительной литературы
- •2.4.3. Перечень иных информационных источников
- •Раздел 3. Процедура разработки и утверждение рабочей программы учебной дисциплины
- •Иные документы об оценке качества рабочей программы
- •Внесение изменений в рабочую программу
- •Приложение с1-1
- •1. Еженедельный отчет студента
- •2. Регулярный контроль на аудиторном занятии
- •3. Итоговый контроль на зачетных и экзаменационных мероприятиях
- •Приложение с1-2
- •Приложение с1-3
- •1. Файлы
- •2. Процедуры и функции
- •3. Циклы, массивы, вычисления
- •04. Множества, строки, записи
- •5. Логические выражения и операторы ветвления.
- •Приложение с1-4
- •Ооп: инкапсуляция
- •Ооп: полиморфизм
- •Приложение с1-5
- •Приложение с2-1
- •1. Еженедельный отчет студента
- •2. Регулярный контроль на аудиторном занятии
- •3. Итоговый контроль на зачетных и экзаменационных мероприятиях
- •Приложение с2-2
- •Приложение с2-3
- •1. Файлы
- •2. Процедуры и функции
- •3. Циклы, массивы, вычисления.
- •4. Множества, строки, записи
- •5. Графика
- •6. Сортировки (быстрая сортировка — имеется ввиду нерандомизированная):
- •7. Рекурсия
- •8. Разработка и программная реализация алгоритмов
- •9. Перебор
- •10. Бинарные деревья и поиск
- •11. Перестановки
- •12. Графы
- •13. Стек, очередь, очередь с приоритетатами
- •14. Списки, хеш-таблицы, сбалансированные деревья.
- •Приложение с2-4
- •Приложение с2-5
5. Графика
(Упражнения выполняются с помощью графического пользовательского интерфейса)
05.01. [1]
05.01.1. В декартовой системе координат на плоскости
05.01.2. В полярной системе координат на плоскости
вывести график параметрической функции (зависит от одного параметра t). Пользователь задает диапазон изменения параметра и его «шаг» dt. Возможно, пользователь задает и другие параметры (по усмотрению разработчика программы.) Предусмотреть выбор 3–4 разных функций для каждой системы координат.
05.02. [2] В таблице/в файле введен список точек на плоскости. Можно выбрать как целочисленные, так и вещественные координаты. В отдельной компоненте построить список точек, задающих минимальную выпуклую оболочку изначально заданных точек. Обеспечить вывод/удаление (по-отдельности) на TImage точек исходного списка, экстремальных точек выпуклой оболочки, многоугольника с вершинами в экстремальных точках. Обеспечить сохранение/загрузку исходного списка точек в файл / из файла. Цвета и прочие характеристики объектов подобрать разумным образом.
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
(При выполнении упражнений требуется разрабатывать программы с графическим пользовательским интерфейсом).
Рекомендуется пользоваться книгой Лафоре Р. Структуры данных и алгоритмы в Java. Классика Computer Science. 2-е изд. — СПб.: Питер. 2011. 704 с.
6. Сортировки (быстрая сортировка — имеется ввиду нерандомизированная):
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8
http://ru.wikibooks.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8
http://www.youtube.com/results?search_query=sort+algorithm
Упражнение 6.01. [0] Реализовать быструю сортировку и сортировку пузырьком. Сравнить производительность на различных размерах данных. Найти размер данных, когда разница времени исполнения становиться видна.
Упражнение 6.02. [0] Реализовать сортировку вставками и сортировку Шелла. Сравнить производительность на различных размерах данных. Найти размер данных, когда разница времени исполнения становиться видна.
Упражнение 6.03. [1] Реализовать быструю сортировку и сортировку пузырьком. Сравнить производительность на различных данных. Подумать и найти случай когда стандартная быстрая сортировка работает за такое же время.
Упражнение 6.04. [1] Реализовать поразрядную сортировку (radix sort) и сравнить ее с быстрой сортировкой на различных размерах данных
Упражнение 6.05. [1] Реализовать сортировку слиянием для N массивов
7. Рекурсия
http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F
http://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F
http://www.structur.h1.ru/recurs.htm
http://comp-science.narod.ru/Progr/Rekursia.html
Упражнение 7.01. [0] Вычислить N-ю строку треугольника Паскаля рекурсивным и итеративным способом
Упражнение 7.02. [0] Вычислить рекурсивным и итеративным способом N-ое число Фибонначи
Упражнение 7.03. [0] Вычислить рекурсивно детерминант матрицы N*N.
Упражнение 7.04. [0] Дан массив 1..N. В клетках записаны целые неотрицательные числа. С помощью процедуры перехода с позиции N можно перейти на позицию N+1 или N+3. Определить с помощью рекурсии можно ли собрать сумму чисел K. Стартуем с первого элемента массива
Упражнение 7.05. [0] В урну на каждом шагу могут бросить N1 черных и M1 белых шаров, либо N2 черных и M2 белых шаров. Выяснить с помощью рекурсии, можно ли получить N3 черных и M3 белых шаров через K ходов.
Упражнение 7.06. [1] Дано шахматное поле 8*8 и фигура коня стоящая на позиции (1, 1). Выяснить, сможет ли она за N ходов достичь поля (8, 8).
Упражнение 7.07. [1] Нарисовать любой фрактал рекурсивных способом из следующего списка: Треугольник Серпинского, Кривая Коха, Кривая Леви, Канторово множество, Кривая дракона, Ковер Серпинского, Дерево Пифагора, Круговой фрактал.
Про эти фракталы можно прочитать тут: http://ru.wikipedia.org/wiki/%D0%A4%D1%80%D0%B0%D0%BA%D1%82%D0%B0%D0%BB
Упражнение 7.08. [1] Сгенерировать все перестановки из набора 1, 2, 3, …, N с помощью рекурсивного алгоритма.
Упражнение 7.09. [1] Дана схема состоящая из сопротивлений ri. Рассчитать суммарное сопротивление цепи. Если сопротивления соединены последовательно, то сопротивления складываются. Если параллельно то общее сопротивление есть (r1*r2)/(r1+r2).
Упражнение 7.10. [1] Дан массив и функция от N переменных. Рекурсивно вычислить левую свертку от него.
Свертка это f(…f(f(e1, e2, …, en1), en1+1, en2+2, … e2*n1-1)…)
Упражнение 7.11. [2] Есть наборы бусинок различных цветов: Красный (K штук), Синий (L штук), Зеленый (M штук).
Существуют правила: синяя не может идти за красной, красная не может быть на четной позиции
С помощью рекурсивной функции подсчитать сколько может быть собрано различных бус длины M, по данным правилам. На место склейки – правила не распространяется