1-maruza
|
1-maruza
- Bu sahifa navigatsiya:
- Исторический обзор
Тема 1. Понятие и свойства алгоритмов. Лекция №1. Знакомство с видами контроля по учебной дисциплине. Введение в «Теорию алгоритмов». Цель: рассказать о дисциплине «Теория алгоритмов», о поставленных задачах по дисциплине и о видах контроля. Дисциплина «Теория алгоритмов» изучается на втором курсе в первом семестре. Всего 76 часов. Курс «Теория алгоритмов» предполагает значительный объём самостоятельной работы студентов, которая включает: изучение лекционного материала, учебной литературы, обучающих Интернет-ресурсов; подготовку к выполнению контрольных работ; - написание рефератов; - тестирование. Для организации самоконтроля знаний предусмотрено компьютерное тестирование по следующим разделам учебного материала: Алгоритмы Интуитивное представление об алгоритмах 3. Виды алгоритмов. 4. Проектирование алгоритмов. в ходе изучения предполагается выполнение контрольных работ, практических работ. На рубежном контроле тестирование, итоговый контроль – экзамен в тестовой оболочке СКСЭиП. Исторический обзор Первым дошедшим до нас алгоритмом в его интуитивном понимании – конечной последовательности элементарных действий, решающих поставленную задачу, считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел (алгоритм Евклида). Отметим, что в течение длительного времени, вплоть до начала XX века само слово «алгоритм» употреблялось в устойчивом сочетании «алгоритм Евклида». Для описания пошагового решения других математических задач использовалось слово «метод». Начальной точкой отсчета современной теории алгоритмов можно считать работу немецкого математика Курта Гёделя (1931 год - теорема о неполноте символических логик), в которой было показано, что некоторые математические проблемы не могут быть решены алгоритмами из некоторого класса. Общность результата Геделя связана с тем, совпадает ли использованный им класс алгоритмов с классом всех (в интуитивном смысле) алгоритмов. Эта работа дала толчок к поиску и анализу различных формализаций алгоритма. Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году годы Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Черча были эквивалентными формализмами алгоритма. Сформулированные ими тезисы (Поста и Черча-Тьюринга) постулировали эквивалентность предложенных ими формальных систем и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство алгоритмически неразрешимых проблем. В 1950-е годы существенный вклад в теорию алгоритмов внесли работы Колмогорова и Маркова. Download Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling