Бураков П.В., Косовцева Т.Р. Информатика. Алгоритмы и программирование. Учебное пособие.-СПб НИУ ИТМО, 2013. – 83с.
Учебное пособие предназначено для студентов экономических специальностей специальности 080100 «Экономика» гуманитарного факультета, изучающих дисциплину «Информатика». Пособие представляет собой вводный курс по построению алгоритмов и по программированию на языке Турбо Паскаль. Пособие содержит много примеров. Подробно излагаются теоретические аспекты построения алгоритмов и основ программирования. Во второй части учебного пособия приводтся лабораторный практикум.
В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет». Министерством образования и науки Российской Федерации была утверждена Программа развития государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный университет информационных технологий, механики и оптики» на 2009– 2018 годы.
© Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, 2013 ©П.В. Бураков, Т.Р.Косовцева
Постановка задачи......................................................................................................................... |
|
Разработка математической модели............................................................................................ |
|
Выбор метода численного решения............................................................................................. |
|
Разработка алгоритма и структуры данных................................................................................ |
|
Реализация алгоритма в виде программы................................................................................... |
|
Отладка и тестирование программы............................................................................................ |
|
Решение задачи на компьютере................................................................................................... |
|
ПОСТРОЕНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ............................................................................. |
|
Описание алгоритма...................................................................................................................... |
|
Схема алгоритма.......................................................................................................................... |
|
Структурированные схемы алгоритмов.................................................................................... |
|
СРЕДСТВА РЕАЛИЗАЦИИ АЛГОРИТМА.......................................................................................... |
|
Критерии выбора языка программирования............................................................................. |
|
СТРУКТУРА ПРОГРАММЫ И ЕЕ ЭЛЕМЕНТЫ................................................................................. |
|
Основные элементы программирования................................................................................... |
|
Алфавит и словарь языка TurboPascal (TPascal)....................................................................... |
|
Структура программы................................................................................................................. |
|
ТИПЫ ДАННЫХ...................................................................................................................................... |
|
Скалярные типы данных............................................................................................................. |
|
Структурированные типы данных............................................................................................. |
|
ВВОД-ВЫВОД ДАННЫХ....................................................................................................................... |
|
Процедуры ввода-вывода........................................................................................................... |
|
ОПЕРАТОРЫ............................................................................................................................................ |
|
Общие сведения........................................................................................................................... |
|
Простые операторы..................................................................................................................... |
|
Структурные операторы............................................................................................................. |
|
Условные операторы................................................................................................................... |
|
Операторы цикла......................................................................................................................... |
|
МАССИВЫ................................................................................................................................................ |
|
Действия над массивами............................................................................................................. |
|
Действия над элементами массива............................................................................................ |
|
Операции с матрицами................................................................................................................ |
|
ПРОЦЕДУРЫ И ФУНКЦИИ................................................................................................................... |
|
Необходимость структуризации в программировании............................................................ |
|
Подпрограммы в языке ТPascal.................................................................................................. |
|
Процедуры.................................................................................................................................... |
|
Функции....................................................................................................................................... |
|
Механизм передачи параметров................................................................................................ |
|
ФАЙЛЫ..................................................................................................................................................... |
|
Общие сведения........................................................................................................................... |
|
Описания файлового типа.......................................................................................................... |
|
Средства обработки файлов....................................................................................................... |
|
Текстовые файлы......................................................................................................................... |
ЛАБОРАТОРНЫЙ ПРАКТИКУМ.......................................................................................................... |
|||
Лабораторная работа 1. |
Программирование линейных и |
разветвляющихся |
|
вычислительных процессов............................................................................................................. |
|||
Лабораторная работа № 2. |
Циклические вычислительные процессы................................... |
||
Лабораторная работа № 3. |
Операции с массивами................................................................. |
||
Лабораторная работа № 4. |
Операции с файлами..................................................................... |
||
Лабораторная работа 5. Процедуры и функции...................................................................... |
|||
БИБЛИОГРАФИЧЕСКИЙ СПИСОК..................................................................................................... |
|||
ЭЛЕМЕНТЫ ТЕХНОЛОГИИ РЕШЕНИЯ ПРАКТИЧЕСКИХ ЗАДАЧ НА КОМПЬЮТЕРЕ
Решение задач с применением персонального компьютера включает следующие основные этапы.
1. Постановка задачи.
2. Разработка математической модели.
3. Выбор метода численного решения для расчетных задач.
4. Разработка алгоритма решения и структуры данных.
5. Реализация алгоритма в виде программы.
6. Отладка и тестирование программы.
7. Решение задачи на компьютере, численные эксперименты и анализ результатов.
Постановка задачи
В работе специалиста, проектирующего новое изделие, технологический процесс или решающего определенную практическую задачу для нужд пользователя, сочетаются наука и искусство.
Конечным итогом является нахождение подходящего решения и представление его в виде удобном для практического применения. Эффективность решения во многом определяется четким осознанием потребности и точной словесной формулировкой этой потребности в виде цели (или нескольких целей). После этого в исследуемой предметной области собирается информация о тех факторах, которые влияют на достижение конечной цели, о взаимосвязи этих факторов, об ограничениях, связанных с различными сторонами рассматриваемой задачи. Таким образом, создается возможно более полное словесное описание задачи и условий ее решения.
Требуется определить длину пути, который проходит тело, движущееся с переменной скоростью. Начальная скорость тела равна 0. С определенной степенью степенью достоверности движение можно считать равноускоренным. Использование пакетов стандартных программ не предполагается.
В настоящее время эффективное решение сложных задач базируется на использовании математических моделей. Кроме возможности получения решения целого класса задач применение математических моделей обеспечивает проведение многовариантных расчетов, быструю адаптацию к изменению условий и поиск наилучших решений.
Разработка математической модели
На основе словесной формулировки задачи выбираются переменные, участвующие в процессе решения, определяется их область изменения, математически описываются связи между этими переменными и ограничения. Выделяются и формально описываются те факторы, которые входят в эти взаимосвязи как параметры. В результате инженерная задача приобретает вид формализованной математической модели.
Математической моделью задачи, сформулированной в примере 1 является формула: S = 0,5 a t 2 , где в качестве основной переменной выступает время t , параметром движения является ускорение а . Формула показывает зависимость между длиной пути и временем в соответствии с законом механики.
Следует отметить, что для математического описания зависимостей можно использовать различную степень детализации и различные формы математического описания. Так, в общем случае при движении с переменной скоростью длина пути определяется интегралом
S = ∫ V (t) dt ,
при этом закон изменения скорости V(t) в зависимости от времени может быть достаточно сложным и определить значение интеграла аналитически не удается. Поэтому в большинстве случаев практически целесообразно использовать приближенные методы решения.
Особое внимание следует уделять адекватности математической модели по отношению к исходному описанию задачи и условиям ее решения с одной стороны. Неоправданная сложность приводит к ненужным затратам сил, средств и времени. С другой стороны, недостаточная точность математического описания (грубость модели) приводит к большим погрешностям в решении, а иногда и к ошибочным выводам.
Выбор метода численного решения
Для расчетной задачи необходимо выбрать метод ее численного решения, сводящий решение задачи к последовательности арифметических и логических операций. Разработкой и изучением таких методов занимается раздел математики, называемый численным анализом. В качестве примера численного метода для вычисления определенных интегралов можно привести метод прямоугольников. В этом методе интеграл заменяется конечной суммой
∫ f (x ) dx ≈ ∆ x ∑ f (x i ) , где ∆х - шаг интегрирования (const), ∆х=(b-a)/n,
x i+1 =xi +∆ х, x1 =a , xn+1 =b
Вычисление приближенного значения определенного интеграла по этому методу сводится к последовательному расчету значений подынтегральной функции, их суммированию и умножению на величину шага интегрирования.
При выборе метода надо учитывать требования, предъявляемые постановкой задачи, и возможности его реализации на компьютере: точность решения, быстроту получения результата, требуемые затраты оперативной памяти для хранения исходных и промежуточных данных и результатов (для задач большого объема), сложность программной реализации, трудоемкость подготовки программы и решения задачи.
Разработка алгоритма и структуры данных
Если выбранный для решения задачи численный метод реализован в виде стандартной библиотечной подпрограммы, то алгоритм обычно сводится к описанию и вводу исходных данных, вызову стандартной подпрограммы и выводу результатов на экран или на печать. Более характерен случай, когда стандартные подпрограммы решают лишь какую-то часть задачи.
Четкая структуризация задачи, разбиение ее на последовательность подзадач, реализация подзадач отдельными модулями, постепенная детализация логики алгоритма, использование типовых логических конструкций являются хорошими средствами, позволяющими в разумные сроки создавать работоспособные программы для решения сложных задач.
Важной составной частью разработки алгоритма является выбор состава и способов организации (структур) данных: исходных, промежуточных и конечных результатов. Языки программирования, позволяют работать с числовыми и символьными константами, переменными, массивами данных (векторами и матрицами). Так в языке Turbo Pascal допускаются и более сложные структуры данных, удобные для задач обработки нечисловых данных, например текстов, для решения комбинаторных задач и имитационного моделирования. Поэтому выбор состава, типов и структур данных обычно производится с учетом особенностей реализации алгоритма на том или ином входном языке. Если разработчик программы владеет программированием на разных алгоритмических языках, то у него появляется возможность выбрать язык, наиболее соответствующий структуре данных задачи.
Разработка алгоритма завершается либо его представлением в виде графической схемы, либо записью с помощью символов специального языка проектирования программ, называемого псевдокодом. Используются также другие средства представления логики алгоритма: диаграммы, таблицы решений, схемы.
Реализация алгоритма в виде программы
При составлении программы на выбранном языке следует познакомиться с описанием особенностей реализации этого языка. Сначала рекомендуется использовать основные конструкции и типы данных языка, расширяя диапазон применяемых средств по мере приобретения опыта программирования и практического решения задач на компьютере.
При разработке и реализации алгоритмов не следует стремиться к получению программ, наилучших по быстродействию, объему требуемой памяти, удобству работы с данными. Дополнительное время, затраченное на разработку, программирование и отладку слишком сложного алгоритма, может обесценить результаты от его применения, так как они будут получены слишком поздно.
Важно получить работоспособную программу как можно раньше, жертвуя при этом на первых порах изяществом, компактностью, а порой и вычислительной эффективностью алгоритма. Совершенствование программы можно отложить до более позднего времени, когда проведенные эксперименты позволят уточнить постановку задачи, выяснить сферу применимости
программы, требования удобства ввода исходных данных и обработки результатов. С этой точки зрения также полезно использовать принцип модульности при разработке алгоритма, так как программу, составленную из модулей, легче модернизировать. Выделение в программе модулей ввода данных, расчета характеристик, вывода результатов позволит локализовать будущие изменения в программе в пределах каждого модуля, а также использовать некоторые из них в качестве готовых «строительных» блоков для новых задач.
Отладка и тестирование программы
При программировании и вводе данных с клавиатуры могут быть допущены ошибки. Их обнаружение, локализацию и устранение выполняют на этапе отладки и испытания (тестирования) программы.
Одним из критериев профессионального мастерства программистов является их способность обнаруживать и исправлять собственные ошибки: начинающие программисты не умеют этого делать, у опытных программистов особых затруднений это не вызывает. Тем не менее ошибки в программах делают все.
По данным разных авторов, этап отладки и тестирования программы занимает от 50 до 70 % времени, затрачиваемого на все этапы создания программы и получения решения. В связи с важностью и трудоемкостью этапа отладки все современные системы программирования имеют специальные средства, помогающие в обнаружении и устранении ошибок. Уже на этапе разработки алгоритма полезно предусмотреть простейшие средства контроля, встраиваемые в разрабатываемую программу: печать введенных данных непосредственно после их считывания в память машины (эхо-печать), печать промежуточных результатов в узловых точках. Но главное - надо максимально упрощать структуру программы за счет расчленения ее на модули, реализуемые в виде подпрограмм или процедур, и использования конструкций языка, наиболее простых и освоенных программистом.
Решение задачи на компьютере
На этом этапе компьютер выполняет все предусмотренные программой вычисления и выдает результаты на экран или на печать. Чтобы облегчить последующую обработку результатов счета, надо при проектировании программы предусмотреть вывод результатов с пояснениями. Выводимым числам и таблицам результатов должны предшествовать заголовки, одни группы данных следует отделять от других пропусками строк. При табулировании функции полезно указывать и значения аргументов, а если функции зависят от параметров, то перед выдачей значений функции следует указать и значения параметров.
При недостаточном опыте программирования не следует увлекаться формой представления результатов, однако какое-то время все же следует уделять этим вопросам, так как в конечном итоге это сокращает трудоемкость последующей обработки данных. Целесообразно отрабатывать форму представления выводимых данных на пробных прогонах программы, анализируя результаты на экране.
Контрольные вопросы
1. Какие факторы влияют на эффективность решения задач на компьютере?
2. Перечислите этапы решения задач на компьютере.
3. Каковы основные требования к математической модели задачи?
4. Назовите главные характеристики алгоритмов.
5. Какие особенности следует учитывать при разработке программ на компьютере?
6. Чем завершается разработка алгоритма?
ПОСТРОЕНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ
Описание алгоритма
Под алгоритмом понимается конечная последовательность точно сформулированных правил решения некоторого касса задач. Алгоритм обладает следующими свойствами:
Определенность. Все действия, которые необходимо произвести должны быть строго определены.
Понятность. Все действия, которые необходимо произвести, должны быть однозначно поняты и выполнены каждым исполнителем алгоритма. Это свойство может быть интерпретировано как однозначность алгоритма, под которой понимается единственность толкования исполнителем правил выполнения действий и порядка их выполнения.
Конечность . Обязательность завершения каждого из действий, составляющих алгоритм и завершимость выполнения алгоритма в целом.
Результативность . Если алгоритм применим к данной задаче, то после конечного числа шагов должен быть получен результат.
Массовость. Возможность применения данного алгоритма для решения класса задач, отвечающих общей постановке задачи.
Правильность . Способность алгоритма давать правильные результаты решения поставленных задач.
Каждое правило алгоритма записывается в виде повелительного предложения, понимаемого исполнителем алгоритма как команда на выполнение.
Рассмотрим алгоритмы решения нескольких задач. Задача 1 . Составить алгоритм вычисления x по формуле
x = a (r − q ) 2 , где p ≠ -12.
p + 12
1. Начало;
2. Вычислить b:= p + 12;
3. Вычислить c:= r – q;
4. Вычислить d:= c c;
5. Вычислить e:= a d;
6. Вычислить x:= e / b;
7. Записать результат: x;
В записи алгоритма решения задачи 1 введены буквенные обозначения
– переменные. Так, через b обозначено p + 12 , через c – разность r – q. Запись
b:= p+12 означает, что вначале должна быть найдена сумма p + 12 при определенных значениях p, а затем это значение присваивается переменной b.
Придавая a, p, q, r разные значения, будем получать различные задания на вычисление x . Поэтому алгоритм обычно позволяет решать не одну, а целый класс задач. Такую особенность алгоритма называют массовостью алгоритма. Возможны алгоритмы, решающие только единственную задачу.
Величины a, p, q, r, 12 составляют исходные данные для алгоритма, 12
– постоянную составляющую, a, p, q, r – переменную составляющую информации. Величины b, c, d, e являются вспомогательными переменными, x – результат исполнения алгоритма.
Алгоритм называется линейным , если при его исполнении все команды выполняются строго последовательно, без нарушения порядка их следования. Предложенный алгоритм решения задачи 1 является линейным.
Следует отметить, что сама формула не является алгоритмом, так как не указан однозначный порядок исполнения операций.
Задача 2 . По формуле
x = − b ± b 2 − 4 ac составить алгоритм решения квадратного уравнения
ax2 + bx + c = 0 (a ≠ 0).
1. Начало;
2. p:= 2a;
3. D:= b 2 – 4ac;
4. Если D ≥ 0, то перейти к п. 5, иначе к п. 10;
5. d:= D ;
6. x 1 : = − b − d ; p
7. x 2 : = − b + d ; p
8. Записать результат: x 1 , x2 ;
9. Перейти к п. 11;
10. Записать результат: уравнение действительных корней не имеет;
11. Конец.
При исполнении алгоритма выполняются не все его команды, следовательно, алгоритм решения задачи 2 не является линейным. Кроме арифметических действий и операций извлечения квадратного корня, вычислительный процесс содержит в правиле 4 операцию проверки условия: в зависимости от выполнения условия (да) или невыполнения условия (нет) выбирается одно из двух возможных продолжений. Такой алгоритм называют разветвляющимся. Операцию, которая может изменить последовательность выполнения правил алгоритма, назовем оператором управления.
Команды, определяющие порядок исполнения операций, подразделяются на два типа: команды условного перехода и команды безусловного перехода . К командам условного перехода относится, например, правило 4 алгоритма решения задачи 2 . Правило 9 содержит безусловный переход.
В командах условного перехода обязательно присутствует логическое условие типа: если α ◊ β , то …(где ◊ - один из операторов > , ≥ , < , ≤ , = , ≠ ).
Схема алгоритма
Схема алгоритма представляет собой графическое изображение алгоритма с помощью определенным образом связанных между собой блоков. Каждый блок изображается определенной фигурой. Блоки в схеме соединяются дугами. Дуги указывают порядок следования блоков при исполнении алгоритма. Типы блоков представлены на рисунке 1.
Рис.1 . Типы блоков
Прямоугольник вместе с заключенным в нем этапом вычисления S называют функциональным блоком , или процессом (рис.1, а). Ромб с заключенным в нем условием P называют блоком проверки условия , или решением (рис.1, б). Он используется для управления порядком исполнения блоков в схеме алгоритма. Из функционального блока выходит одна стрелка, а из блока проверки условия – две. Последнее объясняется тем, что в результате исполнения команды проверки условия получаем либо выполнение (да), либо невыполнение (нет) заданного условия P. Информационный блок (рис.1, в) используется для ввода и вывода А. Блоки (рис.1, г) и (рис.1, д) называют соответственно начальным и конечным . Блок-схема решения задачи начинается в начальном блоке и заканчивается в конечном.
Исполнение алгоритма решения задачи осуществляется по схеме в направлении, заданном дугами от начального блока к конечному. В информационных блоках указываются значения параметров, которые задаются исполнителю, и значения переменных, которые вводятся. В функциональных и логических блоках записаны операторы от переменных.
Исполнение функциональных блоков осуществляется согласно записанным в них действиям. В логических блоках в результате анализа происходит выбор одной из двух возможных дуг «да» или «нет» и передача управления блоку, на который указывает выбранная дуга. Поэтому при исполнении алгоритма существует всего один путь от начального блока к конечному.
При составлении схемы алгоритмов решения задач подразумевается, что значения переменных в операциях, записанных в блоках, уже заданы. Однако для исполнения алгоритмов необходимы специальные указания на то, откуда брать значения этих переменных.
На рисунках 2 и 3 изображены схемы алгоритмов решения задачи нахождения суммы n - чисел: a1 , a2 , a3 , a4 ,.., an .
Понятие алгоритма относится к основным понятиям информатики. Рассмотрим основные понятия, связанные с понятием алгоритма.
Когда речь идет об алгоритме, всегда подразумевается существование некоторого исполнителя, для которого предназначен алгоритм.
Исполнитель - человек или автомат (например, компьютер), который умеет выполнять определенный конечный набор действий.
Предписание - приказ на выполнение действий из указанного конечного набора.
Система предписаний - совокупность допустимых приказов.
Программа - конечная последовательность предписаний с указанием порядка их выполнения.
В случае, когда исполнителем является компьютер, предписание называется командой , а система предписаний называется системой команд компьютера . Разные компьютеры в зависимости от их устройства могут иметь разные системы команд.
Программирование - составление последовательности команд, которая необходима для решения поставленной задачи.
Составлению программы предшествует разработка алгоритма.
Алгоритм - это точное и понятное указание исполнителю совершить конечную последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи.
Любой алгоритм обладает следующими свойствами:
- 1. Дискретность. Выполнение алгоритма разбивается на последовательность элементарных действий - шагов. Каждое действие должно быть закончено исполнителем прежде, чем он перейдет к выполнению следующего действия. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма, называемое командой.
- 2. Точность или детерминированность. Запись алгоритма должна быть такой, чтобы, выполнив очередную команду, исполнитель точно знал, какую команду надо выполнять следующей.
- 3. Понятность. Каждый алгоритм строится в расчете на конкретного исполнителя, который должен быть в состоянии выполнить каждую команду алгоритма в строгом соответствии с ее назначением.
- 4. Результативность. При точном исполнении всех предписаний алгоритма процесс должен завершится за конечное число шагов и при этом должен быть получен какой-либо ответ на поставленную задачу. В качестве одного из возможных решений может быть установление того факта, что задача не имеет решения
- 5. Массовость. помощью одного и того же алгоритма можно решать однотипные задачи и делать это неоднократно. Свойство массовости значительно увеличивает практическую ценность алгоритмов.
Большая ценность алгоритмов заключается в том, что исполнитель может не вникать в смысл того, что он делает, и вместе с тем получать нуж больше знаний, чем от исполнителя.
Простейшие операции, на которые распадается процесс решения задачи, может реализовать автоматическое устройство, специально созданное для выполнения отдельных команд алгоритма в указанной последовательности. Если удается получить алгоритм решения какой-нибудь задачи, появляется возможность создать машину, которая автоматизировала бы ее решение.
Каждый алгоритм предполагает наличие некоторых исходных данных. Например, для медицинского рецепта (алгоритма) исходными данными являются медикаменты, а результатом - флакон с готовым лекарством. Для алгоритма сложения исходными данными являются пара слагаемых, а результатом - их сумма. Для каждого алгоритма существует класс объектов, допустимых в качестве исходных данных. Иногда исходными данными являются материальные объекты, а иногда - числа.
Алгоритм - это правило, следовательно, оно должно быть сформулировано на некотором языке. Исходные данные и искомые результаты также должны быть описаны на некотором языке, возможно отличном от языка, на котором описан алгоритм.
Таким образом, каждый алгоритм связан с двумя языками: на одном он сформулирован сам, предложения другого являются для него допустимыми вариантами исходных данных.
Разработка алгоритма решения задачи называется алгоритмизацией. В процессе алгоритмизации задача сводится к построению последовательности шагов, расположенных в определенном порядке.
Между алгоритмами и программами нет четкого разграничения. Программой обычно называют алгоритм решения задачи, рассчитанный на исполнение его компьютером и записанный с помощью предложений используемого языка программирования.
Алгоритмической структурой называется стандартный способ соединения отдельных шагов алгоритма для выполнения типичной последовательности действий.
В теории алгоритмов доказывается, что любой алгоритм может быть представлен в виде комбинации трех алгоритмических структур: следования, развилки и цикла.
Представляет собой последовательное выполнение действий (рис. 12).
Рис. 12.
Применяется в случае, когда в зависимости от истинности некоторого логического условия необходимо выполнить то или иное действие (рис. 13).
Рис. 13.
Действия 1 и 2 могут, в свою очередь, включать в себя другие алгоритмические структуры.
Цикл . Применяется, когда некоторые действия необходимо выполнить несколько раз. Существуют две разновидности цикла.
Применяется, когда некоторые операции надо повторять до тех пор, пока некоторое условие не станет ложным (рис. 14).
Рис. 14. Цикл До.
Под начальными присвоениями подразумеваются операции присвоения исходных значений переменным, используемым в цикле. Многократно повторяемая последовательность действий называется телом цикла.
Применяется, когда некоторые операции надо повторять до тех пор, пока некоторое условие не станет истинным (рис. 15).
Рис. 15. Цикл Пока.
Любое управление процессом требует определенных правил и четких действий. Компьютер – это устройство, предназначенное для автоматизации создания, хранения, обработки и передачи данных, а значит здесь должны выполняться четкие предписания для выполнения той или иной задачи.
Для создания программ, предназначенной для решения на ЭВМ какой-либо задачи, требуется составление алгоритма ее решения.
Алгоритмами, например, являются правила сложения, умножения, решения алгебраических уравнений, умножения матриц и т.п. Слово алгоритм происходит от algoritmi, являющегося латинской транслитерацией арабского имени хорезмийского математика IX века аль-Хорезми. Благодаря латинскому переводу трактата аль-Хорезми европейцы в XII веке познакомились с позиционной системой счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система счисления и правила счета в ней.
Иными словами, алгоритм – это точная инструкция, а инструкции встречаются практически во всех областях человеческой деятельности. Возможны алгоритмы проведения физического эксперимента, сборки шкафа или телевизора, обработки детали. Однако не всякая инструкция есть алгоритм.
Инструкция становится алгоритмом только тогда, когда она удовлетворяет определенным требованиям. Одно из требований алгоритма однозначность, т.е. если при применении к одним и тем же данным он даст один и тот же результат.
Применительно к ЭВМ алгоритм позволяет формализовать вычислительный процесс, начинающийся с обработки некоторой совокупности возможных исходных данных и направленный на получение определенных этими исходными данными результатов. Термин вычислительный процесс распространяется и на обработку других видов информации, например, символьной, графической или звуковой.
Если вычислительный процесс заканчивается получением результатов, то говорят, что данный алгоритм применим к рассматриваемой совокупности исходных данных. В противном случае говорят, что алгоритм неприменим к совокупности исходных данных. Любой применимый алгоритм обладает следующими основными свойствами:
· дискретностью;
· определенностью;
· результативностью;
· массовостью.
Дискретность – последовательное выполнение простых или ранее определённых (подпрограммы) шагов. Преобразование исходных данных в результат осуществляется дискретно во времени.
Определенность состоит в совпадении получаемых результатов независимо от пользователя и применяемых технических средств (однозначность толкования инструкций).
Результативность означает возможность получения результата после выполнения конечного количества операций.
Массовость заключается в возможности применения алгоритма к целому классу однотипных задач, различающихся конкретными значениями исходных данных (разработка в общем виде).
Для задания алгоритма необходимо описать следующие его элементы:
· набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;
· правило начала;
· правило непосредственной переработки информации (описание последовательности действий);
· правило окончания;
· правило извлечения результатов.
Алгоритм всегда рассчитан на конкретного исполнителя. В нашем случае таким исполнителем является ЭВМ. Для обеспечения возможности реализации на ЭВМ алгоритм должен быть описан на языке, понятном компьютеру, то есть на языке программирования.
Понятия алгоритма и программы разграничены не очень чётко. Обычно программой называют окончательный вариант алгоритма решения задачи, ориентированный на конкретного пользователя.
Таким образом, можно дать следующее определение программы для ЭВМ:
К основным способам описания алгоритмов можно отнести следующие:
· словесно-формульный (на естественном языке);
· структурный или блок-схемный;
· с использованием специальных алгоритмических языков;
· с помощью граф-схем (граф – совокупность точек и линий, в которой каждая линия соединяет две точки. Точки называются вершинами, линии – рёбрами).
Перед составлением программ чаще всего составляют алгоритм решения поставленной задачи одним из вышеописанных способов.
При словесно -формульном способе алгоритм записывается в виде текста с формулами по пунктам, составляющих последовательность действий.
Пусть, например, необходимо найти значение следующего выражения:
у = 4а – (х + 3).
Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:
1. Ввести значения а и х.
2. Сложить х и 3.
3. Умножить а на 4.
4. Вычесть из 4а сумму (х+3).
5. Вывести у как результат вычисления выражения.
При блок -схемном описании алгоритм изображается геометрическими фигурами (блоками), связанными по управлению линиями (направлениями потока) со стрелками. В блоках записывается последовательность действий.
Такой вид записи алгоритма обладает наибольшими достоинствами. Он наиболее нагляден: каждая операция вычислительного процесса изображается отдельной геометрической фигурой. Кроме того, графическое изображение алгоритма наглядно показывает разветвления путей решения задачи в зависимости от различных условий, повторение отдельных этапов вычислительного процесса и другие детали.
Оформление программ должно соответствовать определенным требованиям (рис. 2.). В настоящее время действует единая система программной документации (ЕСПД), которая устанавливает правила разработки, оформления программ и программной документации. В ЕСПД определены и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД).
Одним из свойств алгоритма является дискретность, т.е. представление процесса вычислений на отдельные шаги и выделения отдельных участков программы на определенные структуры.
Любой вычислительный процесс может быть представлен как комбинация элементарных алгоритмических структур:
· Следование. Предполагает последовательное выполнение команд сверху вниз. Если алгоритм состоит только из структур следования, то он является линейным.
· Ветвление. Выполнение программы идет по одной из двух, нескольких или множества ветвей. Выбор ветви зависит от условия на входе ветвления и поступивших сюда данных.
· Цикл. Предполагает возможность многократного повторения определенных действий. Количество повторений зависит от условия цикла.
· Функция (подпрограмма). Команды, отделенные от основной программы, выполняются лишь в случае их вызова из основной программы (из любого ее места). Одна и та же функция может вызываться из основной программы сколь угодно раз.
При этом выделят три основных вида алгоритмов:
Современные системы программирования обычно предоставляют пользователям мощные и удобные средства разработки программ. В них входят:
· компилятор или интерпретатор;
· интегрированная среда разработки;
· средства создания и редактирования текстов программ;
· обширные библиотеки стандартных программ и функций;
· отладочные программы, т.е. программы, помогающие находить и устранять ошибки в программе;
· "дружественная" к пользователю диалоговая среда;
· многооконный режим работы;
· мощные графические библиотеки; утилиты для работы с библиотеками;
· встроенный ассемблер;
· встроенная справочная служба;
· другие специфические особенности.
Понятие алгоритма так же фундаментально для информатики, как и понятие информации. Существует много различных определений алгоритма, так как это понятие достаточно широкое и используется в различных областях науки, техники и повседневной жизни.
Алгоритм – понятная и точная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное.
Исполнителем алгоритма может быть как человек (кулинарные рецепты, различные инструкции, алгоритмы математических вычислений), так и техническое устройство. Различные машины (компьютеры, промышленные роботы, современная бытовая техника) являются формальными исполнителями алгоритмов. От формального исполнителя не требуется понимание сущности решаемой задачи, но требуется точное выполнение последовательности команд.
Алгоритм можно записывать различными способами (словесное описание, графическое описание – блок схема, программа на одном из языков программирования и т.д.). Программа – это алгоритм, записанный на .
Для создания алгоритма (программы) необходимо знать:
полный набор исходных данных задачи (начальное состояние объекта);
цель создания алгоритма (конечное состояние объекта);
систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить).
Полученный алгоритм (программа) должен обладать следующим набором свойств:
дискретность (алгоритм разбит на отдельные шаги - команды);
однозначность (каждая команда определяет единственно возможное действие исполнителя);
понятность (все команды алгоритма входят в систему команд исполнителя);
результативность (исполнитель должен решить задачу за конечное число шагов).
Большая часть алгоритмов обладает также свойством массовости (с помощью одного и того же алгоритма можно решать множество однотипных задач).
Выше отмечалось, что один и тот же алгоритм может быть записан по-разному. Можно записывать алгоритм естественным языком. В таком виде мы используем рецепты, инструкции и т.п. Для записи алгоритмов, предназначенных формальным исполнителям, разработаны специальные языки программирования . Любой алгоритм можно описать графически в виде блок-схемы . Для этого разработана специальная система обозначений:
| Обозначение | Описание | Примечания |
| Начало и конец алгоритма | ||
 |
