Алгоритмы. Brainware - третий «кит» информатики

Алгоритмы нужны всем: военным, поварам, врачам, фармацевтам, математикам и, конечно, программистам. Мы живём в мире алгоритмов, современная цивилизация – это цивилизация алгоритмов.

Мясников Александр Леонидович

Мясников Александр Леонидович: Невозможно противопоставить свой скудный опыт индустрии доказательной медицины. В мире уже выработан алгоритм лечения больных, который выверен на миллионах пациентов. Нам нужно только согласиться с правильностью предложенных методов. Введение системы стандартов позволит нам сэкономить. Если бы мы приняли систему стандартов, все бы узнали, что лучшее лекарство от гипертонии - это копеечные мочегонные препараты, от инфарктов эффективнее всего защищает аспирин, оптимальный антибиотик при пневмонии - тетрациклин стоимостью 15 рублей, а не импортные препараты по 80 долларов за пузырёк. Система стандартов спасёт пациентов и от болезненных операций.

Мухаммад ибн Муса Хорезми ( ) таджикско- персидский математик, астроном и географ Аль-Хорезми

Алгоритм Евклида для отыскания наибольшего общего делителя двух целых положительных чисел a и b: Рассмотри данные числа a и b, переходим к следующему пункту; Сравни предложенные числа: a = b; a > b; a < b; переходим к следующему пункту; Если a = b, то прекратите вычисления, так как каждое из них даст искомый результат. Если нет, переходите к следующему пункту; Если первое число меньше второго, переставь их местами. Переходите к следующему указанию. Вычитай второе число из первого. Рассмотри два числа вычитаемое и остаток. Переходите к пункту второму.

Потребность в алгоритмизации научных вычислений: Системы мира по Птолемею ( 15 вычислений) и Копернику (7 вычислений)

Потребность в упрощении системы учета: Механические счетные машины («Паскалина», калькулятор Лейбница, арифмометр) – для их работы необходима инструкция!

Дональд Эрвин Кнут (родился в 1938) американский учёный. Алгоритм это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность.

Андрей Андреевич Марков ( ) советский математик Алгоритм это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

Андрей Николаевич Колмогоров ( ) советский математик Алгоритм это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

Алгоритмы. Определение Алгоритм – это строго определенная последовательность действий для некоторого исполнителя, приводящая к конкретному результату за конечное число шагов. Составление алгоритма - творческий процесс. Выполнения программы - это не творческий процесс. Ранее часто писали «алгорифм». Ранее вместо слова «порядок» использовали слово «последовательность».

Исполнители: неформальные и формальные

Дави́д Ги́альберт (нем. David Hilbert; 23 января февраля 1943) Проблема разрешимости алгоритма по Гилберту: Всегда можно составить алгоритм, который сможет дать однозначный ответ на любой заданный вопрос ( неразрешимых задач не существует). Алгоритмическая разрешимость свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае.формальной теории алгоритмом формуле аксиом В 1900 году на Втором Международном математическом конгрессе Гиальберт формулирует знаменитый список 23 нерешённых проблем математики 1900 году Международном математическом конгрессе нерешённых проблем математики

Процедурный текст …Отвори потихоньку калитку И войди в тихий садик как тень. Не забудь потемнее накидку, Кружева на головку надень…

Декларативный текст Фонтану Бахчисарайского дворца …Фонтан любви, фонтан живой! Принес я в дар тебе две розы. Люблю немолчный говор твой И поэтические слезы…

Тьюринг: нельзя определить алгоритмически, завершит ли данная машина Тьюринга свою работу или нет. А́лан Мэ́тисон Тью́ринг (англ. Alan Mathison Turing; 23 июня июня 1954) английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики (машина Тьюринга). Алонзо Чёрч (англ. Alonzo Church; 14 июня 1903, Вашингтон, США 11 августа 1995, Хадсон, Огайо, США) выдающийся американский математик и логик, внесший значительный вклад в основы информатики (лямбда –исчисление).

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

Машина Тьюринга

Требования к алгоритму Дискретность (прерывность, раздельность) – алгоритм состоит из отдельных простых "шагов". Каждый шаг исполняется только после того, как закончилось исполнение предыдущего. Детерминированность (определенность) – каждая команда алгоритма должна быть однозначной. Алгоритм должен быть независимым от того, кто и сколько раз будет его повторять. (Всё- таки, кулинарные рецепты плохо отвечают этому требованию) Результативность (конечность) – алгоритм должен приводить к результату за конечное число шагов. Массовость – алгоритм может использоваться многократно при разных исходных данных.

Форма представления алгоритмов Алгоритм может быть записан словами и/или формализован - изображён схематически. Обычно сначала алгоритм описывается словами, затем всё более формализуется (записывается на языке, понятном исполнителю). Если алгоритм выполняется компьютером, то для записи используется машинный код. В алгоритме присутствуют следующие структуры: линейная часть – команды, выполняемые последовательно друг за другом; ветвление – участок алгоритма, содержащий условие, в результате проверки которого происходит переход на одно или на другое продолжение алгоритма; цикл – участок алгоритма, предусматривающий повторение одних и тех же операций с новыми исходными данными.

Формы записи алгоритмов Словесная, на естественном языке; Графическая, например, в виде блок-схем; На алгоритмическом языке (псевдокоде); На языках программирования.

