Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РФ

РЕФЕРАТ

ИНФОРМАЦИОННО-ЛОГИЧЕСКИЕ И АЛГОРИТМИЧЕСКИЕ ОСНОВЫ ПРОГРАММИРОВАНИЯ. МИКРОПРОЦЕССОРЫ

Выполнил:

Студент курса

Группы

Проверил:

2013

Содержание

• 1. Алгоритмические основы программирования
• 2. Информационно-логические основы программирования
• 3. Микропроцессоры
• Список литературы

Размещено на http://www.allbest.ru/

1. Алгоритмические основы программирования

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

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

Алгоритмизация задачи - процесс разработки (проектирования) алгоритма решения задачи с помощью ПК на основе ее условия и требований к конечному результату.

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

Алгоритм - понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи [1].

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

Термин алгоритм происходит от имени узбекского ученого IX в. АльХорезми, который в своем труде ?Арифметический трактат?, переведенном в XII в. с арабского на латынь, изложил правила арифметических действий над числами в позиционной десятичной системе счисления. Эти правила и называли алгоритмами. Таким образом, правила сложения, вычитания, деления, умножения чисел, правила преобразования алгебраических выражений, правила построения геометрических фигур, грамматические правила правописания слов и предложений - все это алгоритмы. Многие правила, инструкции, записанные в различных документах и представляющие собой подробнейшие указания, годные во всевозможных ситуациях, также можно отнести к алгоритмам.

Виды алгоритмов как логико-математических средств отражают также компоненты человеческой деятельности, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения и определения действий исполнителя подразделяются на [3]:

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

- гибкие алгоритмы, например стохастические, т. е. вероятностные и эвристические.

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

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

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

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

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

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

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

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

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

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

1) последовательную декомпозицию задачи, выделение автономных этапов вычислительного процесса и разбивку каждого этапа на отдельные шаги;

2) формальную запись содержания каждого этапа и/или шага;

3) определение общего порядка выполнения этапов и/или шагов;

4) проверку правильности алгоритма.

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

Часто начинающие программисты не уделяют этапу алгоритмизации достаточного внимания и даже пытаются его игнорировать. В результате процесс программирования сильно усложняется.

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

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

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

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

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

Соответствующие системы правил называют языками описаний.

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

2. Информационно-логические основы программирования

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

Булева алгебра оперирует с логическими переменными, которые могут принимать только два значения: истина или ложь, обозначаемые соответственно 1 и 0.

Основной системой счисления ЭВМ является двоичная система счисления, в которой также используются только две цифры: 1 и 0. Таким образом, одни и те же цифровые устройства ЭВМ могут применяться для обработки как числовой информации в двоичной СС, так и логических переменных. Это обуславливает универсальность (однотипность) схемной реализации процесса обработки информации в ЭВМ.

Совокупность значений логических переменных x₁, x₂, ..., x_n называется набором переменных.

Логической функцией от набора логических переменных (аргументов) F(x₁, x₂, ..., x_n ) называется функция, которая может принимать только два значения: истина или ложь (1 или 0). Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записываются возможные наборы аргументов, а в правой -- соответствующие им значения функции. Логическую функцию порой называют функцией алгебры логики (ФАЛ).

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

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

Вся информация в ЭВМ представляется в двоичной системе счисления. Поставим в соответствие входным сигналам отдельных устройств ЭВМ значения переменных х_i (i = 1, n), а выходным сигналам - значения функций у_j (j = 1, m) (рис. 2.1). Здесь - i-й вход; - j-й выход; n - число входов; т - число выходов в устройстве

Рис. 2.1. Представление схемы ЭВМ

В этом случае зависимостями

можно описывать алгоритм работы любого устройства ЭВМ. Каждая такая зависимость у является «булевой функцией, у которой число возможных состояний и каждой ее независимой переменной равно двум» [стандарт ISO 2382/2-76], т. е. функцией алгебры логики, а ее аргументы определены на множестве {0, 1}. Алгебра логики устанавливает основные законы формирования и преобразования логических функций. Она позволяет представить любую сложную функцию в виде композиции простейших функций. Рассмотрим наиболее употребительные из них.

Известно, что количество всевозможных функций N от п аргументов выражается зависимостью:

N =

При n = 0 можно определить две основные функции (N = 2), не зависящие от каких-либо переменных: у₀, тождественно равную нулю (у₀ = 0), и у₁, тождественно равную единице (y₁ = 1). Технической интерпретацией функции y₁ = 1 может быть генератор импульсов. При отсутствии входных сигналов на выходе этого устройства всегда имеются импульсы (единицы). Функция у₀ = 0 может быть интерпретирована отключенной схемой, сигналы от которой не поступают ни к каким устройствам.

При n = 1 зависимость дает N = 4. Представим зависимость значений этих функций от значения аргумента х в виде специальной таблицы истинности (табл. 2.3).

Таблицы истинности получили такое название, потому что они определяют значение функции в зависимости от комбинации входных сигналов. В этой таблице, как и ранее, y₀ = 0 и y₁ = 1. Функция у₂ = х, а функция y₃ = (инверсия х).

Таблица 2.3 - Таблица функций от одной переменной

Этим функциям соответствуют определенные технические аналоги. Схема, реализующая зависимость у₂ = х, называется повторителем, а схема y₃ = - инвертором.

