Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема 1. Алгоритмы и способы их представления
Главная особенность всех вычислений на ЭВМ состо ит в том, что в основе ее работы лежит программный принцип управления. Это означает, что для решения как са мой простой, так и самой сложной задачи пользователю необходимо использовать перечень инструкций или команд, следуя которым шаг за шагом ЭВМ выдаст необходимый результат.
Таким образом, для того, чтобы решать задачу на ЭВМ, ее необходимо сначала алгоритмизировать. Именно алгоритмический принцип и лежит в основе рабо ты всех ЭВМ. Умение выделять алгоритми ческую суть явления и строить алгоритмы - очень важно для человека любой профессии.
Алгоритм – строгая и четкая система правил, которая определяет последовательность действий над некоторыми объектами и после конечного числа шагов приводит к достижению поставленной цели.
Например, пусть необходимо найти корень уравнения ax + b = 0. В этой задаче:
|
a, b |
- исходные данные, в качестве которых можно использовать любые числовые данные; |
|
x |
- корень уравнения, результат решения. |
Метод решения (алгоритм) состоит в вычислении x = - b / a при a < > 0.
Здесь a, b, x - переменные.
Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя (человека, робота, компьютера, языка программирования и т.д.). Свойством, характеризующим любого исполнителя, является то, что он умеет выполнять некоторые команды. Совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя. Алгоритм описывается в командах исполнителя, который будет его реализовывать. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.
Алгоритм не только задает последовательность выполнения операций при решении конкретной задачи. Он должен обладать следующими свойствами:
Существуют множество различных форм записи алгоритмов. Это связано с тем, что каждый исполнитель алгоритмов "понимает" лишь такой алгоритм, который записан на его "языке" и по его правилам. Условно выделяют 4 формы записи алгоритмов:
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.
Алгоритм может быть следующим:
заменить большее из чисел разностью большего и меньшего из чисел;
повторить алгоритм с шага 2.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи.
Словесный способ не имеет широкого распространения по следующим причинам:
Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.
Такое графическое представление называется схемой алгоритма или блок-схемой.
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Схема алгоритма – графическое представление алгоритмов. Каждый пункт алгоритма отображается на схеме некоторой геометрической фигурой – блоком – дополняется элементами словесной записи. Правила выполнения схем алгоритмов регламентируются ГОСТ 19.002-80.
Блоки на схемах соединяются линиями потоков информации. Основное направление потока информации идет сверху вниз и слева направо (стрелки могут не указываться), снизу вверх и справа налево – стрелка обязательна. Количество входящих линий для блока не ограничено. Выходящая линия должна быть одна (исключение составляет логический блок).
Таблица 1
Основные элементы блок-схем
Например: Алгоритм вычисления значения выражения .
Рисунок 1.
Элементарные шаги алгоритма можно объединить в следующие алгоритмические конструкции: линейные (последовательные), разветвляющиеся, циклические и рекурсивные.
Линейная структура процесса вычислений предполагает, что для получения результата необходимо выполнить некоторые операции в определенной последовательности. Например, для определения площади треугольника по формуле Герона необходимо сначала определить полупериметр треугольника, а затем по формуле его площадь. Стандартная блок-схема линейного алгоритма приводится на рисунке 2,а (вычисление произведения двух чисел A и B).
Разветвленная структура процесса вычислений предполагает, что конкретная последовательность операций зависит от значений одного или не скольких параметров. Например, если дискриминант квадратного уравнения не отрицателен, то уравнение имеет два корня, а если отрицателен, то действительных корней нет. Примером может являться разветвляющийся алгоритм, изображенный на рисунке 2,б. Аргументами этого алгоритма являются числа А и В, а результатом число – Х. Если условие А>=В истинно, то выполняется операция умножения чисел (Х=А*В), в противном случае выполняется операция сложения (Х=А+В). В результате печатается то значение Х, которое получаются в результате выполнения одного из действий.
Циклическая структура процесса вычислений предполагает, что для получения результата некоторые действия необходимо выполнить несколько раз. Например, для того, чтобы получить таблицу значений функции на заданном интервале изменения аргумента с заданным шагом, необходимо соответствующее количество раз определить следующее значение аргумента и посчитать для него значение функции.
Процессы вычислений циклической структуры в свою очередь можно разделить на три группы:
Рисунок 2. Примеры структур алгоритмов:
а – линейный алгоритм, б – алгоритм с ветвлением, в – алгоритм с циклом.
Алгоритмы простых программ разрабатывают, продумывая последовательность действий для решения некоторой задачи, как это было выполнено в примере. Для разработки алгоритмов более сложных программ целесообразно использовать метод пошаговой детализации. Параллельно с разработкой алгоритма уточняют диапазон изменения, точность и структуры представления переменных, используемых для хранения исходных данных и результатов, а также для временного размещения промежуточных результатов, и описывают их в специальных таблицах.
Тема 2. Эволюция языков программирования
Общеизвестно, что информационные технологии являются одной из наиболее быстро развивающихся областей современной жизни. Новые технологии, проекты, названия и аббревиатуры появляются едва ли не каждый день.
Язык программирования – набор ключевых слов (словарь) и система правил (грамматических и синтаксических) для конструирования операторов, состоящих из групп или строк чисел, букв, знаков препинания и других символов, с помощью которых программисты могут сообщать компьютеру набор команд.
В настоящее время в мире существует несколько сотен реально используемых языков программирования. Для каждого есть своя область применения. В зависимости от степени детализации обычно определяется уровень языка программирования — чем меньше детализация, тем выше уровень языка.
По этому критерию можно выделить следующие уровни языков программирования:
Машинные языки и машинно-ориентированные языки – это языки низкого уровня, требующие указания мелких деталей процесса обработки данных. Языки же высокого уровня имитируют естественные языки, используя некоторые слова разговорного языка и общепринятые математические символы. Эти языки более удобны для человека.
Языки высокого уровня делятся на:
Языки программирования можно классифицировать по типам задач следующим образом:
Процедурное программирование. Каждый оператор такого языка является указанием компьютеру совершить некоторое действие, например, принять данные от пользователя, провести с ними определенные действия и вывести результат этих действий на экран. Программы написанные на процедурных языках представляют собой последовательность инструкций.
Для небольших программ не требуется дополнительной внутренней организации. Программист создает перечень инструкций, а компьютер выполняет действия, соответствующие этим инструкциям.
Структурное программирование. Основой структурного программирования является деление программы на функции и модули. Когда размер программы велик, список команд становится слишком громоздким. Мало кто из программистов способен удерживать в голове большое число строк кода. Функция является средством, облегчающим восприятие при чтении текста программы (термин функция употребляется в языках С и С++, в других языках программирования это же понятие называют подпрограммой или процедурой). Программа, построенная на основе процедурного метода, разделана на функции, каждая из которых в идеальном случае выполняет некоторую законченную последовательность действий и имеет явно выраженные связи с другими функциями программы. Также можно объединить несколько функций в модуль.
Главной проблемой структурного программирования является невозможность его сопоставления картинам реального мира. В реальном мире нам приходится иметь дело с объектами, такими как люди, машины. Эти объекты нельзя отнести ни к данным, ни к функциям, поскольку реальные вещи представляют собой совокупность свойств и поведения.
Объектно-ориентированное программирование. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути, описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.
ООП позволяет разложить проблему на связанные между собой задачи. Каждая проблема становится самостоятельным объектом, содержащим свои собственные коды и данные, которые относятся к этому объекту. В этом случае исходная задача в целом упрощается, и программист получает возможность оперировать с гораздо большими по объему программами.
Основополагающей идеей ООП является объединение данных и действий, производимых над ними, в единое целое, которое называется объектом. Функции объекта, называемые в С++ методами или функциями-членами, обычно предназначены для доступа к данным объекта. Если необходимо считать какие-либо данные объекта, нужно вызвать соответствующий метод, который выполнит считывание и возвратит требуемое значение. Прямой доступ к данным не возможен. Данные сокрыты от внешнего воздействия, что защищает их от случайного изменения. Говорят, что данные инкапсулированы. Термины сокрытие и инкапсуляция являются ключевыми в описании объектно-ориентированных языков.
Типичная программа на С++ состоит из совокупности объектов, взаимодействующих между собой посредством вызова методов друг друга.
Тема 3. Трансляция, компиляция и интерпретация
Транслятор – это программа или техническое средство, выполняющее преобразование программы, представленной на одном из языков программирования, в программу на другом языке, в определенном смысле равносильную первой.
Компиляция в программировании – преобразование программы, представленной на одном из языков программирования, в коды на машинно-ориентированном языке, которые принимаются и исполняются непосредственно процессором. Результатом компиляции является объектный файл с необходимыми внешними ссылками для компоновщика. Программа уже переведена в машинные инструкции, однако еще не полностью готова к выполнению.
Компилятор – это программа, предназначенная для трансляции исходного текста программы с высокоуровневого языка в объектный код. Входной информацией для компилятора является описание алгоритма или программа на языке программирования. На выходе компилятора – эквивалентное описание алгоритма на машинно-ориентированном языке (объектный код).
Компоновка – это один из этапов создания исполняемого файла. Компилировать – проводить трансляцию машинной программы с проблемно-ориентированного языка на машинно-ориентированный язык (создание объектного кода) для ее исполнения. Результатом компиляции является объектный файл с необходимыми внешними ссылками для компоновщика. Программа уже переведена в машинные инструкции, однако еще не полностью готова к выполнению. В объектном файле имеются ссылки на различные системные функции. Даже если в программе явно не упомянута ни одна функция, необходим, по крайней мере, один вызов системной функции – завершение программы и освобождение всех принадлежащих ей ресурсов.
Компоновщик – модуль системы программирования или самостоятельная программа, которая собирает результирующую программу из объектных модулей и стандартных библиотечных модулей. Этот процесс называется компоновкой, его результатом и будет исполняемый файл. С процедурой интерпретации компоновка не связана.
При работе с программами существуют этапы: компиляции, компоновки, интерпретации, исполнения программы.
Создание исполняемого файла из исходного текста программы предполагает выполнение этапов а и б (компиляции и компоновки).
Исполняемый файл – это файл, который может быть обработан или выполнен компьютером без предварительной трансляции. Обычно исполняемый файл получается в результате компиляции и компоновки объектных модулей и содержит машинные команды и/или команды операционной системы.
Интерпретатор анализирует и тут же выполняет программу покомандно, по мере поступления ее исходного кода на вход интерпретатора. Алгоритм работы простого интерпретатора:
Утверждение «Языковый процессор, который построчно анализирует исходную программу и одновременно выполняет предписанные действия, а не формирует на машинном языке скомпилированную программу, которая выполняется впоследствии» справедливо для интерпретатора. Режим интерпретации можно использовать при отладке программ на языке высокого уровня.
Интерпретация в разработке программ – процесс непосредственного покомандного выполнения программы без предварительной компиляции, «на лету». В большинстве случаев интерпретируемая программа работает намного медленнее, чем скомпилированная программа, но не требует затрат на компиляцию, что в случае небольших программ может повышать общую производительность. Интерпретация связана с получением переменными значений в процессе работы программы.