Алгоритмизация и программирование

Технические средства реализации информационных процессов

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

Логический вентиль (вентиль) – это своего рода элемент, из которого состоят электронные узлы ЭВМ. Он работает по принципу крана, открывая или закрывая путь сигналам.

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

Логические функции отрицания, дизъюнкции и конъюнкции реализуют логические схемы, называемые инвертором, дизъюнктором и конъюнктором.

Логическая функция "инверсия", или отрицание, реализуется логической схемой (вентилем), называемой инвертор.

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

Аналогично, если предположить, что на входе инвертора будет напряжение 1 ("истина"), то на выходе инвертора будет сниматься 0 вольт.

Функцию отрицания можно условно отождествить с электрической схемой соединения в цепи с лампочкой (рис. 6.1), в которой замкнутая цепь соответствует 1 ("истина") или х = 1, а размыкание цепи соответствует 0 ("ложь") или х = 0.

Рис. 5.1. Электрический аналог схемы инвертора

Дизъюнкцию реализует логическое устройство (вентиль) называемое дизьюнктор

Дизъюнктор условно изображается схематически электрической цепью вида (рис. 5.2)

Рис. 5.2. Электрический аналог схемы дизъюнктора

Конъюнкцию реализует логическая схема (вентиль), называемая конъюнктором.

Конъюнктор можно условно изобразить схематически электрической цепью вида (рис. 5.3):

Рис. 5.3. Электрический аналог схемы конъюнктора

Схематически инвертор, дизъюнктор и конъюнктор на логических схемах различных устройств можно изображать условно следующим образом (рис. 5.4 – 5.6). Есть и другие общепринятые формы условных обозначений.
Условные обозначения вентилей:

Рис. 5.4.Схема инвертора

Рис. 5.5. Схема конъюнктора

Рис. 5.6. Схема дизъюнктора

Из указанных простейших базовых логических элементов собирают, конструируют сложные логические схемы ЭВМ, например, сумматоры, шифраторы, дешифраторы и др. Большие (БИС) и сверхбольшие (СБИС) интегральные схемы содержат в своем составе (на кристалле кремния площадью в несколько квадратных сантиметров) десятки тысяч вентилей. Это возможно и потому, что базовый набор логических схем (инвертор, конъюнктор, дизъюнктор) является функционально полным (любую логическую функцию можно представить через эти базовые вентили), представление логических констант в них одинаково (одинаковы электрические сигналы, представляющие 1 и 0) и различные схемы можно "соединять" и "вкладывать" друг в друга (осуществлять композицию и суперпозицию схем).

Пример. В двоичной системе таблицу суммирования цифры x и цифры y и получения цифры z с учетом переноса p в следующий разряд можно изобразить таблицей вида:

x	y	z	p

Эту таблицу можно интерпретировать как совместно изображаемую таблицу логических функций (предикатов) вида

Логический элемент, соответствующий этим функциям, называется одноразрядным сумматором и имеет следующую схему (обозначим ее как или – если мы хотим акцентировать именно выбранный, текущий i-й разряд) (рис. 5.7):

Рис. 5.7. Схема одноразрядного сумматора

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

Рис. 5.8. Схема "черного ящика 1"

Из анализа входных значений (входных сигналов) х, у и поразрядного сравнения логических констант в этих сообщениях с константами в значении z – результате выполнения функции в "черном ящике", видно, что подходит, например, функция вида

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

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

Эту задачу решают с помощью методов теоретической информатики (методов булевой алгебры).

Пример. Построим схему для логической функции

Схема, построенная для этой логической функции, приведена на рис. 5.9.

Рис. 5.9. Схема логической функции

Пример. Определим логическую функцию, реализуемую логической схемой вида (рис. 5.10)

Рис. 5.10. Схема искомой функции

Искомая логическая функция, если выписать ее последовательно, будет иметь следующий вид:.

" Алгоритм " является базовым основополагающим понятием информатики, а алгоритмизация (программирование) – основным разделом курса информатики.

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

Алгоритм — это не просто набор конечного числа правил, задающих последовательность выполнения операций для решения задачи. Помимо этого, он имеет 5 важных особенностей:

