Слайд 2Первым дошедшим до нас алгоритмом считается предложенный Евклидом в III веке до
![Первым дошедшим до нас алгоритмом считается предложенный Евклидом в III веке до](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1123012/slide-1.jpg)
нашей эры алгоритм нахождения наибольшего общего делителя двух чисел - алгоритм Евклида
Начальной точкой отсчета современной теории алгоритмов можно считать работу немецкого математика Курта Гёделя 1931 год - теорема о неполноте символических логик
Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году годы Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом
В 1950-е годы существенный вклад в теорию алгоритмов внесли работы Колмогорова и Маркова.
Слайд 3К 1960-70-ым годам оформились следующие направления в теории алгоритмов:
Классическая теория алгоритмов
Теория асимптотического
![К 1960-70-ым годам оформились следующие направления в теории алгоритмов: Классическая теория алгоритмов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1123012/slide-2.jpg)
анализа алгоритмов
Теория практического анализа вычислительных алгоритмов
Слайд 4Цели и задачи теории алгоритмов
формализация понятия «алгоритм» и исследование формальных алгоритмических систем;
формальное
![Цели и задачи теории алгоритмов формализация понятия «алгоритм» и исследование формальных алгоритмических](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1123012/slide-3.jpg)
доказательство алгоритмической неразрешимости ряда задач;
классификация задач, определение и исследование сложностных классов;
асимптотический анализ сложности алгоритмов;
исследование и анализ рекурсивных алгоритмов;
получение явных функций трудоемкости в целях сравнительного анализа алгоритмов;
разработка критериев сравнительной оценки качества алгоритмов.
Слайд 5Практическое применение результатов теории алгоритмов
Теоретический аспект
- является ли задача в принципе
![Практическое применение результатов теории алгоритмов Теоретический аспект - является ли задача в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1123012/slide-4.jpg)
алгоритмически разрешимой
Практический аспект
- рациональный выбор из известного множества алгоритмов решения
данной задачи
- получение временных оценок решения сложных задач
- получение достоверных оценок невозможности решения некоторой
задачи за определенное время
- разработка и совершенствование эффективных алгоритмов решения
задач
Слайд 6Понятие алгоритма
Определение 1.1: Алгоритм - это заданное на некотором языке конечное предписание,
![Понятие алгоритма Определение 1.1: Алгоритм - это заданное на некотором языке конечное](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1123012/slide-5.jpg)
задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных.
Определение 1.2 (Колмогоров): Алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
Определение 1.3 (Марков): Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.