Введение в дисциплину. Алгоритмы и структуры данных. Лекция 1

1.

АЛГОРИТМЫ И
СТРУКТУРЫ ДАННЫХ
Тема 1 Введение в
дисциплину
Pump up U

2.

Слайд 2
Смеляков Кирилл Сергеевич
профессор кафедры ЭВМ,
доктор технических наук,
профессор
R&D Interests*
Data Science, Data Mining, Artificial Intelligence,
Machine Vision and Pattern Recognition, Algorithms
and Data Structures
*R&D – Research and Development
Pump up U

3.

NURE Data Science
https://www.facebook.com/NUREDataScience
Слайд 3
Pump up U

4.

Тема 1 Введение в дисциплину
Outline
1
2
3
4
5
Слайд 4
Понятие алгоритма
Цели и задачи дисциплины
Структура дисциплины
Frequently Asked Questions (FAQ)
Литература и ресурсы
Lecturer ScD, Professor Kirill Smelyakov
Pump up U

5.

Тема 1 Введение
в дисциплину
1 Понятие
алгоритма
Pump up U

6.

Определение алгоритма
Слайд 6
Алгоритм – это формально описанный порядок действий
(операций), которые необходимо выполнить для решения
поставленной задачи за конечное число шагов.
Что значит формально? А это значит, что алгоритм составляется
на основе некоторого стандарта, который регламентирует:
типы данных,
действия с данными,
формы записи алгоритма.
Алгоритм для нас – это новое понятие???
Pump up U

7.

Определение алгоритма
Слайд 7
Описанию алгоритма предшествует постановка задачи (для
решения которой алгоритм и создается) обязательными
элементами которой, помимо функции цели, являются модели:
исходных данных на основе которых работает алгоритм, и
результатов решения поставленной задачи.
Например, при решении задачи сортировки, как минимум,
задают тип данных и отношение порядка элементов на выходе.
Постановка задачи может содержать дополнительные
ограничения и требования, например, по трудоемкости, или по
затратам памяти.
Pump up U

8.

Algorithm and Software
Слайд 8
Алгоритм – это прототип программной реализации, при
составлении которой, главным образом, отрабатывают логику
решения поставленной задачи. Алгоритм составляется для того,
чтобы понимать
как писать эффективный код
Описание алгоритма стараются минимально привязывать к
особенностям его программной реализации для долгого
времени жизни алгоритма и возможности выполнения на
различных устройствах.
Pump up U

9.

Наша система координат
Mathware Development
(Data Science / Mining, etc.)
лексическая / лексикографическая
Prototyping or Scientific Programming
(Python, R, etc.)
текст программы
Algorithms and Data Structures
лексическая / лексикографическая /
блок-схема / псевдокод
Слайд 9
Выполняется в
наукоемких
проектах
Разработка
эффективного кода,
развитие аналитических
способностей и навыка
алгоритмизации
Software Development (C++, etc.)
текст программы
Hardware Development
Pump up U

10.

Уровни познания алгоритма
Слайд 10
Разбор постановки задачи + Изучение принципа действия
Решение типовой задачи: (1) с учителем и (2) без учителя
Разбор модификаций (особое внимание бинарной версии)
Вывод оценок эффективности в отношении трудоемкости и
затрат памяти + рассмотрение зависимости по данным
Сравнительный анализ с аналогами
Программная реализация алгоритма
Экспериментальный анализ эффективности
Pump up U

11.

Слайд 11
Формализация познания алгоритма
No
Уровень познания \ Алгоритм
Алгоритм 1
…
Алгоритм n
1
Изучение принципа действия
√
…
√
2
Разбор типовой задачи
√
…
√
3
Разбор оценок эффективности
√
…
4
Изучение модификаций
√
…
5
Изучение сферы и
особенностей применения
√
…
6
Сравнительный анализ
√
…
7
Программная реализация
√
…
√
√
Pump up U

12.

Algorithms and Data Structures
Слайд 12
Все это изучается в рамках дисциплины с типовым названием
Algorithms and Data Structures (от 1 до 4 семестров) на всех
«компьютерных» специальностях по направлениям подготовки
компьютерные науки, компьютерная инженерия, программная
инженерия, информатика и др.
Для
названных
специальностей
Algorithms and Data Structures является
фундаментальной дисциплиной. Так
как прежде всего учит думать:
разрабатывать,
анализировать,
сравнивать, выбирать, отрабатывать
логику решения задачи!
Pump up U

13.

