Алгоритмы и программирование задач

Информатика – наука, систематизирующая приемы и методы создания, хранения, воспроизведения, обработки и передачи данных (информации) средствами вычислительной техники, а также принципы функционирования этих средств и методы управления ими.
Основная задача информатики – систематизация приемов и методов работы с аппаратными и программными средствами вычислительной техники.
Цель систематизации – выделение, внедрение, развитие передовых, наиболее эффективных технологий, в автоматизации этапов работы с данными, а также в методическом обеспечении новых технологических исследований.
Предметами информатики являются: аппаратное обеспечение средств ВТ; программное обеспечение средств ВТ; средства взаимодействия аппаратного и программного обеспечения; средства взаимодействия человека с аппаратными и программными средствами (пользовательский интерфейс).
1. Основные этапы автоматизации решения задач на ЭВМ

Основные направления практического применения информатики
Разработка приемов и методов построения вычислительных систем. Разработка приемов и методов управления аппаратным и программным обеспечением.
Разработка приемов, методов и средств разработки программ (программирование).
Защита информации в вычислительных системах.
Автоматизация функционирования программно-аппаратных средств.
Стандартизация аппаратных и программных средств, их интерфейсов, форматов представления данных.
Оценка эффективности функционирования вычислительных систем и программного обеспечения.

Характеристика процессов решения задач
Человек
ЭВМ
Решает осмысленно и при случае может прекратить вычисления, обратиться за консультацией, повторить часть вычислений и т. д.
ЭВМ будет выполнять лишь то, что предписано, разработанной программой.
Человек имеет возможность интуитивного решения задач с учетом накопленного опыта.
У ЭВМ полностью отсутствуют интуитивные возможности и поэтому весь процесс решения задач должен быть предварительно осознан человеком.
Этого можно добиться, если формализовать способ решения задачи с использованием аппарата математики при разработке и описании алгоритма задачи.
расчетные
математические модели
разработки текстово-графических документов
автоматического управления
управления базами данных
автоматизированного принятия решений
автоматизированного проектирования
Задачи можно разделить на следующие основные типы:
автоматизированного программирования
распознавания образов
математической лингвистики
информационно-поисковые
мультимедийные
автоматизированного обучения
информационно-справочные

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

Свойства алгоритма:
Повторяемость - получение результата при многократных расчетах с одними и теми же исходными данными.
Результативность - обязательным получением некоторого результата (числа, таблицы, текста, звука, изображения и т. д.) или сигнала о том, что данный алгоритм неприменим для решения поставленной задачи.
Массовость - возможностью получения результата при различных исходных данных для некоторого класса сходных задач.
Дискретность - возможностью разбиения алгоритма на отдельные элементарные действия.
2. Алгоритм, его свойства и способы представления
Алгоритм - точное описание способа решения задачи, устанавливающее состав операций и последовательность их выполнения (ГОСТ 19781-83).

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

Основные этапы разработки алгоритма задачи

Разработанный алгоритм решения задачи должен быть представлен в наглядной и компактной форме, удобной для практического использования и дальнейшего составления его программы.
Словесная форма применяется для представления достаточно сложных алгоритмов. Она используется лишь на начальных стадиях разработки алгоритма.
Графическая форма представления алгоритмов является более компактной и наглядной.
Блок-схема алгоритма - последовательность связанных между собой блоков, каждый из которых соответствует выполнению одного или нескольких операторов. Условные графические обозначения символов, используемых для со­ставления блок-схемы алгоритма, стандартизированы (ГОСТ 19.002-80 и ГОСТ19.003-80).
Операторная схема представления алгоритма была введена Ляпуновым. Она – цепочка символов операторов действий и условных переходов.
Ориентированный граф алгоритма - граф-схема, состоящая из конечного числа узлов (вершин) и соединяющих их ориентированных ребер. Всегда есть два узла: входной и выходной. Из каждого узла с арифметическим оператором выходит одна стрелка, а из узла с логическим оператором – две стрелки.
Алгоритм, представленный на языке программирования, есть программа. Алгоритм на этапе разработки может быть запрограммирован на любом удобном для его проверки языке программирования.

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

Рассмотрим блок-схему алгоритма решения
квадратного уравнения ax2 + bх + с = 0.

Uo- оператор начала алгоритма
А – арифметический оператор
Р – логический оператор
Е – конец алгоритма
Операторная схема представления произвольного алгоритма
без раскрытия содержания операторов
Uo A1 P2 A3 ; A4 P5 A6 E7
Вышеприведенный алгоритм можно представить
в виде ориентированного графа

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

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

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

В частном случае может оказаться, что для одного из выбранных путей действий предпринимать не нужно. Такая структура получила название обход или структура «если – то».
Если в алгоритме имеется три и более направления ветвления, то его можно представить в виде совокупности нескольких базовых структур разветвление «если - то – иначе».
Такую разновидность структуры разветвление часто называют множественный выбор.

Базовая структура цикл обеспечивает повторное выполнение или, другими словами, циклическую работу операторов.
Различают две разновидности этой структуры: «цикл – пока» и «цикл – до».
Вход
Алгоритмы, имеющие в своем составе базовую структуру цикл, называются циклическими.

3. Разработка программ
В соответствии с действующей для данной ЭВМ системой программного обеспечения алгоритм решения задачи записывается либо на языке вычислительной машины, либо на алгоритмическом языке.
Программирование алгоритмов осуществляется вручную и с помощью автоматизированных систем программирования.
ГОСТ 19.1001-77 устанавливает следующие виды программ:
компонент;
комплекс.
Компонент- программа, рассматриваемая как единое целое, выполняющая законченную функцию и применяемая самостоятельно или в составе комплекса.
Комплекс - программа, состоящая из двух или более компонент и (или) комплексов, выполняющих взаимосвязанные функции, и применяемые самостоятельно или в составе другого комплекса.
Программа - упорядоченная последовательность команд.
Приложение (операционной системы) - программа, функционирующая под управлением конкретной операционной системы.

Этапы разработки программ определяются ГОСТ 19.102-77.

Характерные ошибки при разработке программ

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

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

Инкапсуляция – объединение свойств и методов в одном объекте. Целью инкапсуляции является обеспечение автономности объектов и возможности изменения их структуры без внесения изменений в другие части программы.
При инкапсуляции объект заключается в непроницаемую оболочку, и только его внешний вид доступен для обозрения. Этим обеспечивается защита объекта от кодов других частей программы. Объект отвечает за корректность реализации своей функциональной способности, а вызывающая объект программа - за корректность использования объекта.
С помощью механизма наследования одни классы объектов могут происходить от других. Дочерний класс способен унаследовать от своего родительского класса все его методы и данные, причем потомок может унаследовать способности и от нескольких родителей.
То есть наследование позволяет использовать разработанные ранее классы, что обеспечивает сокращение разработки программ. При этом расширяются возможности класса за счет объединения свойств и методов исходных классов.
Полиморфизм – позволяет использовать одно имя для обозначения действий, общих для родственных классов. При этом конкретизация выполняемых действий осуществляется в зависимости от типа обрабатываемых данных. Полиморфизм исключает избыточность кодов в программе.
Объектно-ориентированное программирование характеризуется следующими тремя признаками: инкапсуляцией, наследованием и полиморфизмом.