1. Понятие алгоритма
При работе с компьютером пользователи часто употребляют фразы «программное обеспечение», «программа». Мы уже знаем, что программное обеспечение представляет собой совокупность программ. Но что такое программа? Можно сказать, что это последовательность инструкций для решения некоторой задачи, записанная на каком-либо языке программирования. Тогда возникает вопрос: «Как создаются программы?». На деле это очень сложная интеллектуальная деятельность, конечным результатом которой является работающая программа. Но на пути к этому результату необходимо пройти несколько этапов, которые называют этапами решения задачи на ЭВМ:
Постановка задачи – выделение известных для решения задачи данных и выделение того, что будет результатом решения задачи. На первый взгляд это очень просто. Но повспоминайте свои проблемы в решении задач по математике в школе – наверняка бывали ситуации, кода вы задачу решили, но получили не тот ответ. Почему? Потому что неправильно поняли условие задачи! То есть неправильно выполнили постановку задачи. То есть, в конечном счете, была решена другая задача.
На этом же этапе все данные обозначаются (именуются), оговариваются их возможные значения, единицы измерения.
Этот этап является важнейшим для правильного решения задачи. Если на этом этапе допущены ошибки, то придется все решение начинать с самого начала.
Выбор метода решения – фактически на этом этапе подбираются формулы, посредством применения которых можно перейти от исходных данных к конечным результатам. По окончании этого этапа формируется математическая модель задачи.
Конструирование алгоритма – описание последовательности действий для решения задачи на естественном языке. Понятие алгоритма разберем чуть позднее.
Разработка программы – фактически это преобразование алгоритма в команды на языке программирования.
Отладка программы – выявление ошибок в программе посредством многократного запуска программы на исполнение с различными исходными данными. Это наиболее длительный этап (около 90% времени подготовки задачи для решения на ЭВМ) и очень влияющий на качество программы. Все «дыры» в программном обеспечении (о которых регулярно пишут в прессе и на которые ориентируются хакеры) образуются в результате некачественной отладки программ.
Тестирование программы – контрольное испытание программы в тех условиях и на том предприятии, где она должна работать. На этом этапе выявляются и устраняются неучтенные особенности задачи.
Решение задачи – эксплуатация программы заказчиком.
Теперь более подробно разберемся с понятием «алгоритм».
Человек регулярно в жизни сталкивается с алгоритмами – это разнообразные инструкции (например, правила пользования междугородним телефоном), рецепты, правила (например, порядок действий при пожаре) и др.
Термин «алгоритм» произошёл от имени среднеазиатского учёного IX века Мухаммеда ибн Муса ал-Хорезми (в переводе с арабского означает «Мухамед сын Мусы из Хорезма»), который описал десятичную систему счисления и впервые сформулировал правила выполнения арифметических действий над целыми числами и простыми дробями. Правила эти и сегодня служат простейшими примерами математических алгоритмов.В латинском переводе эти правила начинались словами «Алгоризми сказал». Постепенно люди забыли, что Алгоризми — это автор правил, и стали сами эти правила называть алгоритмами.
Большой вклад в теорию алгоритмизации внес английский ученый Алан Тьюринг (1912-1954) - разработал понятие абстрактной цифровой вычислительной машины (получившей впоследствии название машины Тьюринга), способной имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому. Неоценим вклад в развитие теории алгоритмизации советского ученого Андрея Маркова, предложившего нормальный алгоритм (названный нормальным алгоритмом Маркова), демонстрирующий работу идеальной машины, разработавшего теорию сложности алгоритмов Впоследствии теория алгоритмов была разработана американским ученым Дональдом Кнутом (род в 1938 г.), семитомный труд которого «Искусство программирования для ЭВМ» и в наше время многократно переиздается и изучается специалистами. В советской школе изучение информатики началось с 1985 года, благодаря деятельности А.П. Ершова.
Строгого математического определения алгоритма не существует. Используются понятия, которые в различной степени детализируют понятие алгоритма. Так, под алгоритмом понимается упорядоченная последовательность действий, приводящая к получению результата (точное предписание, определяющее вычислительный процесс, ведущее от начальных данных к искомому результату).
В энциклопедическом словаре по информатике приводится более точное понятие: Предписание, однозначно задающее процесс преобразования исходной информации в виде последовательности элементарных дискретных шагов, приводящих за конечное число их применений к результату.
Алгоритм должен обладать следующими свойствами:
- дискретность – алгоритм разбивается на отдельные шаги, реализация которых сводится к выполнению элементарной операции, то есть алгоритм исполняется по шагам – следующий шаг не начнет выполняться, пока не закончится предыдущий);
- конечность – число шагов для достижения результата обязательно должно быть конечным;
- результативность - после завершения алгоритма должен быть получен результат или сообщение о невозможности его получения;
определенность (однозначность) – команды алгоритма должны быть однозначно поняты исполнителем;
массовость - алгоритм должен быть применим для решения множества однотипных задач.
Надо отметить, что для решения одной задачи может быть составлено несколько алгоритмов (так как задачу можно решать несколькими способами). Но существуют задачи, для решения которых нет алгоритмов (их называют алгоритмически неразрешимыми). Например, не существует алгоритм распознавания кота.
Рассмотрим алгоритм открывания двери ключом:
Вставить ключ в замочную скважину.
Повернуть 2 раза против часовой стрелки.
Вынуть ключ.
Потянуть дверь на себя.
Обладает ли этот алгоритм свойством массовости?
Необходимо разобрать еще уже упоминавшиеся понятия:
исполнитель – это человек или техническое средство, предназначенное для исполнения алгоритмов;
Система команд исполнителя – совокупность команд, которые данный конкретный исполнитель умеет выполнять. Каждый исполнитель имеет ограниченную систему команд. Например, ученик первого класса не знает команду «интегрировать», экономист не знает команду «поставить диагноз больному» и т.д. Следовательно, свойство определенности алгоритма означает, что алгоритм может состоять только из команд, входящих в систему команд данного исполнителя.
- Содержание
- Введение
- Лекция 1. Введение в курс. Классификация компьютерных информационных технологий
- Предмет дисциплины. Понятие «компьютерные информационные технологии»
- Технологическая схема обработки информации
- Базовые и специальные информационные технологии
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 2. Информационные ресурсы автоматизированных систем обработки экономической информации
- Понятие «информационные ресурсы». Классификация
- Политика Республики Беларусь в области формирования информационных ресурсов
- Информационные услуги, режимы их предоставления
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 3. Техническое обеспечение компьютерных информационных технологий
- Классификация эвм
- Процессоры
- Устройства автоматизации ввода данных
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 4. Сетевые информационные технологии. Компьютерные сети: основные понятия и принципы построения
- Компьютерные сети: понятие, классификация
- Топология компьютерной сети
- Модель коммутационной сети
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 5. Локальные вычислительные сети
- 1. Оборудование лвс
- 2. Методы доступа к сети
- 3. Стандарты локальных сетей
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 6. Сетевые информационные технологии. Сетевые модели
- Эталонная модель osi
- Конвергенция компьютерных и телекоммуникационных сетей
- Корпоративные сети
- Преимущества, которые дает использование сетей
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 7. Глобальные компьютерные сети
- 1. Глобальная сеть Интернет, протоколы tcp/ip
- 2. Адресация компьютеров в сети
- 3. Услуги Интернет
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 8. Сетевые ит. Интернет и бизнес
- Задачи бизнеса в Интернете
- Классификация электронного бизнеса
- 3. Правовые аспекты электронного бизнеса
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 9. Сетевые информационные технологии. Электронные платежные системы
- Виды платежных систем
- Услуги платежных систем в Беларуси
- Формирование сетевой экономики
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 10. Технологии обеспечения безопасности информационных систем
- 1. Понятие безопасности информационных систем
- 2. Угрозы информационно безопасности
- 3. Методы и средства защиты информации
- Физические и юридические лица имеют право
- Особенности обеспечения безопасности в компьютерных сетях
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 11. Программное обеспечение компьютерных информационных технологий. Системное по
- Модели разработки и распространения по
- Виды лицензий на использование по
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 12. Программное обеспечение компьютерных информационных технологий. Прикладное по
- Технологии обработки информации. Офисные пакеты
- Технологии автоматизированного ввода документа (осr-системы)
- Технологии автоматизации перевода текстов
- Технологии организации рабочего места
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 13. Технологии искусственного интеллекта
- Понятие искусственного интеллекта
- 2. Области применения ии
- Понятие экспертной системы
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 14. Пакеты для математической обработки данных. Maple. Основы работы
- Компоненты экрана, справочная система Maple
- Вычисления в Maple
- Числа и константы
- Стандартные функции
- Преобразование математических выражений
- Решение уравнений
- Численное решение уравнений
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 15. Пакеты для математической обработки данных.Maple. Матрицы и графики
- Работа с массивами
- Графики и анимация
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция 16. Технологии и инструментальные средства программирования. Основы алгоритмизации
- 1. Понятие алгоритма
- 2. Типы алгоритмических процессов
- Повторять:
- 3. Способы записи алгоритмов
- Контрольные вопросы
- Литература
- Основные понятия
- Лекция №17. Технологии и инструментальные средства программирования. Языки программирования
- Технологии разработки программных комплексов
- Классификация языков программирования
- Инструментальные средства программирования
- Контрольные вопросы
- Литература
- Основные понятия