Презентация Алгоритмы. Задачи алгоритмизации онлайн

Содержание слайда: Алгоритмы

Содержание слайда: Литература Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО. — 960 с. Bирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 2003. Кнут Д. Э. - Искусство программирования. Том 1. Основные Алгоритмы. Скиена С. Алгоритмы. Руководство по разработке. – 2-е изд.:Пер. с англ. – СПб.: БХВ-Петербург, 2011. – 720 с.

Содержание слайда: Задачи алгоритмизации Построение нового или модификация некоторого ранее разработанного или определенного алгоритма. Доказательство правильности алгоритма (верификация, тестирование). Реализация применения разработанного или модифицированного алгоритма. Анализ, оценка алгоритма по некоторым критериям его эффективности.

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

Содержание слайда: Алгоритм Существует некоторое абстрактное устройство, способное распознать инструкции и выполнить предписываемые ими действия

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

Содержание слайда: Основные требования предъявляемые к алгоритмам Алгоритм должен иметь одну или несколько выходных величин. Конечность (или сходимость алгоритма) Результативность Последовательность шагов алгоритма детерминированна Алгоритм предполагает наличие механизма реализации Алгоритм должен обладать определенностью Массовость алгоритма

Содержание слайда: Алгоритм поиска НОД двух целых чисел Вычисление НОД чисел m и n при помощи алгоритма Евклида Шаг 1. Если n = 0, вернуть m в качестве ответа и закончить работу; иначе перейти к шагу 2. Шаг 2. Поделить нацело m на n и присвоить значение остатка переменной r. Шаг 3. Присвоить значение n переменной m, а значение r — переменной n. Перейти к шагу 1.

Содержание слайда: Алгоритм поиска НОД двух целых чисел Вычисление НОД чисел методом последовательного перебора Шаг 1. Присвоить значение функции min {m, n} переменной t. Шаг 2. Разделить m на t. Если остаток равен нулю, перейти к шагу 3; иначе перейти к шагу 4. Шаг 3. Разделить n на t. Если остаток равен нулю, вернуть t в качестве ответа и закончить работу; иначе перейти к шагу 4. Шаг 4. Вычесть 1 из t. Перейти к шагу 2.

Содержание слайда: Алгоритм поиска НОД двух целых чисел Вычисление НОД чисел m и п школьным методом Шаг 1. Разложить на простые множители число m. Шаг 2. Разложить на простые множители число n. Шаг 3. Для простых множителей чисел m и n, найденных на шаге 1 и 2, выделить их общие делители. Если р является общим делителем чисел тип и встречается в их разложении на простые множители, соответственно, рm и рn раз, то при выделении нужно повторить это min {pm,pn} раз. Шаг 4. Вычислить произведение всех выделенных общих делителей и вернуть его в качестве результата поиска НОД двух указанных чисел.

Содержание слайда: Основные способы описания алгоритмов словесно-формульный структурный или блок-схемный табличный с помощью граф-схем

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

Содержание слайда: Управляющие структуры

Содержание слайда: Управляющие структуры

Содержание слайда: Пример. Дана точка в декартовой системе координат P(x,y). Требуется составить условие определения в какой четверти находится данная точка.

Содержание слайда: Пример. Алгоритмическое решение. Вариант 1. Последовательный перебор. Последовательно составляются условия на принадлежность к каждой четверти. Вариант 2. Метод деления пополам. Сначала сравнивается первая координата на условие принадлежности точки к половине системы координат. Затем уточняется к какой из ее двух частей принадлежит точка Для решения задач выбора применяются: Операции сравнения, которые возвращают True (истина) или False (ложь): меньше, больше, равно, не равно, больше или равно, меньше или равно Логические операторы, применяемые для проверки одновременно несколько условий: X and Y (Истина, если оба значения X и Y истинны) X or Y (Истина, если хотя бы одно из значений X или Y истинно) not X (Истина, если X ложно)

Содержание слайда: Пример. Программное решение. Вариант 1. Последовательный перебор. Последовательно составляются условия на принадлежность к каждой четверти.

Содержание слайда: Пример. Программное решение. Вариант 2. Метод деления пополам. Сначала сравнивается первая координата на условие принадлежности точки к половине системы координат. Затем уточняется к какой из ее двух частей принадлежит точка

Содержание слайда: Управляющие структуры

Содержание слайда: Множественный выбор. Пример

Содержание слайда: Управляющие структуры

Содержание слайда: Повторяющиеся вычисления (управляющая структура «цикл для»). Пример.

Содержание слайда: Управляющие структуры

Содержание слайда: Управляющие структуры

Содержание слайда: Пример. Циклы с условием «до» и «после»

Содержание слайда: Управление процессом цикла

Содержание слайда: Автоматные графы

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

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

Содержание слайда: Итерация. Вычисление факториала Итерация — способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ.

Содержание слайда: