Аннотация
Уже в первом модуле курса рассматриваются вопросы оценки времени выполнения алгоритмов, как составной части решения поставленной задачи, поскольку для задач больших размеров важную роль играет не только мощность вычислительных средств, но и эффективность алгоритма. Далее будут рассмотрены основные структуры данных, в контексте которых мы посмотрим на односвязные и двухсвязные списки, динамические массивы, стеки, очереди, деревья и множества. Мы детально познакомимся с алгоритмами сортировки, с понятиями «хеш-таблицы» и «В-деревья». Заключительный Модуль нашего курса будет посвящен решению практических примеров - задачи коммивояжера, задачи о ханойских башнях и задачи триангуляции.
Аудитория
Курс предназначен для начинающих программистов и тех, кто имеет базовые знания о программировании или желает их усовершенствовать.
Предварительная подготовка
- Уверенное владение персональным компьютером
- Базовые знания языка программирования C#
- Навыки работы с текстовыми редакторами, средой разработки Visual Studio
Программа
1.Введение в структуры и алгоритмы данных. Связные списки
- Понятие алгоритма и структуры данных.
- Понятие временной и асимптотической сложности алгоритма.
- Использование О-нотации.
- Обзор основных структур данных.
- Обзор односвязных списков.
- Двусвязные списки.
- Примеры реализации связных списков на C#
2. ArrayList
- Реализация динамического массива на C#.
- Обзор класса ArrayList.
- Добавление элементов в динамический массив.
- Политики роста динамического массива.
- Удаление элементов из массива.
- Индексация элементов.
3. Stack и Queue
- Обзор структуры данных - стек.
- Реализация стека на основе двухсвязных списков на C#.
- Методы Push, Pop, Peek, Count.
- Обзор структуры данных – очередь. Уже в первом модуле курса рассматриваются вопросы оценки времени выполнения алгоритмов, как составной части решения поставленной задачи, поскольку для задач больших размеров важную роль играет не только мощность вычислительных средств, но и эффективность алгоритма. Далее будут рассмотрены основные структуры данных, в контексте которых мы посмотрим на односвязные и двухсвязные списки, динамические массивы, стеки, очереди, деревья и множества. Мы детально познакомимся с алгоритмами сортировки, с понятиями «хеш-таблицы» и «В-деревья». Заключительный Модуль нашего курса будет посвящен решению практических примеров - задачи коммивояжера, задачи о ханойских башнях и задачи триангуляции.
Аудитория
Курс предназначен для начинающих программистов и тех, кто имеет базовые знания о программировании или желает их усовершенствовать.
Предварительная подготовка
- Уверенное владение персональным компьютером
- Базовые знания языка программирования C#
- Навыки работы с текстовыми редакторами, средой разработки Visual Studio
Программа
1.Введение в структуры и алгоритмы данных. Связные списки
- Понятие алгоритма и структуры данных.
- Понятие временной и асимптотической сложности алгоритма.
- Использование О-нотации.
- Обзор основных структур данных.
- Обзор односвязных списков.
- Двусвязные списки.
- Примеры реализации связных списков на C#
2. ArrayList
- Реализация динамического массива на C#.
- Обзор класса ArrayList.
- Добавление элементов в динамический массив.
- Политики роста динамического массива.
- Удаление элементов из массива.
- Индексация элементов.
3. Stack и Queue
- Обзор структуры данных - стек.
- Реализация стека на основе двухсвязных списков на C#.
- Методы Push, Pop, Peek, Count.
- Реализация методов Enqueue, Dequeue, Peek, Count.
- Обзор структуры данных двусвязная очередь (дек).
- Реализации двухсвязной очереди на основе списков.
- Реализация стека на основе двухсвязной очереди.
- Реализация двухсвязной очереди на основе массива.
4.Деревья
- Структура данных – дерево.
- Реализация дерева на основе массива.
- Реализация бинарного дерева поиска на C#.
- Добавление, удаление и поиск узлов дерева.
- Прямой, обратный и симметричный обход дерева.
5. Множество
- Структура данных – множество.
- Реализация класса Set.
- Добавление и удаление элементов и поиск элементов множества.
- Объединение, пересечение, разность, симметрическая разность двух множеств.
6. Алгоритмы сортировки
- Сортировка пузырьком.
- Сортировка вставками.
- Сортировка выбором.
- Сортировка слиянием.
- Сортировка Шелла.
- Быстрая сортировка.
7. Хеш-таблицы
- Описание структуры данных - хеш-таблицы.
- Хеш-функция.
- Коллизии хеш-функции.
- Реализация хеш-таблицы на C#.
8. B-деревья
- Описание В-дерева.
- Реализация В-дерева на C#.
- Поиск, добавление и удаление записей в В-дереве.
- Время выполнения операций В-деревом.
9. Задачи
- Задача коммивояжёра.
- Задача Ханойские башни.
- Задача триангуляции.