Введение. Ранее в общих чертах было рассмотрено устройство компьютера

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

Как вам известно аппаратные средства, часто называемые в нашей литературе жаргонным словом «железо» или американским термином «hardware». В свою очередь, программные средства называются английским словом «software».

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

Вопрос 1. Основы алгоритмизации.

1.1 Понятие и свойства алгоритмов

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

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

Объектами действий алгоритма являются данные - информация представленная в форме для обработки на ЭВМ.

Данные подразделяются на входные и выходные.

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

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

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

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

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

Формульно-словесная (задание инструкций о выполнении действий с использованием математических символов в сочетании со словесными пояснениями);

Алгоритмический язык (программа на алгоритмическом языке, например, на бейсике);

Графическая (блок-схемная).

1.3. Основные свойства алгоритмов

Сформулируем основные свойства алгоритмов:

- определенность (набор указаний должен быть точным и понятным);

- массовость (предполагается, что алгоритм должен быть пригоден для решения всех задач данного типа);

- дискретность (возможность расчленить алгоритм на элементарные части, выполнение которых не вызывает сомнения);

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

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

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

Для изображения алгоритмов будем использовать блок-схемы, формируемые из типовых блоков, показанных на рис. 1.

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

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

Структура "ветвление" предполагает выполнение одной из двух групп действий в зависимости от выполнения условия в блоке ветвления. На рис. 3 знаком "+" показано выполнение условия, а знаком "-" — его невыполнение. Часто используется неполная команда ветвления, когда один из блоков действия отсутствует.

Структура "цикл" имеет несколько разновидностей. На рис. 4 показан цикл типа "пока" с предусловием. Действия внутри этого цикла повторяются пока выполняется условие в блоке ветвления, причем сначала проверяется условие, а затем выполняется действие. Достаточно часто используются другие типы цикла, показанные на рис. 5 и 6. Цикл с постусловием(цикл-до) программируется оператором

Repeat <тело цикла> Until <условие окончания>

В цикле с постусловием проверка условия выхода из цикла выполняется после очередного действия. Цикл "для" является модификацией цикла "пока" для ситуации, когда заранее известно количество повторений некоторых действий. Запись в блоке заголовка цикла на рис.6 показывает пример описания заголовка цикла, в котором действия повторяются столько раз, сколько целых значений приобретает параметр цикла i от своего начального значения 1 до конечного N с шагом 1. Обычно шаг не указывается, если он равен 1.

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

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

1.4. Методика разработки алгоритмов

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

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

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

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

Принцип поэтапной детализации алгоритма (другое название — "проектирование сверху-вниз"). Этот принцип предполагает первоначальную разработку алгоритма в виде укрупненных блоков (разбиение задачи на подзадачи) и их постепенную детализацию.

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

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

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

Пример 1

Разработать блок-схему алгоритма Евклида, определяющего наибольший общий делитель (НОД) двух натуральных чисел A и B.

В основе алгоритма Евклида лежит правило:

НОД(A,B)= НОД(min(A,B), |A-B|),

где НОД(A,B) — наибольший общий делитель двух натуральных чисел A и B.

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

1.5 Основные этапы компьютерного решения задач

Обобщим рассмотренные выше примеры и принципы разработки алгоритмов и программ и выделим главные этапы методики программирования задач.

Постановка задачи. Основное требование к постановке задачи – достаточное количество информации для решения задачи. Очень часто постановка задачи выполняется не программистом, а некоторым Заказчиком. Программист является Исполнителем заказа. От него требуется добиться от Заказчика полной информации о решаемой задаче.

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

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

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

Тестирование алгоритма. Этап предполагает проверку алгоритма вручную с использованием подготовленных ранее контрольных примеров. Для сложных задач этот этап может оказаться весьма трудоемким, поэтому опытные программисты пропускают его и тестируют программу.

Программирование алгоритма. Программирование является формальной записью алгоритма средствами языка программирования.

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

Эксплуатация программы и интерпретация результатов. В сложных программах может быть недостаточно тестирования для устранения всех ошибок. Очень час-то они обнаруживаются на стадии эксплуатации Заказчиком.

Успех в разработке программы зависит от двух основных факторов: соблюдения описанной выше методики и от опыта программирования. Не следует игнорировать или недооценивать этапы проектирования программы (1 – 5), выполняемые вне компьютера. "Час, потраченный на выбор алгоритма, стоит пяти часов программирования" (Д.Ван-Тассел. Стиль, разработка, эффективность, отладка и испытание программ.- М.: Мир, 1985).

Пример 2

тестирование вручную алгоритма решения задачи на примере алгоритма Евклида (рис. 14).

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

Вопрос 2. Основы программирования

Язык программирования — это способ записи программ решения различных задач на ЭВМ в понятной для компьютера форме. Процессор компьютера непосредственно понимает язык машинных команд (ЯМК).

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

Программы на МК программисты писали лишь для самых первых ламповых машин — ЭВМ первого поколения. Программирование на МК — дело непростое. Программист должен знать числовые коды всех машинных команд, должен сам распределять память под команды программы и данные.

