Формы записей алгоритмов. Общие принципы построения.

Свойства алгоритмов

Понятие алгоритма

Объектно-ориентированное программирование (ООП)

Чтобы написать еще более сложную программу, необходим новый подход к программированию - технология объектно-ориентированного программирования.

OOП включает лучшие идеи, воплощённые как в структурном программировании, так и в модульном. «Является еще более структурным программированием, еще более модульным» (Джеф Дантеманн?).

И, кроме того, ООП сочетает старые принципы с мощными новыми концепциями, которые позволяют оптимально организовывать программы.

Объектно-ориентированное программирование позволяет разложить проблему на составные части. Каждая составляющая становится самостоятельным объектом, содержащим свои собственные коды и данные, которые относятся к этому объекту. В этом случае программирование в целом упрощается, и программист получает возможность оперировать гораздо большими по объёму программами.

Таким образом, ООП - «это методология, основанная на представлении программы в виде совокупности объектов, каждый из которых является реализацией собственного класса» (А.Д. Александровский).

Основным понятием ООП является понятие класса.

Класс - множество объектов, связанных общностью структуры и поведения (класс содержит описание структуры и поведение всех объектов, связанных отношением общности). Любой объект является экземпляром класса.

Coordinates = class

x, y: byte;

procedure Init (Xinit, Yinit: byte);

function GetX: byte;

function GetY: byte;

Для разработки приложений в Delphi используются специальным образом оформленные классы - компоненты .

Компонент обладает набором свойств и методов . Свойства компонента изменяются либо на этапе сборки приложения (под воздействием системы), либо программно, в процессе работы приложения (под воздействием пользователя).

Особым видом свойства компонента является событие . Процедура обработки события - это реакция приложения на изменение свойства компонента под воздействием системы или пользователя (нажатие клавиши, перемещение курсора и т.п.)

Разветвляющимся алгоритмом называется алгоритм, в котором выполняется одна из ветвей действий при заданных значениях параметра.

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

Такие задачи можно описать с помощью алгоритмов разветвляющейся структуры. В таких алгоритмах выбор направления продолжения вычисления осуществляется по итогам проверки заданного условия. Ветвящиеся процессы описываются оператором IF (условие).

а) если - то

б) если - то иначе

условие 1: действие 1

условие N: действие N

Разветвляющийся алгоритм:

Циклический алгоритм - алгоритм, в котором какая-то совокупность действий повторяется несколько раз при изменяющихся значениях параметра.

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

а) Пока <условие> делай<тело цикла>

б) для i от i 1 до i 2 делай<тело цикла>.

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

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

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

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

Следование;

Ветвление (в полной и сокращенной форме);

Цикл (с предусловием или постусловием).

Характерной особенностью этих структур является наличие у них одного входа и одного выхода.

Циклический алгоритм:

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

Ну, а теперь главный вопрос: Что такое алгоритм?

Свойства алгоритмов

Я не буду изобретать велосипед, а просто перечислю свойства алгоритма, которые известны уже много лет.

1. Конечность(результативность) алгоритма означает, что за конечное число шагов должен быть получен результат;
2. Дискретность алгоритма означает, что алгоритм должен быть разбит на последовательность выполняемых шагов;
3. Понятность алгоритма означает, что алгоритм должен содержать только те команды, которые входят в набор команд, который может выполнить конкретный исполнитель;
4. Точность алгоритма означает, что каждая команда должна пониматься однозначно;
5. Массовость алгоритма означает, что однажды составленный алгоритм должен подходить для решения подобных задач с разными исходными данными.
6. Детерминированность (определенность) . Алгоритм обладает свойством детерминированности, если для одних и тех же наборов исходных данных он будет выдавать один и тот же результат, т.е. результат однозначно определяется исходными данными.

Таким образом, Алгоритм — это понятное и точное предписание исполнителю, выполнить конечную последовательность шагов, приводящей от исходных данных к искомому результату.

Представьте, что я должен с ножом порезать апельсин. Чтобы выполнить это действие мне потребуется алгоритм.

Я хочу порезать апельсин. Как это сделать?

Виды алгоритмов

• Линейный(Команды последовательны без повторов и переходов);

