Курсовая работа «Алгоритмы» Подготовила Атлангириева Айна, группа 2

Задачи презентации Понятие алгоритма Исторический обзор Развитие теории алгоритмов в XX веке Алгоритмы и компьютеры Способы записи алгоритмов

Оглавление Задачи презентации Задачи презентации Этимология слова «алгоритм» Этимология слова «алгоритм» Кибернетика Основные алгоритмы, разработанные до XX века Основные алгоритмы, разработанные до XX века Современное понятие алгоритма Современное понятие алгоритма Алгоритм нахождения НОД Алгоритм нахождения НОД Языки программирования. Языки программирования.

Оглавление (продолжение) Блок-схемы Теория алгоритмов Основные требования к алгоритмам. Примеры алгоритмов. Жизнь Современное состояние теории алгоритмов Список источников информации,

Определения понятия «алгоритм» В математике АЛГОРИТМ - точное предписание исполнителю совершить определенную последовательность действий для достижения поставленной цели за конечное число шагов. АЛГОРИТМ система правил, сформулированная на понятном исполнителю языке, которая определяет процесс перехода от допустимых исходных данных к некоторому результату и обладает свойствами: массовости массовости конечности конечности определенности определенности детерминированности детерминированности

Этимология слова «алгоритм» Слово алгоритм содержит в своем составе преобразованное географическое название Хорезм. Термин алгоритм обязан своим происхождением великому ученому средневекового Востока - Муххамад ибн Муса ал-Хорезми ( Магомет, сын Моисея, из Хорезма ). Он жил приблизительно с 783 по 850 гг. В латинских переводах с арабского арифметического трактата ал-Хорезми его имя транскрибировалось как algorismi. Откуда и пошло слово алгоритм – сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определенным правилам и инструкциям.

Кибернетика Кибернетика (от греч. Κυβερνήτης - "кормчий") наука об общих закономерностях процессов управления и передачи информации в машинах, живых организмах и обществе. Кибернетика является междисциплинарной наукой, призванной объединить и систематизировать знания тех областей, которые до сих пор было принято считать различными и несовместимыми. Данная цель достигается в кибернетике за счёт анализа и выявления общих принципов и подходов в процессе научного познания. Наиболее весомыми теориями, объединяемыми кибернетикой, можно назвать следующие: Теория передачи сигналов Теория передачи сигналов Теория информации Теория информации Теория систем Теория систем Теория управления Теория управления Теория автоматов Теория автоматов Теория принятия решений Теория принятия решений Синергетика Синергетика

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

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

Алгоритм нахождения НОД (наибольшего общего делителя) Например, описание алгоритма Евклида нахождения НОД (наибольшего общего делителя) двух целых положительных чисел может быть представлено в виде трех шагов. Шаг 1: Разделить m на n. Пусть p остаток от деления. Шаг 2: Если p равно нулю, то n и есть исходный НОД. Шаг 3: Если p не равно нулю, то сделаем m равным n, а n равным p. Вернуться к шагу 1. Приведенная здесь запись алгоритма нахождения НОД очень упрощенная. Запись, данная Евклидом, представляет собой страницу текста, причем последовательность действий существенно сложней.

Блок-схема нахождения НОД X:=n Y:=m X =Y nod:= X X >Y X := X - Y Y := Y - X ДА НЕТ ДА НЕТ

Языки программирования Структурные языки программирования Basic Basic QBASIC QBASIC Фортран Фортран Фокал Фокал Процедурные языки программирования Алгоритмический язык Алгоритмический язык Си Си КОБОЛ КОБОЛ Паскаль Паскаль Глагол Глагол Логические языки программирования PrologProlog Объектно- ориентированные языки программирования Ada Java JavaScript C++ C# ColdFusion Object Pascal Visual Basic Smalltalk Оберон Python Perl PHP

Блок-схемы

Пример алгоритма в медицине МРТ, КТ, НСГ ВЕНТРИКУЛОСКОПИЯ Узкое отверстие Монро, 3-й желудочек НЕТДА Гибкая эндоскопия по принципу «мама- дочка» ВЦС - III Наружное дренирование Цитология ликвора, онкомаркеры ликвора, биопсия ДАНЕТ

Теория алгоритмов Раздел математики, изучающий общие свойства алгоритмов. Содержательные явления, приведшие к образованию понятия «алгоритм», прослеживаются в математике в течение всего времени её существования. Само это понятие сформировалось лишь в XX в. и стало предметом самостоятельного изучения (по-видимому, впервые, хотя ещё в расплывчатом виде) лишь в 20-х гг. XX в. в трудах представителей математического интуиционизма Л. Э. Я. Брауэра и Г. Вейля.

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

Примеры алгоритмов. Жизнь Шаг работы программы «Жизнь», разработанной Пенроузом

Современное состояние теории алгоритмов В настоящее время теория алгоритмов развивается, главным образом, по трем направлениям: Классическая теория алгоритмов изучает проблемы формулировки задач в терминах формальных языков, вводит понятие задачи разрешения, проводит классификацию задач по классам сложности P, NP и другим. Классическая теория алгоритмов изучает проблемы формулировки задач в терминах формальных языков, вводит понятие задачи разрешения, проводит классификацию задач по классам сложности P, NP и другим.формальных языковPNPформальных языковPNP Теория асимптотического анализа алгоритмов рассматривает методы получения асимптотических оценок ресурсоемкости или времени выполнения алгоритмов, в частности, для рекурсивных алгоритмов. Асимптотический анализ позволяет оценить рост потребности алгоритма в ресурсах (например, времени выполнения) с увеличением объема входных данных. Теория асимптотического анализа алгоритмов рассматривает методы получения асимптотических оценок ресурсоемкости или времени выполнения алгоритмов, в частности, для рекурсивных алгоритмов. Асимптотический анализ позволяет оценить рост потребности алгоритма в ресурсах (например, времени выполнения) с увеличением объема входных данных. Теория практического анализа вычислительных алгоритмов решает задачи получения явных функции трудоёмкости, интервального анализа функций, поиска практических критериев качества алгоритмов, разработки методики выбора рациональных алгоритмов. Теория практического анализа вычислительных алгоритмов решает задачи получения явных функции трудоёмкости, интервального анализа функций, поиска практических критериев качества алгоритмов, разработки методики выбора рациональных алгоритмов.

Список источников информации Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ, 2-е издание (Introduction to Algorithms, Second Edition) М: Вильямс. ISBN , ISBN ISBN ISBN ISBN ISBN Марков А. А., Нагорный Н. М. Теория алгоритмов, изд. 2. М.: ФАЗИС, Интернет-сайт: Wikipedia.org Интернет-сайт: slovari.yandex.ru Кушниренко А.Г. и др. Информатика. - М.: Дрофа, 1998 Лебедев Г.В., Кушниренко А.Г. 12 лекций по преподаванию курса информатики. - М.: Дрофа, 1998 Шауцукова Л.З. Информатика М.: Просвещение, 2000

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