РЕСПУБЛИКА КАЗАХСТАН

УНИВЕРСИТЕТ «ТУРАН»

Учебно-методический комплекс по дисциплине «Информатика»

Раздел: «Основы алгоритмизации»

Краткий конспект лекций

Методические материалы для лабораторных занятий

Методические рекомендации по СРСП и СРС

Для студентов специальности _________________________________________

АЛМАТЫ, 2009

Содержание

Краткий конспект лекции №11 3

Методические материалы для практического занятия №11 12

Методические рекомендации по СРСП №1 17

Методические рекомендации по СРС №1 19

Краткий конспект лекции №11

Тема: Основы алгоритмизации.

Количество часов: 1 ч.

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

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

Алгоритмы использовались уже в древней Греции: алгоритм Герона вычисления квадратного корня, алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел. Позднее было изобретено много алгоритмов решения вычислительных задач — численного решения уравнений, систем линейных алгебраических уравнений и т.п.

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

С современной точки зрения слово "алгоритм" означает точное описание некоторого процесса (не обязательно вычислительного), инструкцию по его выполнению.

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

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

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

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

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

• Дискретность – предусматривает разбиение процесса обработки информации на более простые этапы (шаги выполнения), выполнение которых человеком или компьютером не вызывает затруднений.

• Понятность. В алгоритм можно включать команды только из системы команд данного исполнителя.

• Определенность (или детерминированность) – характеризует однозначность выполнения каждого отдельного шага преобразования информации. Например, робот будет поставлен в тупик командой "Взять две-три ложки песка": что значит "две-три"?, какого песка?

• Результативность (или конечность) – предполагает завершение работы алгоритма в целом за конечное число шагов;

• Массовость – характеризует пригодность алгоритма для решения определенного класса задач.

Этапы решения задачи на компьютере

Процесс решения задачи на компьютере включает в себя следующие основные этапы:

1. Постановка задачи.

2. Выбор метода решения (построение математической модели).

3. Разработка алгоритма.

4. Составление программы.

5. Реализация программы на компьютере.

6. Анализ полученных результатов.

Постановка задачи

Прежде чем решать задачу на компьютере, необходимо четко определить, чем мы располагаем — какие есть исходные данные, каковы ограничения на них, что будет являться решением задачи. Если задача конкретная (например, надо решить уравнение 2х² + 3х + 5 = 0, где коэффициенты уравнения — константы), то под постановкой задачи понимаем ответ на вопросы:

• какие исходные данные известны;

• что требуется определить.

Если задача обобщенная (например, надо решить квадратное уравнение aх² + bх + c = 0), от отвечать при постановке задачи понадобится еще на третий вопрос: какие данные допустимы. Итак, постановка задачи "решить квадратное уравнение aх² + bх + c = 0" выглядит следующим образом:

Дано: a, b, c — коэффициенты уравнения.

Требуется: x₁, x₂ — корни уравнения. Ограничения: a  0. D = b² - 4ac  0.

Выбор метода решения (построение математической модели)

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

Разработка алгоритма

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

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

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

Реализация программы на компьютере

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

Анализ полученных результатов

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

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

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

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