В 1950-х гг. появляются первые средства автоматизации программирования — языки Автокоды («Ассемблеры»). Появление языков типа Автокод-Ассемблер облегчило участь программистов. Переменные величины стали изображаться символическими именами. Числовые коды операций заменились на словесные обозначения (легче запомнить). Язык программирования стал понятнее для человека, но при этом удалился от языка машинных команд. Чтобы компьютер мог исполнять программы на Автокоде, потребовался специальный переводчик — транслятор. Транслятор — это системная программа, переводящая текст программы в текст эквивалентной программы на МК.

Компьютер, оснащенный транслятором с Автокода, понимает Автокод. В этом случае можно говорить о псевдо-ЭВМ (аппаратура плюс транслятор с Автокода), языком которой является Автокод. Языки типа Автокод-Ассемблер являются машинно-ориентированными, т.е. они настроены на структуру машинных команд конкретного компьютера. Разные компьютеры с разными типами процессоров имеют разный Ассемблер.

Языки программирования высокого уровня (ЯПВУ) являются машинно-независимыми языками. Одна и та же программа на таком языке может быть выполнена на ЭВМ разных типов, оснащенных соответствующим транслятором. Форма записи программ на ЯПВУ по сравнению с Автокодом еще ближе к традиционной математической форме, к естественному языку. Очень скоро вы увидите, что, например, на языке Паскаль она почти такая же, как на школьном Алгоритмическом языке. ЯПВУ легко изучаются, хорошо поддерживают структурную методику программирования.

Первыми популярными языками высокого уровня (1950-х) - Фортран, Кобол (в США) и Алгол (в Европе). Для первых ЯПВУ предметная ориентация языков была характерной чертой.

В 1965 г. в Дартмутском университете был разработан язык Бейсик. По замыслу авторов это простой язык, легко изучаемый, предназначенный для программирования несложных расчетных задач. Наибольшее распространение Бейсик получил на микроЭВМ и персональных компьютерах. На некоторых моделях школьных компьютеров программировать можно только на Бейсике. Однако Бейсик — неструктурный язык, и потому он плохо подходит для обучения качественному программированию. Справедливости ради следует заметить, что последние версии Бейсика для ПК(например, QBasic) стали более структурными и по своим изобразительным возможностям приближаются к таким языкам, как Паскаль.

Значительным событием в истории языков программирования стало создание в 1971 г. языка Паскаль. Его автор —швейцарский профессор Н.Вирт — разрабатывал Паскаль как учебный язык структурного программирования.

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

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

ЭВМ будущего, пятого поколения называют машинами «искусственного интеллекта». Но прототипы языков для этих машин были созданы существенно раньше их физического появления. Это языки ЛИСП и Пролог.

Реализовать тот или иной язык программирования на ЭВМ— это значит создать транслятор с этого языка для данной ЭВМ. Существуют два принципиально различных метода трансляции. Они называются соответственно компиляция и интерпретация.

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

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

• синхронный перевод — лектор читает доклад, переводчик одновременно с ним слово в слово переводит выступление.

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

При компиляции в память ЭВМ загружается программа-компилятор. Она воспринимает текст программы на ЯПВУ как исходную информацию. После завершения компиляции получается программа на языке машинных команд. Затем в памяти остается только программа на ЯМК, которая выполняется, и получаются требуемые результаты.

Интерпретатор в течение всего времени работы программы находится во внутренней памяти. В ОЗУ помещается и программа (на ЯПВУ). Интерпретатор в последовательности выполнения алгоритма «читает» очередной оператор программы, переводит его в команды и тут же выполняет эти команды. Затем переходит к переводу и выполнению следующего оператора. При этом результаты предыдущих переводов в памяти не сохраняются. При повторном выполнении одной и той же команды она снова будет транслироваться.

При компиляции исполнение программы разбивается на два этапа: трансляцию и выполнение.

При интерпретации, поскольку трансляция и выполнение совмещены, программа на ЭВМ проходит в один этап.

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

Программы на Паскале, Си, Фортране всегда компилируются. Бейсик чаще всего реализован через интерпретатор.

2.2. Структура и способы описания языков программирования высокого уровня

Во всяком языке программирования определены:

- способы организации данных

- способы организации действий над данными.

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

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

.

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

Всякий язык программирования имеет три основные составляющие: алфавит, синтаксис и семантику.

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

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

Для описания синтаксиса языка программирования тоже нужен какой-то язык

Вопрос 3. Основные понятия и назначение программного обеспечения ПК.

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

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

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

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

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

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

- базовый уровень;

- системный уровень;

- служебный уровень;

- прикладной уровень.

Определению интерфейс можно дать общее определение: - это средства взаимодействия, средства связи, сопряжения, согласования.

Всего различают три вида интерфейса:

Физический интерфейс - взаимосвязь на уровне электронных компонент;

Интерфейс программиста - комплекс правил и соглашений о стыковке программ;

Интерфейс пользователя - набор средств диалога, взаимодействия программы (компьютера) с человеком. Такой диалог обеспечивается через основные элементы интерфейса: меню и окно.

Заключение

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

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