Материал: Информатика Лекции 27.03.02

Раздел 4. Алгоритмы и способы их записи. Лекции 12-13.

Темы 24-28. Алгоритмы и способы их записи.

Понятие алгоритма используется давно. Сам термин «алгоритм» произошел при переводе на европейские языки имени арабского математика IXв. Аль-Хорезми, которым были описаны правила (алгоритмы) выполнения основных арифметических действий в десятичной системе счисления.

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

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

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

По разновидности алгоритмы можно разделить на три крупных вида:

вычислительные;

информационные;

управляющие.

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

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

Для того, чтобы произвольное описание последовательности действий было алгоритмом, оно должно обладать следующими свойствами:

1. Дискретность. Процесс решения задачи должен быть разбит на последовательности отдельных шагов, каждый из которых называется командой. Примером команд могут служить пункты инструкции, нажатие на одну из кнопок пульта управления, рисование графического примитива (линии, дуги и т.п.), оператор языка программирования. Наиболее существенным здесь является тот факт, что алгоритм есть последовательность четко выделенных пунктов – такие «прерывные» объекты в науке принято называть дискретными.

2. Понятность. Каждая команда алгоритма должна быть понятна тому, кто исполняет алгоритм; в противном случае эта команда и, следовательно, весь алгоритм в целом не могут быть выполнены. Данное требование можно сформулировать более просто и конкретно. Составим полный список команд, который умеет делать исполнитель алгоритма, и назовем его системой команд исполнителя (СКИ). Тогда понятными будут являться только те команды, которые попадают в этот список.

3. Определенность (или детерминированность). Команды, образующие алгоритм (или, можно сказать, входящие в СКИ), должны быть предельно четкими и однозначными. Их результат не может зависеть от какой-либо дополнительной информации извне алгоритма. Сколько бы раз вы не запускали программу, для одних и тех же исходных данных всегда будет получаться один и тот же результат. При наличии ошибок в алгоритме последнее сформулированное свойство может иногда нарушаться. Например, если не было предусмотрено присвоение переменной начального значения, то результат в некоторых случаях может зависеть от случайного состояния той или иной ячейки памяти компьютера. Но это, скорее, не опровергает, а подтверждает правило: алгоритм должен быть определенным, в противном случае это не алгоритм.

4. Результативность. Результат выполнения алгоритма должен быть обязательно получен, т.е. правильный алгоритм не может обрываться безрезультатно из-за какого-либо непреодолимого препятствия в ходе выполнения. Кроме того, любой алгоритм должен завершиться за конечное число шагов. Большинство алгоритмов данным требованиям удовлетворяют, но при наличии ошибок возможны нарушения результативности.

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

но это никак не будет гарантировать корректную его работу в случае отрицательной величины аргумента.

6. Массовость. Алгоритм имеет смысл разрабатывать только в том случае, когда он будет применяться многократно для различных наборов исходных данных. Но массовость алгоритма в отдельных случаях может нарушаться: к числу подобных исключений можно отнести алгоритмы пользования некоторыми простыми автоматами (для них входными данными служит единственный тип монет).

На практике наиболее распространены следующие формы представления алгоритмов:

словесная (запись на естественном языке);

графическая (изображения из графических символов);

псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

программная (тексты на языках программирования).

Словесный способ записи алгоритмов представляет собой

описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Для более сжатого и наглядного описания алгоритма используется графическое описание. Графическое описание алгоритма в форме геометрических фигур с направленными связями, показывающими переходы от одной фигуры, где каждая фигура это определенного предписание (команда) называется блок-схемой.

Раздел 5. Основы языка программирования С/С++. Лекции 14-18.

Тема 29. Понятие о языке программирования и среде программирования. Виды реализаций языков программирования.

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

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

Язык программирования – это набор правил, определяющих систему записей, составляющих программу, синтаксис и семантику

последовательность машинных команд.

Имеется два вида средств реализации (трансляторов) – компиляторы и интерпретаторы.

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

Интерпретатор работает с программой построчно. Каждая строка программы проверяется на наличие ошибок, если их нет, то сразу переводится и выполняется.

Тема 30. Характеристики и свойства языков программирования.

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

Мощность языка характеризуется количеством и разнообразием задач, алгоритмы решения которых можно записать, используя этот язык. Любую задачу, запрограммированную на каком-либо языке, можно запрограммировать и на машинном языке.

Уровень языка характеризуется сложностью решения задач с помощью этого языка. Чем проще для человека записать решение задачи, тем выше уровень языка.

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

Удобочитаемость языка – это свойство, обеспечивающее легкость восприятия программ человеком.

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

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

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

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

Эффективность языка обеспечивает высокоэффективную работу программ, написанных на этом языке.

Темы 31-32. Программа на языке программирования С/С++. Понятие о структурном программировании. Стандартные типы данных.

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

Этот язык был создан в 1972 году Деннисом Ритчи (Bell Laboratories). Основными его предшественниками являются:

Algol – 1960 год – разработан специально созданным международным комитетом – большое внимание было уделено модульной структуре программы;

CPL (Combined Programming Language) – 1963 год – разработка Лондонского и Кембриджского университетов;