Запись алгоритма на естественном языке Пример: Автомат получает на вход два трехзначных восьмеричных числа. По этим числам строится новое восьмеричное число по следующим правилам: Вычисляются три восьмеричных числа – сумма старших разрядов, сумма средних разрядов, сумма младших разрядов заданных чисел. Полученные три восьмеричных числа записываются друг за другом в порядке убывания (без разделителей). Пример. Исходные числа: 271,626. Поразрядные суммы: 10,11,7. Результат: Определите, какое из предложенных чисел может быть результатом работы автомата: 18123; 16711; 13115?

Запись алгоритма в виде блок-схем Для графического представления алгоритмов в виде блок-схемы используются стандартные обозначения элементов (ГОСТ – 90).

Запись алгоритма на алгоритмическом языке (псевдокоде) Программа - это алгоритм, записанный на языке программирования. Оператор присвоения -(:=). Примеры: 1.Х:=2+5 2.Х:= Х*2 3.Х:=2>5 Задача: Установите такой порядок выполнения операций, чтобы при начальных значениях А=2, В=5, С=-5 результирующим стало значение С=5. 1)С=С/5; 2) В=А+В; 3) С=В+10; 4) А=А*В.

Оператор перехода Команды в программах выполняются последовательно. Имеется несколько операторов, которые изменяют последовательность выполнения команд программы. Формат записи оператора: GO TO.

Оператор ветвления Форматы записи оператора: IF(ЕСЛИ) THEN (ТО) ELSE (ИНАЧЕ) Если логическое условие истинно, то выполняется первый блок операторов, а если ложно, то второй. Пример: IF А>В THEN А=А*2 ELSE В=В*2

Заданы числа a и b. Определить, эти числа одного или разных знаков?

При начальных значениях А=-1, В=3. Чему будет равно С? IF А>=В THEN С:=(А – В)*В ELSE С:= (В-А)*А IF С

Операторы цикла. Операторы цикла организуют повторное выполнение одних и тех же команд несколько раз. Существуют две разновидности операторов цикла: оператор цикла с фиксированным числом повторений и операторы цикла с переменным числом повторений, зависящим от условий. Формат записи оператора цикла с фиксированным числом повторений: FOR i=N 1 TO N 2 STEP N 3 ; ; NEXT i

Цикл с переменным числом повторений: Блок-схема цикла ПОКА (цикл с предусловием)

Цикл с предусловием Даны положительные числа A и B (A > B). На отрезке длины A размещено максимально возможное количество отрезков длины B (без наложений). Не используя операции умножения и деления, найти длину незанятой части отрезка A

Цикл с переменным числом повторений: Формат записи цикла ПОКА НЕ

Задача, в которой требуется вводить с клавиатуры числа и подсчитывать их сумму, до первого введенного отрицательного числа.

Как вы думаете, к какому виду алгоритмов относится следующий пример? Что он позволит вычислить?

Запись алгоритма на языке программирования #!/usr/bin/python3 # -*-coding: utf-8 -*- import math A = float(input( 'a: ')) B = float(input( 'b: ')) C = float(input( 'c: ')) D = B*B - 4.0*A*C X1 = (-B + math.sqrt(D))/(2.0*A) X2 = (-B - math.sqrt(D))/(2.0*A) print (X1,X2) print ('END')

Классификация алгоритмов детерминированные (жесткие): задаются действия, обеспечивающие однозначный результат (например, работа двигателя); гибкие: вероятностные (стохастические): используют способы, приводящие к вероятному достижению результата (например, метод Монте-Карло) эвристические: достижение результата однозначно не предопределено

Эвристический алгоритм (эвристика) Эвристика (от греч. ερηκα «нашёл!») - алгоритм решения задачи, не имеющий строгого обоснования, но, тем не менее, дающий приемлемое решение задачи в большинстве случаев. Эвристика это математически «не совсем корректный», но практически полезный алгоритм.

Эвристика. Особенности: она не гарантирует нахождение лучшего решения; она не гарантирует нахождение решения, даже если оно заведомо существует; она может дать неверное решение. Эвристики применяются для решения задач, когда полный перебор вариантов занимает существенное время. Например, при распознавании образов, в антивирусных программах, компьютерных играх и т. д.

Пример эвристического алгоритма. Задача коммивояжера. Коммивояжёр должен посетить один раз все указанные города и вернуться обратно, в начальную точку маршрута. Необходимо выбрать минимальный по затратам маршрут. Коммивояжёр разъездной торговый агент.

Детерминированный алгоритм В общем случае, если есть n городов, то существует (n-1)! вариантов маршрута.

Время, требуемое для детерминированного алгоритма Посчитать длину маршрута можно за 1 нс = с. Число городов Время расчета 10 меньше секунды 1587 секунд 1899 часов 1974 дня 203 с половиной года 22 полторы тысячи лет

Оптимальный маршрут:

«Посмотрел – и сразу понял!» ДРАКОН (Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность).

Тест Тьюринга эмпирический тест, идея которого была предложена Аланом Тьюрингом в статье «Вычислительные машины и разум», опубликованной в 1950 году в философском журнале «Mind». Тьюринг задался целью определить, может ли машина мыслить. Аланом Тьюрингом«Вычислительные машины и разум»«Mind» мыслить

Тренируйте сами: Онлайн чат бот с открытым обучением. Вы можете исправлять ответы бота и добавлять новые варианты. Результаты обучения будут доступны другим пользователям сразу после сохранения базы знаний. Бота обучают люди!