ݺߣ

ݺߣShare a Scribd company logo

01 Вступ

•
•
Oleksii Molchanovskyi
Oleksii Molchanovskyi

Слайди лекції з курсу "Розробка та аналіз алгоритмів. Частина 1". Тема лекції: "Вступ". http://edx.prometheus.org.ua/courses/KPI/Algorithms101/2015_Spring/about

1 of 21
Downloaded 12 times
Розробка та аналіз алгоритмів 1. Вступ • Що таке алгоритми? • Ефективність алгоритмів • Приклад: метод Карацуби • Структура курсу (с) Олексій Молчановський, Prometheus.org.ua 1
Що таке алгоритм? • Алгоритм –набір систематизованих правил виконання обчислювального процесу, що обов'язково приводить до розв'язання певного класу задач після скінченного числа операцій • Алгоритм – це довільна, коректна обчислювальна процедура, на вхід якої подається деяка величина або набір величин, а результатом виконання якої є вихідна величина або набір значень (с) Олексій Молчановський, Prometheus.org.ua 2
Приклад: задача сортування (с) Олексій Молчановський, Prometheus.org.ua 3
Властивості алгоритмів 1. Дискретність інформації • Кожний алгоритм має справу з дискретними даними: вхідними, проміжними, вихідними (с) Олексій Молчановський, Prometheus.org.ua 4
Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму • Алгоритм виконується по кроках та при цьому на кожному кроці виконується тільки одна операція (с) Олексій Молчановський, Prometheus.org.ua 5
Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму • Дані, які отримуються в кожний момент часу, однозначно визначаються даними, які були отримані в попередні моменти часу (с) Олексій Молчановський, Prometheus.org.ua 6
Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму 4. Елементарність кроків алгоритму • Правила, за якими отримуються наступні дані з попередніх, повинні бути простими та локальними (с) Олексій Молчановський, Prometheus.org.ua 7
Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму 4. Елементарність кроків алгоритму 5. Виконуваність операцій • В алгоритмі не повинно бути невиконуваних операцій (наприклад, «ділення на нуль») (с) Олексій Молчановський, Prometheus.org.ua 8
Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму 4. Елементарність кроків алгоритму 5. Виконуваність операцій 6. Скінченність алгоритму • Опис алгоритму повинен бути скінченним (с) Олексій Молчановський, Prometheus.org.ua 9
Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму 4. Елементарність кроків алгоритму 5. Виконуваність операцій 6. Скінченність алгоритму 7. Масовість алгоритму • Алгоритм повинен застосовуватись для якогось (потенційно нескінченного) набору вхідних даних (с) Олексій Молчановський, Prometheus.org.ua 10
Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму 4. Елементарність кроків алгоритму 5. Виконуваність операцій 6. Скінченність алгоритму 7. Масовість алгоритму (с) Олексій Молчановський, Prometheus.org.ua 11
Ефективність алгоритмів (с) Олексій Молчановський, Prometheus.org.ua 12 𝑛 𝑙𝑔(𝑛) 𝑛2T n
Приклад: ефективність алгоритмів (с) Олексій Молчановський, Prometheus.org.ua 13
Задача множення цілих чисел (с) Олексій Молчановський, Prometheus.org.ua 14
Золоте правило розробника алгоритмів «Можливо найбільш важливим принципом для гарного розробника алгоритмів є відмова від того, щоб бути задоволеним результатом» Аго, Гопкрофт, Ульман, «Розробка та аналіз комп’ютерних алгоритмів», 1974 (с) Олексій Молчановський, Prometheus.org.ua 15
Задача множення цілих чисел (с) Олексій Молчановський, Prometheus.org.ua 16
Метод Карацуби (с) Олексій Молчановський, Prometheus.org.ua 17
Навіщо вивчати алгоритми? • Щоб вміти більш ефективно розв’язувати складні задачі • Для розвинення власних якостей програміста • Щоб успішно проходити співбесіди в найкращі ІТ-компанії • Заради цікавості та інтелектуальної насолоди (с) Олексій Молчановський, Prometheus.org.ua 18
Структура курсу • Тривалість: 9 тижнів • Кожного тижня: • Відео-лекції – до 2 годин • Практичні завдання • Теоретичні тести • Наприкінці курсу – фінальний іспит (с) Олексій Молчановський, Prometheus.org.ua 19
Структура курсу • Алгоритми та обчислення • Аналіз алгоритмів • Метод декомпозиції. Рекурентні співвідношення • Швидке сортування. Порядкові статистики • Лінійне сортування • Структури даних • Елементарні структури даних • Піраміди • Хеш-таблиці • Бінарні дерева пошуку • Графи • Обхід графів • Пошук найкоротших шляхів в графах. (с) Олексій Молчановський, Prometheus.org.ua 20
Рекомендована література (с) Олексій Молчановський, Prometheus.org.ua 21 • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ • Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh (2006) Algorithms • Sedgewick, Robert; Wayne, Kevin (2011) Algorithms • J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005