· конечность. Алгоритм всегда должен заканчиваться после выполнения конечного числа шагов;

· определенность. Каждый шаг алгоритма должен быть однозначно определен;

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

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

· эффективность. Алгоритм обычно считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени.

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

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

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

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

Рис. 6.1. Структура алгоритмического обеспечения

Основные формы использования алгоритмов – автономное, библиотечное, пакетное.

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

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

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

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

Порядок выполнения операций (старшинство операций – по убыванию) в языке С++:

1. Вычисление выражений в скобках;

2. Вычисление стандартных функций;

3. Умножение и деление (обозначаются "*" и "/");

4. Сложение и вычитание (обозначаются "+" и "–").

Рассмотрим базовые простые команды языка С++ [8-9].

1. Команда описания главной функции:

< тип > main ()

{

…

}

2. Команда описания неглавной функции:

< тип > <имя функции > (< передаваемые параметры>)

{

…

}

2. Ввод – команда ввода в рассмотрение (в тело алгоритма) тех или иных входных параметров:

cin >>вводимый параметр;

3. Вывод – команда вывода на экран тех или иных входных или выходных параметров алгоритма:

cout<< выводимый параметр;

4. Присваивание – команда изменения текущего значения переменной вида:

<идентификатор> = <выражение>;

где <идентификатор> соответствует имени переменной, <выражение> – корректно записанное выражение. Знак "=" означает последовательное выполнение двух действий: определение текущего значения <выражения> и замена текущего значения переменной, имя которой задано <идентификатором>, на новое значение, равное значению <выражения>.

5. Символ начала блок а {.

6. Символ конца блока }.

7. Команда вставки комментариев в текст алгоритма имеет вид:

/* комментарий в несколько строк */

// комментарий в одну строку

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

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

1. Действие следования состоит из двух команд с указанной очередностью их выполнения и имеет вид:

<команда – предшественник>;<команда – преемник>.

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

if <условие> <команда, выполняемая при выполнении условия>; else <команда, выполняемая при невыполнении условия>;

Пример. Команда вида

if (х>y) (если текущее значение х больше текущего значения y) у = х; (текущее значение у полагаем равным текущему значению х) else x= y; (иначе (при х <= y) текущее значение x заменяем на текущее значение y)

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

Структура повторения типа "пока (while)" записывается в виде:

while <условие продолжения повторения> <повторяемая команда>;

или

while <условие продолжения повторения> { <повторяемая команда номер 1>; <повторяемая команда номер 2>;... <повторяемая команда номер N>; }Следующим оператором цикла в языке С++ является оператор for for(<присваивание начального значения счетчику цикла>; <условие проверки выхода из цикла>; <изменение счетчика цикла>){ < операторы цикла>}

Данный цикл выполняется по правилу: если условие повторения для текущих его параметров не выполнено, то повторение команд (тела) цикла на этом завершается; если же оно выполнено, то выполняется тело цикла и опять проверяется условие повторения команд тела цикла.

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

Функция (программа) имеет вид:

int main()

{

int i=1,n,summa=0;

cout<<"Input n= \n";

cin>>n;

while (summa<=n)

{

summa=summa+i;

i++;

}

summa=summa+i;

cout<<" Summa = "<<summa;

return 0;

}

Пример. Найти наименьшее общее кратное любых двух целых чисел m, n, найти наибольший их делитель. Программа, содержащая все необходимые подключения к операционной системе Microsoft Visual Studio 2008 C++, будет иметь вид:

#include "stdafx.h"

#include <iostream>

using namespace std;

#include <conio.h>

int main()

