Алгоритмы и структуры данных 1-й семестр

Темы к зачету и задания от лектора (2012/13)
 Лекции и задачи по АиСД.docx
Темы заданий:
1. Реализация классов.
Примеры заданий: классы матриц, веткоров, комплексных чисел, списков, многочленов и т.д. с решений практической задачи и ami.hse.ru/aisd_1sперегрузкой операторов.
Можно использовать проект http://math.msu.su/~vvb/HSE/Projects/R2Graph.zip
2. Стековый консольный калькулятор.
Примеры заданий: дописать реализацию функция из math.h + меню, быстрое/умное возведение в степень, реализация функция при помощи ряда Тейлора с точностью eps и оценкой радиуса сходимости. Обязательно использование стека, ПОЛИЗа без приоритета операций, проверка входных данных на корректность.
Можно использовать проект http://math.msu.su/~vvb/HSE/Projects/StackCalc.zip
3. Основы MFC
Примеры заданий: отметить кликами левой кнопки мыши три точки в окне программы, по нажатию правой кнпки мыши вывести вписанную и описанную окружности, или вывести сообщение о вырожденности треугольника.
4. Сортировки массивов.
Примеры заданий: сортировки массивов собственными процедурами и стандартными, с отображением графиков работы сортировки на входных данных до 50•10⁶ (50 миллионов) чисел типа double.
Программа должна быть разделена на 2 части:
3.1 Отображение графика ломаной по текстовому файлу с координатами точек
3.2 Вывод врмени сортировки 2-мя способами на случайном массиве по входному параметру - длине массива.
3.2* Программа 3.2 дома запускается в цикле и по ней строится график.
Быстрая сортировка должна иметь
    a) не более logN рекурсий
    b) использовать простую сортировку на малых массивах длины меньше M.
    c) M вводится с клаиватуры при проверке в классе. Дома нужно найти оптимальное M для больших N.
Пирамидальная сортировка должна использовать сортировочное дерево. Нужно сделать ее устойчивой.
При написании своей сортировки нельзя пользоваться стандартными средствами, связанными с сортировками.
Пример программы для подсчета времени:
http://www.cplusplus.com/reference/ctime/clock/
Важными здесь являются строчки    Time.h help
Пример программы для стандартных сортировок с параметрами:
http://www.cplusplus.com/reference/cstdlib/qsort/
http://www.cplusplus.com/reference/algorithm/sort_heap/
Для вывода графика функции можно использовать проект http://math.msu.su/~vvb/HSE/Projects/Func.zip
5. База Данных (+ задачи 6,7)
Сложный и простые поиски, сортировка по полям, нечеткое условие по полям, поиск по маске как бонус.
По списку лектора стр.3-4
6. В зависимости от распределения сделать 1 из 2 задач:
6а) По 1 из полей посторить AVL-дерево из указателей на элементы БД, написать процедуры добавления и удаления в AVL-дерево (с балансировкой), вывод на печать, оценка времени поиска как 1.5*logN
6в) По 1 из полей реализаовать хэш-таблицу методом проб и ошибок и списочной реализацией. Реализовать основные операции множества. Время поиска должно быть константа.
7. Реализовать кодирование Хаффмана по 1 из полей, считая, что сообщением является кокретное поле отдельного элемента и вывести алфавит. На бонус: реализовать адаптированное кодирование Хаффмана для сообщения, передающегося через поток.
8. Реализовать 1 из 3 задач:  |V|=n, |E|=m,
1. Изоморфизм графов + вершинная связность за время O(N^2*M)   (результат - 2 ответа на 2 вопроса <<).
2. Найти в графе G1 все подграфы, изоморфные G2.
3. Найти все клики в графе.
Иметь свои тестовые примеры для тривиальных случаев и для случайных графов. Запуск загрузки файла из консоли.
Графическое изображение алгоритмов или доказательства изоморфизма оценивается дополнительно.
9-10.  Задачи по Графам 2013_2-3.doc (внимательно читайте условие!!!)
11.     Финальное задание (внимательно читайте условие!!!)

 Требования к сдаче программ:
    1. Указание в имени файла/архива/проекта в следующем порядке
     Группа_Фамилия_ИО_ДЗ№_Вариант№_VSверсия№_Проект(Консоль/Приложение_Win32)
    2. Комментарии к программе
    3. Отсутствие вычислений в main, минимальное использование глобальных переменных и аморфных наборов переменных без структур.
    4. Возможность запустить один раз программу с повторным вводом в цикле.
    5. Наличие интерфейса программы (без необходимости scrollить окно программы вверх)
         - что требуется ввести
         - что выдает программа
         - отображение helpа по командам если таковые присутствуют
         - точное описание ошибки
    6. Обработка ошибок, за исключением ввода букв вместо цифр   
    7. Наличие скриншотов тестовых примеров, правильный подбор тестовых примеров на исключительные случаи, c возможность
Проверка ассистентом программы:
    Ассистент 272 группы Мункоева Айлана <lanm2608@gmail.com>
    Ассистент проверяет программу по критериям, написанным выше, проверяет актуальностьтестовых примеров и их соответствие
    присланной программе, вводит свои тестовые примеры.
    Результатом проверки ассистентом программы является таблица соответствий пунктам 1-7 по фамилиям, в которую включаются
    тестовые примеры, на которых программа не работает/работает неправильно, или указывается, что программа работает правильно.

  Ссылка на материалы В.В. Борисенко:
http://math.msu.su/~vvb/HSE/HSEtasks.htm
  Ссылка на материалы по графике:
http://www.codenet.ru/progr/visualc/mfc/
http://www.firststeps.ru/mfc/steps/
http://msdn.microsoft.com/ru-ru/library/