Ввод и вывод данных. | Вывод данных иногда
обозначают иначе:
|
 |
Действие | В вычислительных алгоритмах так обозначают присваивание |
 |
Развилка | Развилка - компонент, необходимый для реализации ветвлений и циклов |
 |
Начало цикла с параметром | |
 |
Типовой процесс | В программировании - процедуры или подпрограммы |
 |
Переходы между блоками |
Приведем пример описания алгоритма суммирования двух величин в виде блок-схемы:
Такой способ описания алгоритм наиболее нагляден и понятен человеку. Поэтому, алгоритмы формальных исполнителей обычно разрабатывают сначала в виде блок-схемы, и только затем создают программу на одном из .
Программист имеет возможность конструировать и использовать нетипичные алгоритмические структуры, однако, в этом нет необходимости. Любой сколь угодно сложный алгоритм может быть разработан на основе трёх типовых структур: следования, ветвления и повторения. При этом структуры могут располагаться последовательно друг за другом или вкладываться друг в друга.
Линейная структура (следование).
Наиболее простой алгоритмической структурой является линейная . В ней все операции выполняются один раз в том порядке, в котором они записаны.
Ветвление.
В полном ветвлении предусмотрено два варианта действий исполнителя в зависимости от значения логического выражения (условия). Если условие истинно, то выполняться будет только первая ветвь, иначе только вторая ветвь.
Вторая ветвь может быть пустой. Такая структура называется неполным ветвлением или обходом .
Из нескольких ветвлений можно сконструировать структуру «выбор » (множественное ветвление), которая будет выбирать не из двух, а из большего количества вариантов действий исполнителя, зависящих от нескольких условий . Существенно, что выполняется только одна ветвь - в такой структуре важное значение приобретает порядок следования условий: если выполняются несколько условий, то сработает только одно из них - первое сверху.
Цикл (повторение).
Цикл позволяет организовать многократное повторение одной и той же последовательности команд - она называется телом цикла. В различных видах циклических алгоритмов количество повторений может зависеть от значения логического выражения (условия) или может быть жестко задано в самой структуре. Различают циклы: «д о », «п ока », циклы со счётчиком. В циклах «д о» и «п ока» логическое выражение (условие) может предшествовать телу цикла (цикл с предусловием ) или завершать цикл (цикл с послеусловием ).
Ц иклы «д о » - повторение тела цикла до выполнения условия:
Ц иклы «п ока » - повторение тела цикла пока условие выполняется (истинно):
Ц иклы со счётчиком (с параметром) – повторение тела цикла заданное число раз:
Вспомогательный алгоритм (подпрограмма, процедура).
Вспомогательный алгоритм представляет собой модуль, к которому можно многократно обращаться из основного алгоритма. Использование вспомогательных алгоритмов может существенно уменьшить размер алгоритма и упростить его разработку.
Методы разработки сложных алгоритмов.
Существует два метода разработки сложных алгоритмов:
Метод последовательной детализации задачи («сверху-вниз») состоит в том, что исходная сложная задача разбивается на подзадачи. Каждая из подзадач рассматривается и решается отдельно. Если какие-либо из подзадач сложны, они также разбиваются на подзадачи. Процесс продолжается до тех пор, пока подзадачи не сведутся к элементарным. Решения отдельных подзадач затем собираются в единый алгоритм решения исходной задачи. Метод широко используется, так как позволяет вести разработку общего алгоритма одновременно нескольким программистам, решающим локальные подзадачи. Это необходимое условие быстрой разработки программных продуктов.
Сборочный метод («снизу-вверх») заключается в создании множества программных модулей, реализующих решение типичных задач. При решении сложной задачи программист может использовать разработанные модули в качестве вспомогательных алгоритмов (процедур). Во многих уже существуют подобные наборы модулей, что существенно упрощает и ускоряет создание сложного алгоритма.
Управление - целенаправленное взаимодействие объектов, одни из которых являются управляющими, другие - управляемыми.
В простейшем случае таких объектов два:
С точки зрения информатики управляющие воздействия можно рассматривать как управляющую информацию. Информация может передаваться в форме команд. Последовательность команд по управлению объектом, приводящая к заранее поставленной цели, называется алгоритмом управления . Следовательно, объект управления можно назвать исполнителем управляющего алгоритма. В рассмотренном примере, управляющий объект работает "не глядя" на то, что происходит с управляющим объектом (управление без обратной связи ). Такая схема управления называется незамкнутой . Другая схема управления может учитывать информацию о процессах, происходящих в объекте управления:
В этом случае, алгоритм управления должен быть достаточно гибким, чтобы анализировать эту информацию и принимать решение о своих дальнейших действиях в зависимости от состояния объекта управления (управление с обратной связью ). Такая схема управления называется замкнутой .
Более подробно процессы управления изучаются рассматриваются кибернетикой . Эта наука утверждает, что самые разнообразные процессы управления в обществе, природе и технике происходят сходным образом, подчиняются одним и тем же принципам.
В последнее время все чаще встречаю мысли о переходе на специальность разработчика . Будь то менеджер, консультант, военный офицер, физик ядерщик или ландшафтный дизайнер - все захотели стать программистами. Попробуем разобраться, почему это происходит и к чему может привести.Мотивирующее изображение:
Проблема
Обычно в разработчики переходят новоиспеченные специалисты до 30-ти лет. И сразу же возникает несколько серьезных проблем:- 5-6 лет потерянных на изучение предметов и наук, которые больше никогда не понадобятся;
- Необходимая смена мышления с гуманитарного\технического на логическое\цифровое;
- Освоение 5-6 лет программы технического вуза в кратчайшие сроки;
- Создание угрозы жизни и благополучия людей, компаний, бизнеса...
Время
Спрашивается, зачем человек изучал несколько лет не нужные ему науки? Зачем подвергал себя таким умственным нагрузкам? Чтобы потом все бросить и начать все с начала? Даже 5 лет это много. За это время можно стать миллиардером или же получить Нобелевскую премию, так нет, человек изучает то что ему не интересно, спит на парах и говорит, что философия - это полнейший бред!Хорошо, если он обучается на платном отделении, а если за счет государства? Это значит, что кто-то, мечтавший стать архитектором, менеджером, финансистом, военным, не попал на это место. Ему пришлось искать другое место под солнцем, возможно, он пошел учиться на программиста.
Там же все просто!
Сколько таких новоявленных «программистов», прочитавших о JAVA у Брюса Эккеля. Все они считают себя гениями программирования, а ООП, MVC, Agile, двоичная система исчисления, теория сложности вычислений… не для них.Приведу несколько жизненных примеров:
- «Программист» пишет вторую версию программы. В первой - была одна форма на 50 кнопок. Вторая версия обладает большей функциональностью, но ее логика не так прозрачна. Планируется писать программу пару месяцев. В функционал заложено порядка 100 кнопок на одной форме. После 10-и минутного введения в теорию графов количество кнопок сократилось до одной (удаление точки), срок написания программы сократился до двух дней.
- «Программисту» дали задание написать программу-конвертер. Логика простая: приходит пакет вида ключ=значение, надо по специальной таблице конвертировать его в пакет2 вида ключ2=значение2 и отправить дальше. После двух месяцев «изучения платформы» ему был передан каркас приложения (прием пакета, трансформация, отправка пакетов) старшими товарищами. Через месяц конвертер был готов!
- Множество реализованных велосипедов;
- Говорящий за себя http://govnokod.ru ;
Таланты
Конечно, нельзя не упомянуть про таланты. Есть талантливые люди, которые занимаются разными работами, они везде преуспевают. Но таких крайне мало. Лучше быть компетентным специалистом в одной области, чем в нескольких понемногу.«Найди себе дело по душе и ни единой минуты в жизни ты не будешь работать» - Конфуций. Важно не потратить на поиск этого дела всю жизнь, иначе придется всю жизнь «вкалывать».
Запах пороха
Очень хорошая идея показать, что представляет собой разработка. Понюхать пороха, так сказать! Вот уже и мэры начали изучать JS .В одной компании, моей знакомой и всему отделу по работе с клиентами показали, как верстать страницы, рассказали, что такое теги. Они даже сверстали простые странички.
Но не стоит считать себя после этого знающим все о программировании. Это только начало. А вот дальше надо изучать множество сложных, и попроще материалов и технологий, несколько томов алгоритмов и несчетное число хороших практик и методик.
Заключение
Программирование - это ремесло, разработка - сродни искусству. Для обычных людей - это магия, для программистов тяжелый труд, трансляция непостоянства окружающего мира в мир конечных состояний, нулей и единиц, ограничений оперативной памяти, канала и тактовой частоты процессора.Все же, думаю, большинство «новых программистов» стремятся больше зарабатывать: сидишь себе - деньги получаешь. Правда, потом такие люди сильно подводят свою команду, работают не в полную силу. А если еще и начальство закроет на это глаза (да, да, такое бывает!), то с ними каши не сваришь, google не разработаешь.
Как показывают исследования . IT в России - не самая высокооплачиваемая отрасль. Она занимает лишь третье место. На втором месте сырьевые отрасли, а на первом - высший менеджмент . Из-за специфики IT, программист никогда не достигнет ступеньки высшего менеджмента. Максимум, на что стоит рассчитывать, это должность руководителя отдела, ведущего направления, директора собственной компании.
Поэтому делайте выводы. Смена рода деятельности серьезный шаг, он должен быть обдуман. Минимум, надо будет изучить современный курс программирования, и это займет не один год.
P.S. В комментариях спрашивают про цели заметки: серьезнее относиться в выбору профессии, заниматься только любимым делом, учиться тому что нравится, профессионально расти, а не пробовать все понемногу без определенной цели. Удивляют люди, которые в 30-40 лет так и не смогли найти себе занятие по душе.