При n = 2, N = 16, т. е. от двух переменных можно построить шестнадцать различных функций. В табл. 2.4 представлена часть из них, имеющая фундаментальное значение при построении основных схем ЭВМ.

Таблица 2.4 - Таблица функций от двух переменных

Заметим, что в левой части таблицы перечислены всевозможные комбинации входных переменных (наборы значений), а в правой - возможные реакции выходных сигналов. В табл. 2.4 представлены функции y₀-y₃, полностью соответствующие функциям из табл. 2.3, а также новые, часто используемые и интересные функции y₄-y₉. При этом местоположение функций и их нумерация в таблице особого значения не имеют. Для составления аналитического выражения наборы переменных, на которых функция принимает значение единицы, записываются как конъюнкции (логическое умножение) и связываются знаками логического сложения. Такие формы функций получили название дизъюнктивных нормальных форм (ДНФ). Если в этих функциях конъюнкции содержат все без исключения переменные в прямом или инверсном значении, то такая форма функций называется совершенной.

Функция у₄ представляет собой функцию логического сложения, дизъюнкцию. Она принимает значение единицы, если хотя бы одна переменная х₁ или х₂ имеет значение единицы:

.

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

Функция у₅ является инверсной функцией по отношению к у₄:

.

Она имеет название «отрицание дизъюнкции». Иногда в литературе встречается ее специальное название - «стрелка Пирса», - по фамилии математика, исследовавшего ее свойства.

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

.

Функция у₇ является инверсной функцией по отношению к у₆:

.

Она называется «отрицание конъюнкции» или «штрих Шеффера».

Функция у₈ называется логической равнозначностью. Она принимает значение единицы, если все ее переменные имеют одинаковое значение (или 0, или 1):

.

Функция у₉ является инверсной функцией по отношению к у₈:

.

Она принимает значение единицы, если ее переменные имеют противоположные значения. Далее будет показано, что функции y₈ и у₉ являются основой для построения сумматоров, так как они соответствуют правилам формирования цифр двоичных чисел при сложении (вычитании).

Из перечисленных функций двух переменных можно строить сколь угодно сложные зависимости, отражающие алгоритмы преобразования информации, представленной в двоичной системе счисления. Алгебра логики устанавливает правила формирования логически полного базиса простейших функций, из которых могут строиться любые более сложные. Наиболее привычным базисом является набор трех функций {инверсия, дизъюнкция - , конъюнкция - &}. Работа с функциями, представленными в этом базисе, очень похожа на использование операций обычной алгебры.

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

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

3. Микропроцессоры

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

В состав МП входят:

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

2. Арифметико-логическое устройство (АЛУ) - предназначено для выполнения всех арифметических и логических операций над числовой и символьной информацией (в некоторых моделях ПК для ускорения выполнения операций к АЛУ подключается дополнительный математический сопроцессор).

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

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

Микропроцессор характеризуется:

1) тактовой частотой, определяющей максимальное время выполнения переключения элементов в ЭВМ;

2) разрядностью, т.е. максимальным числом одновременно обрабатываемых двоичных разрядов.

Разрядностть МП обозначается m/n/k/ и включает:

m - разрядность внутренних регистров, определяет принадлежность к тому или иному классу процессоров;

n - разрядность шины данных, определяет скорость передачи информации;

k - разрядность шины адреса, определяет размер адресного пространства. Например, МП i8088 характеризуется значениями m/n/k=16/8/20;

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

Микроархитектура микропроцессора - это аппаратная организация и логическая структура микропроцессора, регистры, управляющие схемы, арифметико-логические устройства, запоминающие устройства и связывающие их информационные магистрали.

Макроархитектура - это система команд, типы обрабатываемых данных, режимы адресации и принципы работы микропроцессора.

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

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

Рис. 3.1. Архитектура типового микропроцессора

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

Список литературы

1. Пятибратов, А. П. Вычислительные системы, сети и телекоммуникации: учебник. - 3-е изд., перераб. и доп. / А. П. Пятибратов, Л. П. Гудыно, А. А. Кириченко. - М. : Финансы и статистика, 2005. - 560 с.

2. Бройдо, В. Л. Вычислительные системы, сети и телекоммуникации / В. Л. Бройдо, О. П. Ильина. - СПб. : Питер, 2008. - 766 с.

3. Кокова, В. И. Вычислительные системы, сети и телекоммуникации: учеб.-метод. пособие для студентов специальности 080801.65 «Прикладная информатика (в экономике)» дневной и заочной форм обучения / сост. В. И. Кокова. - Красноярск : КГТУ, 2006. - 124 с.

4. Суворов, А. Б. Телекоммуникационные системы, компьютерные сети и Интернет : учеб. пособие / А. Б. Суворов. - Ростов н/Д : Феникс, 2007. - 384 с.

5. Акулов, О. А. Информатика: базовый курс : учебник для студентов вузов, бакалавров, магистров / О. А. Акулов, Н. В. Медведев. - М. : Омега-П, 2008. - 574 с.

6. Обработка данных. Словарь. Часть 2. Арифметические и логические операции : Стандарт ISO 2382/2-76.

7. Обработка данных. Словарь. Часть 1. Основные термины : Стандарт ISO 2382/1-84.

8. Opгaнизaция дaнныx в cиcтeмax oбpaбoтки дaнныx. Tepмины и oпpeдeлeния : ГОСТ 20886-85. - Введ. 01.07.1986.

Размещено на Allbest.ru