Экзаменационные вопросы по дисциплине
"Алгоритмизация и программирования"
Блок 1
Основы алгоритмизации и программирования.
Работа по решению любой задачи с использованием компьютера делится на следующие этапы:
1) Постановка задачи.
2) Формализация задачи.
3) Построение алгоритма.
4) Составление программы на языке программирования.
5) Отладка и тестирование программы.
6) Проведение расчетов и анализ полученных результатов.
Часто эту последовательность называют технологической цепочкой решения задачи на ЭВМ. Непосредственно к программированию в этом списке относятся пункты 3, 4, 5. На этапе постановки задачи должно быть четко сформулировано, что дано и что требуется найти. Здесь очень важно определить полный набор исходных данных, необходимых для получения решения.
Второй этап — формализация задачи. Здесь чаще всего задача переводится на язык математических формул, уравнений, отношений. Если решение требует математического описания какого-то реального объекта, явления или процесса, то формализация равносильна получению соответствующей математической модели.
Третий этап — построение алгоритма. Опытные программисты часто сразу пишут программы на языках, не прибегая к каким-либо специальным способам описания алгоритмов (блок-схемам, псевдокодам). Однако в учебных целях полезно использовать эти средства, а затем переводить полученный алгоритм на язык программирования.
Первые три этапа предусматривают работу без компьютера. Дальше следует собственно программирование на определенном языке, в определенной системе программирования. Последний (шестой) этап — это использование уже разработанной программы в практических целях.
Таким образом, программист должен обладать следующими знаниями и навыками:
- уметь строить алгоритмы;
- знать языки программирования;
- уметь работать в соответствующей системе программирования.
Понятие алгоритма. Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithm! — латинского написания имени Мухаммеда аль-Хорезми (787—850 гг), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел.
Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел — вот первые алгоритмы в математике. Правила алгебраических преобразований, способы вычислений корней уравнений также можно отнести к математическим алгоритмам.
В наше время понятие алгоритма трактуется шире. Алгоритм — это последовательность команд управления каким-либо исполнителем. В школьном курсе информатики с понятием алгоритма, с методами построения алгоритмов ученики знакомятся на примерах учебных исполнителей: Робота, Черепахи, Чертежника и т.д.
Эти исполнители ничего не вычисляют. Они создают рисунки на экране, перемещаются в лабиринтах, перетаскивают предметы с места на место. Таких исполнителей принято называть исполнителями, работающими в обстановке.
Следовательно, в качестве исполнителя выступает компьютер. Компьютер работает с величинами — различными информационными объектами: числами, символами, кодами и т. п. Поэтому алгоритмы, предназначенные для управления компьютером, принято называть алгоритмами работы с величинами.
Рисунок 1.1- Схема алгоритма перехода улицы
Если предписание должно быть выполнено машиной, то необходимо точное, «формальное» описание для соответствующего алгоритма.
Для алгоритмов важно различать следующие аспекты:
1) Постановку задачи, которая должна быть решена с помощью алгоритма.
2) Специфичный способ, каким решается задача, при этом для алгоритма различают:
- элементарные шаги обработки;
- описание выбора отдельных подлежащих выполнению шагов.
Свойства алгоритмов. Массовость -способность получать результат для исходных данных изнекоторого множества.
Результативность -способность получать требуемый результат законечное число шагов.
Детерминированность -способность получать один и тот же результатна каждом шаге для одного и того же набора исходных данных.
Язык программирования. Чтобы алгоритм можно было описать в форме, выполнимой на одной из машин, применяют формальные языки.
Описание алгоритма на формально описанном языке называется программой,а формальный язык- языком программирования.
Формальные языки описываются с помощью специальных нотаций, которые задают правила построения слов. Одна из распространенных нотаций БНФ- нотация (форма Бэкуса- Наура), которая позволяет писать выражения, определяющие множество последовательностей символов, т.е. формальных языков.
