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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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