Пример алгоритма:

начало
достань нож
порежь апельсин(Именно апельсин, а не любой другой фрукт. За это отвечает ТОЧНОСТЬ)
съешь апельсин
конец

• Циклический(Есть группа действий, повторяющихся по некоторому условию);

Пример алгоритма:

начало
достань нож
ПОКА апельсины не закончились
порежь апельсин
съешь все апельсины
конец

• Разветвляющийся(Выполнение команды зависит от условия).

Пример алгоритма:

начало
достань нож
ЕСЛИ нож тупой поточи
порежь апельсин
съешь апельсин
конец

Вот и все. На следующем уроке мы с вами рассмотрим структуру программы в Паскаль.

Итоговое тестирование по информатике

1. Как называлось вычислительное устройство, которое использовалось в Древней Греции?

1. калькулятор
2. машина Паскаля
3. арифмометр
4. логарифмическая линейка

2. Проект первой программно-управляемой машины был разработан:

1. Чарльзом Бэббиджем
2. Блезом Паскалем
3. Джоном фон Нейманом
4. С.А. Лебедевым
5. Джоном Непером

3. Для ввода программ и данных в ЭВМ первого поколения использовались

1. магнитные барабаны
2. оптические диски
3. магнитные диски
4. перфокарты
5. магнитные ленты

4. Элементной базой первого поколения были

1. транзисторы
2. микропроцессоры
3. интегральные схемы
4. электронные лампы
5. электромеханическое реле

5. Первая ЭВМ называлась …

6. Кто был конструктором первых отечественных ЭВМ?

7. Как назывался первый серийный персональный компьютер?

8. Элементной базой ЭВМ третьего поколения были

1. микропроцессоры
2. транзисторы
3. интегральные схемы
4. электронные лампы
5. электромеханическое реле

9. Что такое информатизация?

1. программное обеспечение компьютера
2. технология подготовки документов
3. совокупность способов и приемов хранения, передачи и обработки информации
4. процесс создания, развития и массового применения информационных средств и технологий
5. система управления базами данных

10. Информационным обществом называют:

1. систему национальных, общественных учреждений
2. пользователей сети Интернет
3. сеть, связывающую между собой множество локальных сетей, а также отдельные компьютеры
4. стадию развития общества, на которой основным предметом трудовой деятельности людей становится информация
5. общество, характеризующееся высокой степенью открытости, доступности информации о деятельности учреждений, организаций, должностных лиц и т.п. для общественного ознакомления, обсуждения

11. Что из перечисленного НЕ относится к целям информатизации?

1. информационное обеспечение активного отдыха и досуга людей
2. формирование и развитие информационных потребностей людей
3. формирование условий, обеспечивающих осуществление информатизации
4. информационное обеспечение всех видов деятельности
5. перевод всех информационных ресурсов в цифровой формат

12. К национальным информационным ресурсам относятся

1. медицинские учреждения
2. фонды библиотек и архивов
3. университеты, институты, академии
4. газ, нефть
5. общественные организации

13. К мерам обеспечения информационной безопасности НЕ относится

1. технические меры по защите от компьютерных преступлений
2. юридические меры по защите от компьютерных преступлений
3. разработка технологий создания защищенных автоматизированных систем обработки информации
4. соблюдение правил техники безопасности при работе с компьютером
5. административные меры по защите от компьютерных преступлений

14. По линии прямой связи передаются

1. команды управления и информация об объекте управления
2. информация о состоянии объекта управления
3. информация о состоянии управляющей системы
4. команды управления
5. команды управления и информация об управляющей системе

15. Какой из объектов может являться исполнителем алгоритмов?

16. Алгоритмы, которые решают некоторую подзадачу главной задачи и, как правило, выполняются многократно, называются:

1. циклическими
2. вспомогательными
3. линейными
4. основными
5. ветвящимися

Читайте также: Какие документы должны выдать при увольнении

17. Алгоритм называется линейным:

1. если ход его выполнения зависит от истинности тех или иных условий
2. если его исполнение предполагает многократное повторение одних и тех же операций
3. если операции выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий
4. если он представим в табличной форме
5. если операции выполняются от нач до кон

