Основные конструкции языков программирования

Структурный подход и разработка алгоритма

Базовые конструкции для представления алгоритмов

Понятие оптимизации алгоритма. Классы сложности задач

Современные компьютеры эффективно решают задачи, число шагов в алгоритме которых растет в постоянной степени, например п² или п^2,5, где п – размер входных данных.

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

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

Класс NP («недетерминированное полиномиальное время») – задачи, для которых решение, если оно будет предложено, может быть проверено за полиномиальное время, даже если найти само решение – очень сложная задача.

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

Очевидно, что все задачи класса P входят так же в класс NP, т.к. на проверку правильности каждой уходит не больше времени, чем на ее решение.

BQP – класс задач, эффективно решаемых с помощью квантовых компьютеров.

В класс BQP входят все P- и немногие NP-задачи, в частности задача о разложении на множители.

Класс PS PACE содержит все задачи NP.

1. следование,

2. ветвление,

3. цикл.

Существуют два подхода:

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

2) снизу вверх (сборка вспомогательных алгоритмов в нужные комбинации; использование готовых алгоритмов).

		Алгоритм + структура данных = программы

Рис. 8. Данные динамической структуры

АРИФМЕТИЧЕСКИХ ТИПОВ

СИМВОЛЬНОГО ТИПА

УКАЗАТЕЛЬНОГО (ССЫЛОЧНОГО) ТИПА

БУЛЕВСКОГО (ЛОГИЧЕСКОГО) ТИПА

ДЕЙСТВИТЕЛЬНАЯ И МНИМАЯ ЧАСТЬ – НАТУРАЛЬНЫЕ ЧИСЛА

ДЕЙСТВИТЕЛЬНАЯ И МНИМАЯ ЧАСТЬ – ЦЕЛЫЕ ЧИСЛА  

ДЕЙСТВИТЕЛЬНАЯ И МНИМАЯ ЧАСТЬ – ВЕЩЕСТВЕННЫЕ ЧИСЛА  

КОМПЛЕКСНЫХ ЧИСЕЛ

С ПЛАВАЮЩЕЙ ТОЧКОЙ

С ФИКСИРОВАННОЙ ТОЧКОЙ

ВЕЩЕСТВЕННЫХ ЧИСЕЛ

ЦЕЛЫХ ЧИСЕЛ

НАТУРАЛЬНЫХ ЧИСЕЛ

СТАНДАРТНЫХ ТИПОВ

ДАННЫЕ ТИПОВ, ОПРЕДЕЛЕННЫХ ПРОГРАММИСТОМ

Рис. 9. Данные статистической структуры. Простые (скалярные)

Рис. 10. Данные статистической структуры. Составные (агрегативные)

10.10.Концепция языка

Внешнее различие языков составляют: грамматика, синтаксис и семантика.

Грамматика – строй языка, образующий вместе с фонетикой и лексикой целостную систему.

Синтаксис изучает правило создания речевых единиц.

Семантика – правила истолкования текста.

Метаязыки:

I. БНФ – компактная форма в виде некоторых формул, похожих на математические.

Левая часть – определенное понятие.

Правая – множество допустимых конструкций языка, которые объединены в это понятие.

Метасимволы БНФ:

1)угловые скобки < > (используются только вместе),

2)::= - «по определению есть»,

3) | «или» (объединяющее или),

4)- данное вхождение (или вхождение в данную формулу).

II. Диаграмма Вирта – графическое представление.

Дата добавления: 2014-01-20