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

Июль 26, 2022

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

Содержание

2. Смеляков Кирилл Сергеевич профессор кафедры ЭВМ, доктор технических наук, профессор R&D Interests* Data Science, Data Mining,
3. Pump up U NURE Data Science Слайд 3 https://www.facebook.com/NUREDataScience
4. Outline Слайд 4 Тема 1 Введение в дисциплину Pump up U Lecturer ScD, Professor Kirill Smelyakov
5. 1 Понятие алгоритма Тема 1 Введение в дисциплину Pump up U
6. Алгоритм – это формально описанный порядок действий (операций), которые необходимо выполнить для решения поставленной задачи за
7. Описанию алгоритма предшествует постановка задачи (для решения которой алгоритм и создается) обязательными элементами которой, помимо функции
8. Слайд 8 Algorithm and Software Алгоритм – это прототип программной реализации, при составлении которой, главным образом,
9. Наша система координат Слайд 9 Mathware Development (Data Science / Mining, etc.) лексическая / лексикографическая Prototyping
10. Слайд 10 Уровни познания алгоритма Разбор постановки задачи + Изучение принципа действия Решение типовой задачи: (1)
11. Слайд 11 Формализация познания алгоритма Pump up U
12. Слайд 12 Algorithms and Data Structures Все это изучается в рамках дисциплины с типовым названием Algorithms
13. Слайд 13 Foundational Архитектура и структурная организация ЭВМ Общий принцип организации вычислений на компьютере Принципы работы
14. 2 Цели и задачи дисциплины Тема 1 Введение в дисциплину Pump up U
15. Наши ожидания и намерения Слайд 15 Задачи (то, что мы будем прорабатывать по ходу изучения) разобрать
16. 3 Структура дисциплины Тема 1 Введение в дисциплину Pump up U
17. Программа дисциплины Слайд 17 Раздел 1. Введение в дисциплину (6 лекций) Тема 1. Введение в дисциплину
18. Программа дисциплины Слайд 18 Раздел 3. Структуры данных (2 лекции) Тема 9. Хеширование и хеш-таблицы Тема
19. Баланс времени Слайд 19 По дисциплине предусмотрено 18 лекций (36 часов), которые будут посвящены изучению теоретического
20. Оценивание Слайд 20 На каждую лабораторную / практическую работу на лекции выдается задание. Всего в течение
21. 4 FAQ Тема 1 Введение в дисциплину Pump up U
22. Frequently Asked Questions Слайд 22 Зачем нужна дисциплина? учимся думать и писать эффективный код Предназначение и
23. 5 Литература и ресурсы Тема 1 Введение в дисциплину Pump up U
24. Рекомендуемая литература Слайд 24 Pump up U
25. Рекомендуемая литература Слайд 25 Pump up U
26. Рекомендуемая литература Слайд 26 Pump up U
27. Рекомендуемая литература Слайд 27 … Pump up U
29. Скачать презентацию

Слайд 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

Слайд 2

Слайд 3

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

Слайд 4

Outline
Слайд 4
Тема 1 Введение в дисциплину
Pump up U
Lecturer ScD, Professor

Kirill Smelyakov

Слайд 5

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

Слайд 6

Алгоритм – это формально описанный порядок действий (операций), которые необходимо выполнить

для решения поставленной задачи за конечное число шагов.
Что значит формально? А это значит, что алгоритм составляется на основе некоторого стандарта, который регламентирует:
типы данных,
действия с данными,
формы записи алгоритма.
Алгоритм для нас – это новое понятие???

Определение алгоритма

Слайд 6

Pump up U

Слайд 7

Описанию алгоритма предшествует постановка задачи (для решения которой алгоритм и создается)

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

Определение алгоритма

Слайд 7

Pump up U

Слайд 8

Слайд 8
Algorithm and Software
Алгоритм – это прототип программной реализации, при

составлении которой, главным образом, отрабатывают логику решения поставленной задачи. Алгоритм составляется для того, чтобы понимать
как писать эффективный код
Описание алгоритма стараются минимально привязывать к особенностям его программной реализации для долгого времени жизни алгоритма и возможности выполнения на различных устройствах.

Pump up U

Слайд 9

Наша система координат
Слайд 9
Mathware Development
(Data Science / Mining, etc.)
лексическая

/ лексикографическая

Prototyping or Scientific Programming (Python, R, etc.)
текст программы

Algorithms and Data Structures
лексическая / лексикографическая /
блок-схема / псевдокод