18. Понятность алгоритма означает, что он должен быть записан с помощью:

1. команд, понятных создателю алгоритма
2. команд из системы команд исполнителя
3. команд, понятых пользователю алгоритма
4. команд, понятных для компьютера
5. операторов языка программирования

19. Конечность алгоритма означает, что:

1. в нем должен присутствовать оператор вывода результата
2. он должен решать задачу вычислительного характера
3. в нем должно присутствовать ключевое слово, означающее конец алгоритма
4. он должен быть применим для решения всех задач заданного типа
5. результат должен быть получен за конечное число шагов

20. Как называется свойство алгоритма, соответствующее определению: «Алгоритм должен быть записан из команд, понятных исполнителю, каждая команда должна определять однозначное действие исполнителя»?

1. массовость
2. точность
3. конечность
4. понятность
5. дискретность

21. Алгоритм — это

1. конечный набор предписаний, определяющий решение задачи посредством конечного количества операций
2. правила выполнения определенных действий
3. набор команд для компьютера
4. протокол вычислительной сети
5. предписание исполнителю совершить последовательность действий

22. В клетку электронной таблицы можно занести.

1. только формулу
2. только число или текст
3. только число
4. число, формулу или текст
5. диаграмму

23. Диапазон клеток электронной таблицы — это

1. множество клеток, образующих область произвольной формы
2. множество заполненных клеток ЭТ
3. множество пустых клеток ЭТ
4. множество клеток, образующих область прямоугольной формы
5. множество клеток, образующих область квадратной формы

24. Сколько клеток входит в диапазон клеток A5:D8?

25. Клетка ЭТ называется текущей, если

1. клетка видна на экране
2. в ней находится информация
3. клетка является пустой
4. клетка содержит формулу
5. в ней находится курсор

26. Адрес клетки электронной таблицы — это

1. имя, состоящее из последовательности символов
2. имя, состоящее из имени столбца и номера строки
3. адрес байта оперативной памяти, отведенного под клетку
4. адрес машинного слова оперативной памяти, отведенного под клетку
5. номер байта оперативной памяти, отведенной под клетку

27. Чему равна сумма двоичных чисел 110110 и 101?

28. Неверно утверждение:

1. запись включает в себя несколько полей
2. поле включает в себя несколько записей
3. каждое поле БД имеет свой размер
4. БД имеет жесткую структуру
5. каждое поле имеет имя

29. Структура БД изменится, если

1. добавить/удалить поле
2. отредактировать запись
3. поменять местами записи
4. добавить запись
5. удалить запись

30. В реляционной БД информация организована в виде

1. иерархической структуры
2. файла
3. дерева
4. прямоугольной таблицы

31. Что делает невозможным подключение компьютера к глобальной сети:

1. Тип компьютера
2. Состав периферийных устройств
3. Отсутствие дисковода
4. Отсутствие сетевой карты

32. В компьютерных сетях используются обычно каналы связи:

1. Провода
2. Кабели
3. Радио связь
4. Все вышеперечисленное

33. Эффективность компьютерной связи зависит обычно от:

1. Пропускной способности
2. Производительности процессора
3. Емкости памяти
4. Все вышеперечисленное

34. Устройство, производящее преобразование аналоговых сигналов в цифровые и обратно, называется:

35. Объединение компьютеров и локальных сетей, расположенных на удаленном расстоянии, для общего использования мировых информационных ресурсов, называется.

1. локальная сеть
2. глобальная сеть
3. корпоративная сеть
4. региональная сеть

36. В локальных сетях используются:

1. Провода и кабели
2. Линии телефонной связи
3. Электронные лампы
4. Кристалл

37. Всемирная паутина — это система в глобальной сети, которое носит название:

38. Протоколы — это …

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

39. Браузер — это …

1. информационная система, основными компонентами которой являются гипертекстовые документы
2. программа для просмотра Web-страниц
3. сервис Интернета, позволяющий обмениваться между компьютерами посредством сети электронными сообщениями

40. Адрес электронной почты записывается по определенным правилам. Уберите лишнее

1. petrov_yandex.ru
2. [email protected]
3. [email protected]

Итоговое тестирование по информатике на тему «Управление и алгоритмы» (9 класс)