More Related Content

01 Вступ

  • 1. Розробка та аналіз алгоритмів 1. Вступ • Що таке алгоритми? • Ефективність алгоритмів • Приклад: метод Карацуби • Структура курсу (с) Олексій Молчановський, Prometheus.org.ua 1
  • 2. Що таке алгоритм? • Алгоритм –набір систематизованих правил виконання обчислювального процесу, що обов'язково приводить до розв'язання певного класу задач після скінченного числа операцій • Алгоритм – це довільна, коректна обчислювальна процедура, на вхід якої подається деяка величина або набір величин, а результатом виконання якої є вихідна величина або набір значень (с) Олексій Молчановський, Prometheus.org.ua 2
  • 3. Приклад: задача сортування (с) Олексій Молчановський, Prometheus.org.ua 3
  • 4. Властивості алгоритмів 1. Дискретність інформації • Кожний алгоритм має справу з дискретними даними: вхідними, проміжними, вихідними (с) Олексій Молчановський, Prometheus.org.ua 4
  • 5. Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму • Алгоритм виконується по кроках та при цьому на кожному кроці виконується тільки одна операція (с) Олексій Молчановський, Prometheus.org.ua 5
  • 6. Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму • Дані, які отримуються в кожний момент часу, однозначно визначаються даними, які були отримані в попередні моменти часу (с) Олексій Молчановський, Prometheus.org.ua 6
  • 7. Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму 4. Елементарність кроків алгоритму • Правила, за якими отримуються наступні дані з попередніх, повинні бути простими та локальними (с) Олексій Молчановський, Prometheus.org.ua 7
  • 8. Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму 4. Елементарність кроків алгоритму 5. Виконуваність операцій • В алгоритмі не повинно бути невиконуваних операцій (наприклад, «ділення на нуль») (с) Олексій Молчановський, Prometheus.org.ua 8
  • 9. Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму 4. Елементарність кроків алгоритму 5. Виконуваність операцій 6. Скінченність алгоритму • Опис алгоритму повинен бути скінченним (с) Олексій Молчановський, Prometheus.org.ua 9
  • 10. Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму 4. Елементарність кроків алгоритму 5. Виконуваність операцій 6. Скінченність алгоритму 7. Масовість алгоритму • Алгоритм повинен застосовуватись для якогось (потенційно нескінченного) набору вхідних даних (с) Олексій Молчановський, Prometheus.org.ua 10
  • 11. Властивості алгоритмів 1. Дискретність інформації 2. Дискретність роботи алгоритму 3. Детермінованість алгоритму 4. Елементарність кроків алгоритму 5. Виконуваність операцій 6. Скінченність алгоритму 7. Масовість алгоритму (с) Олексій Молчановський, Prometheus.org.ua 11
  • 12. Ефективність алгоритмів (с) Олексій Молчановський, Prometheus.org.ua 12 𝑛 𝑙𝑔(𝑛) 𝑛2T n
  • 13. Приклад: ефективність алгоритмів (с) Олексій Молчановський, Prometheus.org.ua 13
  • 14. Задача множення цілих чисел (с) Олексій Молчановський, Prometheus.org.ua 14
  • 15. Золоте правило розробника алгоритмів «Можливо найбільш важливим принципом для гарного розробника алгоритмів є відмова від того, щоб бути задоволеним результатом» Аго, Гопкрофт, Ульман, «Розробка та аналіз комп’ютерних алгоритмів», 1974 (с) Олексій Молчановський, Prometheus.org.ua 15
  • 16. Задача множення цілих чисел (с) Олексій Молчановський, Prometheus.org.ua 16
  • 17. Метод Карацуби (с) Олексій Молчановський, Prometheus.org.ua 17
  • 18. Навіщо вивчати алгоритми? • Щоб вміти більш ефективно розв’язувати складні задачі • Для розвинення власних якостей програміста • Щоб успішно проходити співбесіди в найкращі ІТ-компанії • Заради цікавості та інтелектуальної насолоди (с) Олексій Молчановський, Prometheus.org.ua 18
  • 19. Структура курсу • Тривалість: 9 тижнів • Кожного тижня: • Відео-лекції – до 2 годин • Практичні завдання • Теоретичні тести • Наприкінці курсу – фінальний іспит (с) Олексій Молчановський, Prometheus.org.ua 19
  • 20. Структура курсу • Алгоритми та обчислення • Аналіз алгоритмів • Метод декомпозиції. Рекурентні співвідношення • Швидке сортування. Порядкові статистики • Лінійне сортування • Структури даних • Елементарні структури даних • Піраміди • Хеш-таблиці • Бінарні дерева пошуку • Графи • Обхід графів • Пошук найкоротших шляхів в графах. (с) Олексій Молчановський, Prometheus.org.ua 20
  • 21. Рекомендована література (с) Олексій Молчановський, Prometheus.org.ua 21 • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ • Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh (2006) Algorithms • Sedgewick, Robert; Wayne, Kevin (2011) Algorithms • J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005