Билет 6

Задание 1

Задачник № 1 – стр. 275, Семакин – стр. 282

Задание 2

Вопросы:

1. В чем суть понятий алгоритма и исполнителя? Перечислите их основные свойства.

2. Каковы особенности различных подходов и парадигм в развитии программирования? Приведите классификацию язы­ков программирования.

1. Алгоритм – это точное и понятное предписание исполнителю совершить некоторую последователь­ность действий на решение поставленной задачи.

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

1) Описываемый процесс должен быть разбит на последовательность отдельных шагов (дискретность);

2) Алгоритмы составляются с ориентацией на определенного исполнителя (нужно знать, какие команды этот исполнитель может понять и исполнять, а какие не может);

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

4) Результативность (за конечное число шагов должен получиться определенный результат);

5) Массовость (наиболее распространены алгоритмы, обеспечивающие решение не одной конкретной задачи, а некоторого класса задач данного типа)

Исполнитель – тот, кто исполняет. Вся совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя (СКИ). Блок-схема – это графическое описание алгоритма. Важ­нейшее свойство исполнителя – умение выполнять некоторые команды. Исполнитель не вникает в смысл того, что делает, но получает необходимый результат, т.е. исполнитель действует формально (отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила и инструкции).

2. Парадигма – это некоторый набор идей и рекомендация, определяющих стиль написания программ.

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

С появлением структурного программирования описанные выше трудности бы­ли во многом преодолены. В основе технологических принципов структурного программирования лежит утверждение о том, что логическая структура программы может быть выражена комбинацией трех базовых структур: следования, ветвления и цикла (это содержание теоремы Бема-Якопини).

Следование - самая важная из структур. Она означает, что действия могут быть выполнены друг за другом, рис. 1.19:

Эти прямоугольники могут представлять как одну единственную команду, так и множество операто­ров, необходимых для выполнения сложной обра­ботки данных.

Ветвление - это структура, обеспечивающая выбор между двумя альтернатива­ми. Выполняется проверка, а затем выбирается один из путей (рис. 1.20).

Эта структура называется также «ЕСЛИ - ТО - ИНАЧЕ», или «развилка». Каж­дый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран.

Может оказаться, что для одного из результатов проверки ничего предпринимать не надо. В этом случае можно при­менять только один обрабатывающий блок, рис. 1.21:

Цикл (или повторение) предусматривает по­вторное выполнение некоторого на­бора команд про­граммы. Если бы циклы не существовали, вряд ли занятие про­граммированием было бы оправданным: циклы позво­ляют записать длинные последовательности операций обработки данных с помощью небольшого числа по­вторяющихся команд. Разновидности цикла изображены на рис. 1.22 и рис. 1.23.

Цикл начинается с проверки логического выражения. Если оно истинно, то вы­полняется «я», затем все по­вторяется снова, пока логическое выражение сохраняет значение «истина». Как только оно становится лож­ным, выполнение операций «а» прекращается и управление переда­ется по программе дальше.

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

Направление выполнения команд часто изображают сверху вниз.

Существуют различные парадигмы программиро­вания, и преподава­ние каждой из них имеет свои осо­бенности. К основным парадигмам программирования относятся: а процедурное программирование (Паскаль, Бейсик. Фортран, Си, Ассемблеры); D логическое программирование (Пролог); □ функциональное программирование (Лисп); D объектно-ориентированное программирование (Смолток, Си++, Делфи).

В скобках приведены примеры языков программи­рования, в которых реализована соответствующая па­ра­дигма.

Классической, универсальной и наиболее распро­страненной является процедурная парадигма. Наибо­льшее количество существующих языков программи­рования относятся к этой линии. Поэтому чаще всего в учеб­ных заведениях изучается процедурное програм­мирование. А наиболее часто изучаемыми в школе языками программирования являются Паскаль и Бей­сик. В дальнейшем под словом «программирование» мы будем подразумевать именно процедурную парадигму. Процесс изучения и практического освоения про­граммиро­вания можно разделить на три части: D изучение методов построения вычислительных ал­горитмов;

D изучение языка программирования; а изучение и практическое освоение определенной системы програм­мирования.

Здесь и в дальнейшем термин «вычислительные алгоритмы» будем понимать в самом широком смысле как алгоритмы работы с величинами любых типов, ориентированные на исполнителя — ЭВМ.

Процедурные (или алгоритмические) программы представляют из себя систему предписаний для решения конкретной задачи. Роль компьютера сводится к механи­ческому выполнению этих предписаний.

Процедурные языки разделяют на языки низкого и высокого уровня.

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

Программы на языках высокого уровня близки к естественному (английскому) языку и представляют набор заданных команд.

Перечислим наиболее известные системы программирования.

1. Фортран (FORmula TRANslating system - система трансляции формул); старей­ший и по сей день активно используемый в решении задач математической ори­ентации язык.

2. Бейсик (Beginner's All-purpose Symbolic Instruction Code - универсальный символический код инструкций для начинающих); несмотря на многие не­дос­татки и изобилие плохо совместимых версий - самый популярный по числу пользователей.

3. Алгол (ALGOrithmic Language - алгоритмический язык); сыграл большую роль в теории, но для практиче­ского программирования сейчас почти не используется.

4. ПЛ/1 (PL/1 Programming Language - язык программирования первый). Многоце­левой язык; сейчас почти не используется.

5. Си (С - «си»); широко используется при создании системного программного обеспечения.

6. Паскаль (Pascal - назван в честь ученого Блеза Паскаля); чрезвычайно популя­рен как при изучении про­граммирования, так и среди профессионалов. На его базе созданы несколько более мощных языков (Модула, Ада, Дельфи).

7. Кобол (COmmon Business Oriented Language - язык, ориентированный на общий бизнес); в значительной мере вышел из употребления.

3. Дельфи (Delphi) - язык объектно-ориентированного «визуального» программи­рования; в данный момент чрезвычайно популярен.

9. Джава (Java) - платформенно-независимый язык объектно-ориентированного программирования, чрезвы­чайно эффективен для создания интерактивных веб­страниц.

Среди непроцедурных языков наиболее известны

1. Лисп (Lisp);

2. Пролог (PROgramming in LOGic);

3. Оккам (назван в честь философа У. Оккама).

Программирование разделяется:

1) процедурное: операциональное (Ассемблер, Бейсик) и структурное (Паскаль);

2) непроцедурное: объектное (Смолток, Делфи), логическое (Пролог), функциональное (Лисп).