Что такое КИБЕРНЕТИКА?

раздел информатики, целью которой является разработка интеллектуальных систем; наука, занимающаяся изучением способов передачи, хранения и обработки информации с помощью компьютера;

наука об управлении в живых и неживых системах;

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

наука о жизни, одна из естественных наук, предметом которой являются живые существа и их взаимодействие с окружающей средой.

Читайте также: Возврат госпошлины при отказе от иска в арбитражном суде

Кто основал КИБЕРНЕТИКУ?

венгро-немецкий математик Джон фон Нейман;

греческий философ Платон;

французский физик Андре Ампер;

русский учёный Владислав Закревский;

американский математик Норберт Винер.

Из каких элементов с точки зрения кибернетики состоит всякая система управления?

канал обратной связи;

16+ Свидетельство о регистрации СМИ:
Эл №ФС77-60625 от 20.01.2015.

Лицензия на осуществление образовательной деятельности: № 5201 от 20.05.2016.

Адрес редакции и издательства: 214011, РФ,
г. Смоленск, ул. Верхне-Сенная, 4.
Контакты: [email protected]

Правообладатель товарного знака ИНФОУРОК: ООО «Инфоурок» (Свидетельство № 581999)

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение редакции может не совпадать с точкой зрения авторов.

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

1. Как называется свойство алгоритма, 1. Как называется свойство алгоритма, означающее, что данный алгоритм применим к решению целого класса задач?
а) понятность
б) определённость
в) результативность
г) массовость
2. Как называется свойство алгоритма, означающее, что он всегда приводит к результату через конечное, возможно, очень большое число шагов?
а) дискретность
б) понятность
в) результативность
г) массовость
3. Как называется свойство алгоритма, означающее, что он задан с помощью таких предписаний, которые исполнитель может воспринимать и по которым может выполнять требуемые действия?
а) дискретность
б) понятность
в) определённость
г) массовость
4. Как называется свойство алгоритма, означающее, что пусть решения задачи разделён на отдельные шаги?
а) дискретность
б) определённость
в) результативность
г) массовость
5. Как называется свойство алгоритма, означающее, что путь решения задачи определён вполне однозначно, на любом шаге не допускаются никакие двусмысленные и недомолвки?
а) дискретность
б) понятность
в) определённость
г) результативность

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

Ответим на вопросы по теме «Свойства алгоритма»:

Прежде,чем ответить на вопросы теста, вспомним свойства алгоритма:

1. Понятность — содержание команд, понятных исполнителю;
2. Определённость — результат однозначно определяется исходными данными, каждый шаг алгоритма строго определен.
3. Результативность — получение результата через конечное число шагов.
4. Массовость — определенный алгоритм может применяться для решения подобных задач.
5. Дискретность — разделение алгоритма на последовательные действия (шаги).
6. Точность — все команды должны четко (однозначно) пониматься.

Вопрос №1
Как называется свойство алгоритма, означающее, что данный алгоритм применим к решению целого класса задач ?
а) понятность;
б) определённость;
в) результативность;
г) массовость — определенный алгоритм может применяться для решения целого класса подобных задач .
ОТВЕТ: Г) МАССОВОСТЬ

Вопрос № 2
Как называется свойство алгоритма, означающее, что он всегда приводит к результату через конечное . возможно, очень большое число шагов ?
а) дискретность;
б) понятность;
в) результативность — получение результата через конечное число шагов ;
г) массовость.
ОТВЕТ: В) РЕЗУЛЬТАТИВНОСТЬ .

Вопрос №3
Как называется свойство алгоритма, означающее, что он задан с помощью таких предписаний, которые исполнитель может воспринимать и по которым может выполнять требуемые действия ?
а) дискретность;
б) понятность — содержание команд, понятных исполнителю ;
в) определённость;
г) массовость.
ОТВЕТ: Б) ПОНЯТНОСТЬ.

Вопрос № 4
Как называется свойство алгоритма, означающее, что путь решения задачи разделён на отдельные шаги ?
а) дискретность — разделения алгоритма на последовательные действия (шаги);
б) определённость;
в) результативность
г) массовость
ОТВЕТ: А) ДИСКРЕТНОСТЬ

