1.Введение. Краткий обзор истории развития и классификация языков программирования (по уровню близости к аппаратному обеспечению; по степени автоматизации процесса программирования; по направлению использования создаваемого прикладного программного обеспечения). 2 часа

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

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

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

Перечислим некоторые особенности языка Си:

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

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

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

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

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

2.Понятие формального алгоритма. Тезис Тьюринга - Черча об эквивалентности различных определений вычислимости. Абстрактная машина фон Неймана. Понятие об элементарном исполнителе. 2 часа

Понятие формального алгоритма.

Алгоритм- это заранее заданная последовательность четко

определенных правил или команд для получения решения задачи за конечное число шагов.

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

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

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

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

До Тьюринга для определения формального алгоритма использовалось определение Черча. Определение основано на общей рекурсивности Геделя. В 36г. Тьюринг и Черч выдвинули тезис о том, что определения вычислимости могут быть сведены к определению Тьюринга. В частности любой алгоритм можно признать вычислимым, если он допускает реализацию на машине Тьюринга. Машина Тьюринга- гипотетическая: Выполняет считывание символа с ленты, передвинуть ленту, нанести символ на ленту. Рекурсивная программа вызывает сама себя.

Абстрактная машина Фон - Нейманав 45г. при разработке ЭДВАК, базируется на теоретической работе Тьюринга и Бэббиджа. Предложение. Трехкомпонентную архитектуру, получившее название треугольник Фон - Неймана. В Фон-Неймановой архитектуре ЭВМ должны включаться блоки:

1)ЦП - объединяющий в себе устройство управления и арифметико-логическое устройство.

2) ЗУ - запоминающее устройство - память.

3)УВВ - устройство ввода и вывода.

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

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

Устройства ввода:Клавиатура (алф.цифр.),мышь, сканер, джойстик, микрофон.

Устройства вывода:Монитор, принтер, графопостроитель, звука.

Классификация памяти:постоянная и оперативная.

В процессоре объединены два устройства - управления - для считывания команд данных из памяти и общей координации команд и АЛУ - для простейших логических и арифметических операций.

Регистры специального назначения и регистры общего назначения.

РОН предназначены для общего назначения логических и арифметических операций. РСН - в их состав входят регистр - счетчик команд; регистр состояния программы; регистр указателя стека. Счетчик команд хранит адрес следующей команды; состояние программы - обязательно включает в себя флаги, характеризующие результат выполнения последней программы, флаг Z - ,бит равный 1, если результат 0, и 0 если результат другой, флаг N - если результат отрицательный, флаг С 1 если был перенос из старшего разряда. Флаги используются для выполнения условных операций. Регистр стека - хранит адрес вершины стека. Стек - область памяти, доступ к которой осуществляется по принципу LIFO.

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

Существует группа операций.

Команда пересылки.

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

Например:

a = b;

В общем случае после трансляции будет получена команда mov, в которой в качестве операндов будет указан адрес переменной a и адрес переменной b. Если для переменных a и b будет выбран класс памяти регистровый, то при наличии свободных регистров общего назначения, в команде mov будут указаны регистры. Таким образом используется прямая адресация, либо непосредственная. Если мы присваиваем значение целой константы третьему элементу массива М:

М[3]=4;

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

Команды перехода.

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

Фактически осуществляется команда пересылки адреса команды в

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

Арифметические операции.

1. "+"- выполняется код целым числом в прямом коде.

2. "-"- реализуется как сложение уменьшаемого с вычитаемым, которое представляется в дополнительном коде.

3. Умножение выполняется как комбинация сложений и сдвигов.

4. Деление- комбинация вычитаний и сдвигов с определением частного и остатка.

5. Операции над числами с плавающей точкой.

6. Операции над действительными числами выполняются в зависимости от форм представления (с фиксированной или с плавающей точкой).

7. Выполняется в виде совокупности операций или над мантиссой и характеристикой числа.

Логические операции.

Команда сравнения СМР- представляет собой выполнение арифметической операции вычитание без сохранения разности, но с установкой флагов регистров состояния программы. Если ab, то к а будет приписан b в дополнительном коде, а результат никуда перемещен не будет.

Условный переход на команду пересылки и безусловный переход на команду следующей за первой командой пересылки.

Логические операции реализуются непосредственно аппаратной частью.

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

Понятие об элементарном исполнителе.

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