1-maruza

Sana01.01.1970
Hajmi
#100908
Bog'liq
1-maruza


Тема 1. Понятие и свойства алгоритмов.
Лекция №1. Знакомство с видами контроля по учебной дисциплине. Введение в «Теорию алгоритмов».
Цель: рассказать о дисциплине «Теория алгоритмов», о поставленных задачах по дисциплине и
о видах контроля.
Дисциплина «Теория алгоритмов» изучается на втором курсе в первом семестре. Всего 76 часов.
Курс «Теория алгоритмов» предполагает значительный объём самостоятельной работы студентов, которая включает:

Для организации самоконтроля знаний предусмотрено компьютерное тестирование по следующим разделам учебного материала:

  1. Алгоритмы

  2. Интуитивное представление об алгоритмах 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