Вопрос № 5
Как называется свойство алгоритма, означающее, что путь решения задачи определён вполне однозначно . на любом шаге не допускаются никакие двусмысленные и недомолвки?
а) дискретность;
б) понятность;
в) определённость — результат однозначно определяется исходными данными, каждый шаг алгоритма строго определён;
г) результативность.
ОТВЕТ: В) ОПРЕДЕЛЁННОСТЬ.

Бесплатная помощь с домашними заданиями

Введение в понятие алгоритма

Понятие алгоритма

В сегодняшнем социуме слово «алгоритм» настолько широко распространено, что большинству интуитивно понятно. Под ним мы понимаем какую-либо последовательность шагов для достижения той или иной цели. Однако для теоретической науки понятие «алгоритма» достаточно сложное.

Для составления программы, предназначенной для решения на ЭВМ какой-либо задачи, требуется составление алгоритма ее решения.

Алгоритм - это точное предписание, которое определяет процесс, ведущий от исходных данных к требуемому конечному результату. Алгоритмами, например, являются правила сложения, умножения, решения алгебраических уравнений, умножения матриц и т.п. Слово алгоритм происходит отalgoritmi , являющегося латинской транслитерацией арабского имени хорезмийского математика IX века аль-Хорезми . Благодаря латинскому переводу трактатааль-Хорезми европейцы в XII веке познакомились с позиционной системой счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система счисления и правила счета в ней.

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

Если вычислительный процесс заканчивается получением результатов, то говорят, что соответствующий алгоритм применим к рассматриваемой совокупности исходных данных. В противном случае говорят, что алгоритм неприменим к совокупности исходных данных. Любой применимый алгоритм обладает следующими основными свойствами :

результативностью;

определенностью;

массовостью.

Результативность означает возможность получения результата после выполнения конечного количества операций.

Определенность состоит в совпадении получаемых результатов независимо от пользователя и применяемых технических средств.

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

Для задания алгоритма необходимо описать следующие его элементы:

набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;

правило начала;

правило непосредственной переработки информации (описание последовательности действий);

правило окончания;

правило извлечения результатов.

Алгоритм всегда рассчитан на конкретного исполнителя. В нашем случае таким исполнителем является ЭВМ. Для обеспечения возможности реализации на ЭВМ алгоритм должен быть описан на языке, понятном компьютеру, то есть на языке программирования.

Таким образом, можно дать следующее определение программы.

Программа для ЭВМ представляет собой описание алгоритма и данных на некотором языке программирования, предназначенное для последующего автоматического выполнения.

Способы описания алгоритмов

К основным способам описания алгоритмов можно отнести следующие:

словесно-формульный;

структурный или блок-схемный;

с помощью граф-схем;

с помощью сетей Петри.

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

При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий.

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

у = 2а – (х+6).

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

1. Ввести значения а их.

2. Сложить х и 6.

3. Умножить a на 2.

4. Вычесть из 2а сумму (х+6).

5. Вывести у как результат вычисления выражения.

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

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

Оформление программ должно соответствовать определенным требованиям. В настоящее время действует единая система программной документации (ЕСПД), которая устанавливает правила разработки, оформления программ и программной документации. В ЕСПД определены и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД).

Операции обработки данных и носители информации изображаются на схеме соответствующими блоками. Большая часть блоков по построению условно вписана в прямоугольник со сторонамиа и b. Минимальное значениеа = 10 мм , увеличениеа производится на число, кратное5 мм . Размерb=1,5a . Для от дельных блоков допускается соотношение междуа и b, равное 1:2. В пределах одной схемы рекомендуется изображать блоки одинаковых размеров. Все блоки нумеруются. Виды и назначение основных блоков приведены в табл. 1.

Таблица 1. Условные обозначения блоков схем алгоритмов

Наименование	Обозначение	Функции
		Выполнение операции или группы операций, в результате которых изменяется значение, форма представления или расположение данных.
Ввод-вывод		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод).

Понятность - алгоритм должен состоять из команд, "понятных" исполнителю (входящих в систему команд исполнителя).

Дискpетность (прерывность, раздельность) - алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов.