Software Development (C++, etc.)
текст программы

Hardware Development

Выполняется в наукоемких проектах

Разработка
эффективного кода, развитие аналитических способностей и навыка алгоритмизации

Pump up U

Слайд 10

Слайд 10
Уровни познания алгоритма
Разбор постановки задачи + Изучение принципа действия
Решение

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

Pump up U

Слайд 11

Слайд 11
Формализация познания алгоритма
Pump up U

Слайд 12

Слайд 12
Algorithms and Data Structures
Все это изучается в рамках дисциплины

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

Pump up U

Слайд 13

Слайд 13
Foundational
Архитектура и структурная организация ЭВМ
Общий принцип организации вычислений на

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

Pump up U

Слайд 14

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

Слайд 15

Наши ожидания и намерения
Слайд 15
Задачи (то, что мы будем прорабатывать

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

Pump up U

Слайд 16

3 Структура дисциплины
Тема 1 Введение
в дисциплину
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

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

Слайд 22

Frequently Asked Questions
Слайд 22
Зачем нужна дисциплина?
учимся думать и писать эффективный

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

Pump up U

Слайд 23

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

Слайд 24

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

Слайд 25

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

Слайд 26

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

Слайд 27

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

Содержание

Смеляков Кирилл Сергеевич профессор кафедры ЭВМ,доктор технических наук, профессорR&D Interests*Data Science,

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

Outline Слайд 4Тема 1 Введение в дисциплинуPump up ULecturer ScD, Professor

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

Алгоритм – это формально описанный порядок действий (операций), которые необходимо выполнить

Описанию алгоритма предшествует постановка задачи (для решения которой алгоритм и создается)

Слайд 8Algorithm and SoftwareАлгоритм – это прототип программной реализации, при

Наша система координат Слайд 9Mathware Development (Data Science / Mining, etc.)лексическая

Слайд 10Уровни познания алгоритмаРазбор постановки задачи + Изучение принципа действияРешение

Слайд 11Формализация познания алгоритмаPump up U

Слайд 12Algorithms and Data StructuresВсе это изучается в рамках дисциплины

Слайд 13FoundationalАрхитектура и структурная организация ЭВМОбщий принцип организации вычислений на

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

Наши ожидания и намерения Слайд 15Задачи (то, что мы будем прорабатывать

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

Программа дисциплины Слайд 17Раздел 1. Введение в дисциплину (6 лекций)Тема 1.

Программа дисциплины Слайд 18Раздел 3. Структуры данных (2 лекции)Тема 9. Хеширование

Баланс времени Слайд 19По дисциплине предусмотрено 18 лекций (36 часов), которые

Оценивание Слайд 20На каждую лабораторную / практическую работу на лекции выдается

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

Frequently Asked Questions Слайд 22Зачем нужна дисциплина? учимся думать и писать эффективный

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

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

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

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

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

Похожие презентации

Смеляков Кирилл Сергеевич
профессор кафедры ЭВМ,
доктор технических наук, профессор
R&D Interests*
Data Science,

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

Outline
Слайд 4
Тема 1 Введение в дисциплину
Pump up U
Lecturer ScD, Professor

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

Слайд 8
Algorithm and Software
Алгоритм – это прототип программной реализации, при

Наша система координат
Слайд 9
Mathware Development
(Data Science / Mining, etc.)
лексическая

Слайд 10
Уровни познания алгоритма
Разбор постановки задачи + Изучение принципа действия
Решение

Слайд 11
Формализация познания алгоритма
Pump up U

Слайд 12
Algorithms and Data Structures
Все это изучается в рамках дисциплины

Слайд 13
Foundational
Архитектура и структурная организация ЭВМ
Общий принцип организации вычислений на

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

Наши ожидания и намерения
Слайд 15
Задачи (то, что мы будем прорабатывать

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

Программа дисциплины
Слайд 17
Раздел 1. Введение в дисциплину (6 лекций)
Тема 1.

Программа дисциплины
Слайд 18
Раздел 3. Структуры данных (2 лекции)
Тема 9. Хеширование

Баланс времени
Слайд 19
По дисциплине предусмотрено 18 лекций (36 часов), которые

Оценивание
Слайд 20
На каждую лабораторную / практическую работу на лекции выдается

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

Frequently Asked Questions
Слайд 22
Зачем нужна дисциплина?
учимся думать и писать эффективный

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

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

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

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

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