{

int n,m,max,min,nok,nod=1,i;

cout<<"Enter n = ";

cin>>n;

cout<<"\n Enter m = ";

cin>>m;

max=n>m?n:m; // выделение наибольшего числа

min=n<m?n:m; // выделение наименьшего числа

// Поиск НОД

for(i=1;i<=min;i++)

// сравнение остатков от деления на ноль

if((m%i==0)&&(n%i==0))nod=i;

cout<<" \n NOD = "<<nod<<"\n";

// Поиск НОK

for(i=max;i<=m*n;i++)

// сравнение на ноль остатков от деления

if((i%m==0)&&(i%n==0))

{

nok=i;

break; // оператор выхода из цикла

}

cout<<" \n NOK = "<<nok<<"\n";

_getch(); /* функция не закрытия экрана после окончания

программы */

return 0; // оператор возврата в вызывающую программу

}

Рассмотрим примеры алгоритмизации (программирования) задач на языке C++.

Пример. Составим алгоритм и программу вычисления факториала заданного натурального числа n, то есть произведения n! = 1 • 2 • 3 • … • (n – 1)•n c использованием рекуррентной формулы n! = (n – 1)! • n.

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

1. Инициализация: n, i=1, fact = 1.

2. fact=fact*i

3. i=i+1

4. Если i <= n переход к п. 2.

5. Печать fact.

6.Конец алгоритма.

Рис. 6.2. Блок – схема алгоритма

Алгоритм, представленный программным кодом имеет вид:

#include "stdafx.h"

#include <iostream>

using namespace std;

#include <conio.h>

int main()

{

int n,i=1,fact=1;

cout<<"Enter n = ";

cin>>n;

for(i=1;i<=n;i++) fact=fact*i;

cout<<" \n n! = "<<fact<<"\n";

_getch();

return 0;

}

6.2. Данные, типы данных, структуры и обработка

Любая актуализация информации опирается на данные.

Данные– это некоторые сообщения, слова в некотором заданном алфавите.

Пример. Число 123 – данное, представляющее собой слово в алфавите из десяти натуральных цифр; число 12,34 – данное, представляющее собой слово в алфавите из десяти натуральных цифр и десятичной запятой; текст "математика и информатика – полезные дисциплины", – данное в алфавите из символов русского языка и знаков препинания, включая пробел.

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

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

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

Тип данных характеризует область определения значений данных.

Задаются типы данных простым перечислением значений типа, например как в простых типах данных, либо объединением (структурированием) ранее определенных типов – структурированные типы данных.

Пример. Зададим простые типы данных "специальность", "студент", "вуз" следующим перечислением:

специальность = (филолог, историк, математик, медик);

студент = (Петров, Николаев, Семенов, Иванова, Петрова);

вуз = (МГУ, РГУ, МГПИ).

Значением типа "студент" может быть Петров.

Пример. Опишем структурированный тип данных "специальность_студента":

специальность_студента=(специальность, студент).

Значением типа "специальность_студента" может быть пара, например, (историк, Семенов).

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

Часто в зависимости от задачи рассматривают данные, которые имеют не только "линейную" (как было рассмотрено выше), но и иерархическую структуру.

Пример. Структуру "вуз" можно задать иерархической структурой, состоящей, например, из следующих уровней: "Ректорат", "Деканаты и подразделения", "Кафедры", "Отделы", "Преподаватели и сотрудники".

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

Пример. В языке С++ для описания типа данных используются служебные слова: int, float, char, string, bool и др.

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

Пример. Для целого и вещественного типов данных используют операции "=", "+", "–", "*", "/", "<", ">", "<=", ">=". Для символьного типа данных используют операции: "=", "!=", "<", ">", "<=", ">=". Например, сравнение "а"<"b" означает, что символ "а" предшествует символу "b" то есть код буквы "a" меньше кода буквы "b" (коды символов приводятся в соответствии с таблицей ASCII – Аmerican Standard Code for Information Interchange, американский стандарт кодирования для обмена данными).

Для описания переменных, значениями которых могут быть лишь символы, тексты, используются соответствующие ключевые слова: char, string.

Текстовые (символьные) константы обычно заключают в апострофы.

Пример. Составить программу на языке С++ проверки строки символов на симметрию.

#include "stdafx.h"

#include <iostream>

using namespace std;

#include "conio.h"

int main(){

int n;

bool sim = true; // sim = true симметрия есть, иначе sim = false

string s; // строка символов

cout<<"Enter the char \n";