Опpеделенность - т.е. каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола. Благодаpя этому свойству выполнение алгоpитма носит формальный хаpактеp и не тpебует никаких дополнительных указаний или сведений о pешаемой задаче.

Pезультативность (или конечность)- алгоpитм должен пpиводить к pешению задачи (или к ответу, что решения нет) за конечное число шагов.

Массовость - алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма.

Главная особенность любого алгоритма - формальное исполнение, позволяющее выполнять заданные действия (команды) не только человеку, но и техническим устройствам (исполнителям). Таким образом, исполнителями алгоритмов могут быть, например, человек, компьютер, принтер, робот-манипулятор, станок с числовым программным управлением, живая клетка, дрессированное животное, компьютерная программа, компьютерный вирус, "черепашка" в Логорайтере или Логомирах (геометрический исполнитель) и т.д.

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

Эти действия называются допустимыми действиями исполнителя. Только их и можно использовать.

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

Сложность алгоритма

Сложность алгоритма позволяет оценить, насколько быстро растет трудоёмкость алгоритма с увеличением объема входных данных. Под трудоемкостью понимается количество элементарных операций, которые необходимо выполнить для решения задачи с помощью данного алгоритма. Обычно оценка сложности алгоритма представляется в виде O(f(N)), где O – функция сложности, а N – число обрабатываемых наблюдений или примеров. Наименее затратными являются алгоритмы, для которых функция сложности имеет вид f(N)=C и f(N)=C*N, где С – константа. В первом случае вычислительные затраты не зависят от количества обрабатываемых данных, а во втором случае – линейно возрастают. Самыми затратными являются алгоритмы, сложность которых имеет степенную и факториальную зависимости от числа обрабатываемых наблюдений.

СОРТИРОВКА

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если i <= i <= ... <= i.

Имеется два вида алгоритмов сортировки: сортировка массивов, которые могут находиться как в операционной памяти, так и на диске в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах.

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

В общем случае при сортировке данных только часть информации используется в качестве ключа сортировки, который используется в сравнениях. Когда выполняется обмен, передается вся структура данных.

МЕТОДЫ ПОИСКА

Поиск информации в неотсортированном массиве требует проведения последовательного просмотра массива. Просмотр начинается с первого элемента и завершается либо найденным элементом, либо достижением конца массива. Этот метод должен использоваться для неотсортированных данных, но он также может использоваться для отсортированных данных. Если данные отсортированы, то может использоваться двоичный поиск, который выполняется значительно быстрее.

Да, хорошая алгоритмическая подготовка важна для программиста. И нет, хорошая - это вовсе не заучивание алгоритмов из списка “Самых Важных Алгоритмов, Которые Должен Знать Каждый”. На мой взгляд хорошая алгоритмическая подготовка должна стремиться дать программисту следующие три умения.

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

Очевидно, для этого недостаточно просто знать алгоритмы. Нужно уметь “видеть их”, распознавать возможности их применения.

Во-вторых, алгоритмическая подготовка должна прививать привычку анализировать эффективность каждого вашего решения. Не пропускать в критических местах квадратичные или экспоненциальные алгоритмы, и не закладывать в архитектуру программы идеи, которые потом невозможно будет реализовать достаточно эффективно.

В-третьих, алгоритмическая подготовка должна помогать умело пользоваться готовыми инструментами. Базы данных - это сплошные структуры данных и алгоритмы. Причем на концептуальном уровне довольно простые и понятные - деревья поиска, хэштаблицы, SS-Table, …

Например, зная, что индекс в БД - это просто дерево поиска, несложно понять, какие запросы могут быть выполнены быстро, а какие обречены на full-scan.
Зная, как на каких алгоритмах работает полнотекстовый поиск в Lucene, можно предсказать, какие запросы к Elastic будут давать релевантные ответы, а какие - нет, и даже как это можно доработать.

Если подводить итог:

• Кроме самих алгоритмов - учитесь их распознавать в задачах реального мира.
• Прививайте себе привычку анализировать эффективность кода, который вы пишите.
• Изучайте алгоритмы под капотом у инструментов, которыми вы пользуетесь - это пригодится при их эксплуатации.