информатика. Вопрос Понятие, структура и задачи информатики
 Скачать 6.17 Mb.
|
Тема 4. Алгоритмы и программыВопрос 1. Понятие алгоритма.Алгоритм является не только одним из главных понятий математики, но одним из главных понятий современной науки. Более того, алгоритм – одно из основополагающих понятий в информатике. Название «алгоритм» произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783-850 гг. В своей книге «Об индийском счете» он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними («столбиком», в нашем понимании – алгоритмы). В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе. И когда в ХХ веке возникла необходимость в наименовании набора последовательных операций, связанных с вычислениями, европейские ученые и назвали этот набор в честь ал-Хорезми алгоритмом. В математике для решения типовых задач мы используем определенные правила, описывающие последовательности действий. Например, правила сложения дробных чисел, решения квадратных уравнений и т.д. Обычно любые инструкции и правила представляют собой последовательность действий, которые необходимо выполнить в определенном порядке. Для решения задачи надо знать, что дано, что следует получить и какие действия, и в каком порядке следует для этого выполнить. Предписание, определяющее порядок выполнения действий над данными с целью получения искомых результатов, и есть алгоритм. Итак, алгоритм – это система точных и понятных предписаний о содержании и последовательности выполнения конечного числа действий для решения задачи. Вопрос 2. Способы представления алгоритмов.Алгоритмы могут быть представлены в виде: формулы, таблицы, графического или словесного описания, а также описания на специальных алгоритмических языках и языках программирования. Представление в виде формулы – очевидно. Например, формула корня квадратного уравнения дает нам правило вычисления результата (то есть, алгоритм), исходя из значений коэффициентов квадратного трехчлена. А известная с начальных классов таблица умножения дает алгоритм получения произведения сомножителей, записанных в первом столбце и первой строке таблицы. Для графического представления алгоритмов используются блок-схемы, содержащие обозначения конкретных действий над данными, применяемыми в вычислениях.
Словесный способ записи алгоритма чрезвычайно прост. Он содержит словесные описания последовательности действий для решения задачи. Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида). 1. Задать два числа. 2. Если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма. 3. Определить большее из чисел. 4. Заменить большее из чисел разностью большего и меньшего из чисел. 5. Повторить алгоритм с шага 2. При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий. Например, необходимо найти значение следующего выражения: у=2а - (х+6). Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде: 1. Ввести значения а и х. 2. Сложить х + 6. 3. Умножить а х 2. 4. Вычесть из 2а сумму (х+6). 5. Вывести у как результат вычисления выражения. Для задания алгоритма необходимо описать следующие его элементы: набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов; правило начала; правила непосредственной переработки информации (описание последовательности действий); правило окончания; правило извлечения результатов. Алгоритмический язык (или псевдокод) представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи. В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что, в свою очередь, облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций. Алгоритм на алгоритмическом языке в общем виде записывается в форме: алг <название алгоритма (аргументы и результаты)> дано <условия применимости алгоритма> надо <цель выполнения алгоритма> нач <описание промежуточных величин> последовательность команд <тело алгоритма> кон Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон, — телом алгоритма. В предложении алг после названия алгоритма в круглых скобках указываются характеристики (арг, рез) и тип значения (цел, вещ, сим, лит или лог) всех входных (аргументы) и выходных (результаты) переменных. При описании массивов (таблиц) используется служебное слово таб, дополненное граничными парами по каждому индексу элементов массива. Примеры предложений алг: алг Объем и площадь цилиндра (арг вещ R, H, рез вещ V, S) алг Корни КвУр (арг вещ а, b, c, рез вещ x1, x2, рез лит t) алг Исключить элемент (арг цел N, арг рез вещ таб А[1:N]) алг Диагональ (арг цел N, арг цел таб A[1:N, 1:N], рез лит Otvet) |