Foundational
Архитектура и структурная организация ЭВМ
Представление информации (системы счисления, правила перевода чисел,
кодирование информации, таблицы кодировки, прямой и дополнительный
код, форматы с фиксированной и с плавающей точкой (стандарт IEEE 754))
Двоичная логика, арифметика и операции сдвига
Основы дискретной математики
Общий принцип организации вычислений на компьютере
Принципы работы ЦП и его компонент (прежде всего – АЛУ)
Схемы из функциональных элементов (сумматор, …)
Основы компьютерных вычислений
Слайд 13
Теория чисел (теоретико-числовые алгоритмы)
Булева алгебра
Комбинаторика
Алгоритмы на графах (важно понимать как описывать структуры данных в
матричном виде)
Основы программирования
Типы данных, основы алгоритмизации и программирования
Pump up U

14.

Тема 1 Введение
в дисциплину
2 Цели и задачи
дисциплины
Pump up U

15.

Наши ожидания и намерения
Слайд 15
Задачи (то, что мы будем прорабатывать по ходу изучения)
разобрать практически значимые алгоритмы
научиться анализировать, объективно выбирать и адекватно
применять алгоритмы для решения актуальных задач
овладеть методологий алгоритмизации
Цели (то, чего мы хотим добиться в результате)
приобрести знания и навыки для разработки эффективного
кода и, следовательно
успешной работы в сфере IT
Pump up U

16.

Тема 1 Введение
в дисциплину
3 Структура
дисциплины
Pump up U

17.

Программа дисциплины
Слайд 17
Раздел 1. Введение в дисциплину (6 лекций)
Тема 1. Введение в дисциплину
Тема 2. Типы и структуры данных
Тема 3. Построение и анализ алгоритмов (Большая лекция)
Тема 4. Теоретико-числовые алгоритмы (Большая лекция)
Раздел 2. Сортировка и поиск (4 лекции)
Тема 5. Сортировка обменом
Тема 6. Сортировка слиянием
Тема 7. Сортировка распределением
Тема 8. Сортировка, поиск и вставка
Pump up U

18.

Программа дисциплины
Слайд 18
Раздел 3. Структуры данных (2 лекции)
Тема 9. Хеширование и хеш-таблицы
Тема 10. Деревья
Раздел 4. Специальные темы (6 лекций)
Тема 11. Полный перебор
Тема 12. Метод ветвей и границ
Тема 13. Разделяй и властвуй
Тема 14. Предварительная обработка
Тема 15. Жадные алгоритмы
Тема 16. Заключение
Pump up U

19.

Баланс времени
Слайд 19
По дисциплине предусмотрено 18 лекций (36 часов), которые
будут посвящены изучению теоретического материала на
примере решения прикладных задач.
По дисциплине предусмотрено 9 лабораторных и практических
занятий (36 часов), которые посвящены программированию
наиболее важных алгоритмов обработки данных.
Распределение нагрузки «Теория / Практика»
50% / 50%
Pump up U

20.

Оценивание
Слайд 20
На каждую лабораторную / практическую работу на лекции
выдается задание. Всего в течение семестра будет 10 заданий.
Суть каждого задания – разработать программную реализацию
заданного алгоритма.
Каждое задание оценивается в 5 бальной системе. Сумма
балов в конце семестра умноженная на 2 – это Ваш итог.
Максимальная сумма – 100 баллов.
На экзамене оценку можно улучшить.
Pump up U

21.

Тема 1 Введение
в дисциплину
4 FAQ
Pump up U

22.

Frequently Asked Questions
Слайд 22
Зачем нужна дисциплина?
учимся думать и писать эффективный код
Предназначение и содержание лекций?
теория + практика + ресурсы + задание
Предназначение практических видов занятий?
выполнение, консультация, сдача, оценивание
Самостоятельная работа?
внедрение европейской модели обучения; необходима для
успешной работы в сфере IT
Как сдать экзамен?
выставляется автоматически, оценку можно повысить
О роли английского языка?
это наше все: обучение + стажировки + работа в IT
Что мы забыли?
Pump up U

23.

Тема 1 Введение
в дисциплину
5 Литература и
ресурсы
Pump up U

24.

Рекомендуемая литература
Слайд 24
Pump up U

25.

Рекомендуемая литература
Слайд 25
Pump up U

26.

Рекомендуемая литература
Слайд 26
Pump up U

27.

Рекомендуемая литература
Слайд 27
…
Pump up U

28.

Основные ресурсы
Слайд 28
Электронные книги для скачивания: http://e-maxx.ru/bookz/
Важные алгоритмы: http://informatics.mccme.ru/
Важные алгоритмы: https://tproger.ru/tag/algorithms/
Соревнования, тренировки, задачи: http://codeforces.com/
Pump up U