Tallinna Tehnika Ülikool Virumaa Kolledž Inna Dokutšajeva 2011

Требования к начальному уровню знаний: положительная оценка за курс « RAR0280 Programmeerimise põhukursus »

В рамках курса изучаются: общие понятия алгоритмов и структур данных, указателей и способов выделения и освобождения динамической памяти; структур данных «динамические массивы», «очереди», «стека», «списка», «деревьев», «графов»; рекурсивных задач; контейнеров, итераторов; известных алгоритмов поиска подстроки в строке (прямой поиск, алгоритм Кнута, Морриса и Пратта, алгоритм Бойера и Мура); общих понятий и принципов хеширования, составления хэш-таблиц, методов разрешения коллизий, алгоритмов.

Учебные материалы электронного курса по темам: 1.Введение 2.Указатели 3.Динамические массивы 4.Представление структур данных посредством динамических массивов 5.Рекурсия 6.Стеки 7.Очереди 8.Списки 9.Деревья 10.Графы 11.STL-контейнеры 12.Алгоритмы классических сортировок 13.Алгоритмы поиска в тексте 14.Алгоритмы сжатия данных 15.Hash-Таблицы и хэширование данных

Краткое содержание электронного курса: 1.В теме «Введение» даются общие понятия алгоритмов и структур данных, которые более подробно рассматриваются в последующих разделах, а также распределение статической и динамической памяти. 2.В теме «Указатели» рассматривается указательный тип данных и связь указателей и массивов данных. 3.В теме «Динамические массивы» предлагается учебный материал, в котором рассматриваются алгоритмы обработки массивов в динамической памяти. 4.В теме «Представление структур данных посредством динамических массивов» рассматриваются алгоритмы создания и обработки списков, очередей, стеков и деревьев посредством динамических массивов. 5.В теме «Рекурсия» рассматриваются классические рекурсивные задачи, например, такие как 'Ханойские башни', даётся сравнительный анализ рекурсивных и не рекурсивных функций. 6.В теме «Стеки» рассматриваются основные алгоритмы создания динамического стека, добавления элемента в стек, удаления элемента из стека, удаления всего стека, вывод стека для просмотра, а также некоторые прикладные задачи, использующие динамический стек.

7.В теме «Очереди» рассматриваются основные алгоритмы создания динамической очереди, добавления элемента в очередь, удаления элемента из очереди, удаления всей очереди, вывод очереди для просмотра, а также некоторые прикладные задачи, использующие динамическую очередь. 8.В теме «Списки» рассматриваются основные алгоритмы создания динамического списка, добавления элемента в список, удаления элемента из списка, удаления всего списка из динамической памяти, вывод списка. 9.В теме «Деревья» рассматриваются основные понятия и алгоритмы для создания бинарного дерева в динамической памяти, добавления узла в дерево, удаления узла из дерева, удаления всего дерева из динамической памяти, вывод дерева на экран. 10.В теме «Графы» рассматриваются алгоритмы представления и обхода графов 11.В теме «STL-контейнеры» рассматриваются контейнеры, алгоритмы, итераторы, функциональные объекты, контейнерные классы, содержащиеся в стандартной библиотеке шаблонов. 12.В теме «Алгоритмы классических сортировок» рассмотрены алгоритмы классических сортировок для упорядочения наборов данных по определённому признаку.

13.В теме «Алгоритмы поиска в тексте» рассмотрены несколько известных алгоритмов поиска подстроки в строке (прямой поиск, алгоритм Кнута, Морриса и Пратта, алгоритм Бойера и Мура). 14.В теме «Алгоритмы сжатия данных» рассмотрен метод сжатия информации, предложенный Хаффманом. 15.В теме «Hash-Таблицы и хеширование данных» даны общие понятия хеширования, хэш-таблиц, методов разрешения коллизий (метод цепочек, метод открытой адресации), рассмотрены алгоритмы хеширования (таблица прямого доступа, метод остатков от деления, метод функции середины квадрата, метод свёртки).

Курс содержит: 1. Лекции в виде презентаций 2. Видео презентации 3. Примеры на изучаемую тему 4.Домашние задания 5. Тесты

Для допуска к экзамену студент должен выполнить все домашние задания на оценку не ниже «2» (удовлетворительно) в соответствии с назначенными сроками, но не позднее предпоследнего дня окончания аудиторных занятий. В случае невыполнения этого требования, студент к экзамену не допускается. Итоговая оценка за курс – это оценка, полученная студентом на экзамене. Критерии оценивания домашних работ: 1.программа должна компилироваться и выдавать результаты на экран; 2.текст программы должен быть структурирован; 3.программа должна быть снабжена подробными комментариями; 4.программа должна содержать функции и меню вызова этих функций для пользователя, например, 1 – создать список, 2 – добавить элемент в список, и т.д.

Руководство по использованию учебных материалов, опубликованных в интернет-среде: Для просмотра презентаций можно скачать бесплатную программу PowerPoint Viewer Для выполнения домашних заданий можно установить бесплатную программу Microsoft Visual C++ Express Edition, например, отсюда us/products/2010-editions/visual-cpp-expresshttp:// us/products/2010-editions/visual-cpp-express С техническими проблемами (регистрация, проблемы с отправкой файлов и т.п.), можно обращаться к технологу по образованию Дополнительную информацию для регистрации можно получить по следующему адресу: Дополнительную информацию по среде Moodle, можно получить на следующем сайте teacherguid/index.html

Использованная литература при создании курса: 1. Каррано, Причард. Абстракция данных и решение задач на C++. Стены и зеркала К. Поляков. Динамические структуры данных Бондарев. Программирование на С Липпман. C++ для начинающих Дейтель. C Глушаков. Язык программирования C Шилдт. Самоучитель C И.В.Ашарина. Объектно-ориентированное программирование в С А.Крячков, И.Сухинина, В.Томшин. Программирование на С и С++. Практикум. 2000