Некоторые вопросы из группы 2.

Дайте развернутый ответ

01. Языки императивного программирования (на выбор Pascal, С++, Basic): типы данных, базовые конструкции (операторы), структура программы.

При ответе на данный вопрос должны быть рассмотрены: типы(целые, вещественные, символьные, логические, возможно абстрактные); массивы, 3 вида циклов(с пред условием, с пост условием и арифметические), операторы условного перехода( альтернатива – if, выбора – switch или case). Организация подпрограмм, структура программы.

02. Понятие алгоритма и его свойства.

Единого «истинного» определения понятия «алгоритм» нет. В технических системах пользуются определениями:

«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)

«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)

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

«Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)

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

Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

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

• Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.

• Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.

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

• Массовость — универсальность. Алгоритм должен быть применим к разным наборам исходных данных.

• Результативность — завершение алгоритма определёнными результатами.

• Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.

• Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных

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

Интуитивное понятие алгоритма. Интуитивное понятие алгоритма рисует нам его как строго сформулированное правило, следуя которому можно осуществить процесс решения задачи, причем осуществить механически, максимально экономя усилия.

О п р е д е л е н и е. Алгоритм - это предписание, ведущее от исходных данных к искомому результату и обладающее свойствами: 1) определенности (общепонятности и точности); 2) массовости; 3) результативности.

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

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

ДАЛЕЕ ДЛЯ КРУТЫХ!!!!! ТЕОРИЯ АЛГОРИТМОВ!!!

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

Широкое формальное определение алгоритма. Мы знаем уже, что класс первичных алгоритмов задан, если заданы два языка: L₁ и L₂, причем предложения первого из них объявлены записями алгоритмов, а предложения второго - записями операндов и, если задано правило выполнения первичных алгоритмов, применимое к парам: запись алгоритма, запись операнда.

Первый пункт общего определения алгоритма гласит:

1) Первичные алгоритмы - это алгоритмы.

Но общее понятие алгоритма существенно шире. Его второй пункт гласит:

2) Если заданы два языка L₁ и L₂, причем предложения первого объявлены записями алгоритмов, а предложения второго - записями операндов, и если задан некоторый алгоритм W, операндами которого являются конструкции, получаемые связыванием каждого предложения из L₁ с n предложениями языка L₂ при помощи вполне определенной связи ранга n+1, то задано семейство n-местных алгоритмов.

Наконец, третий пункт общего определения гласит:

3) n-местные алгоритмы - тоже алгоритмы.

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

Одноместным называется n-местный алгоритм, для которого n=1. Первичные алгоритмы тоже будем называть одноместными.

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

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

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

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

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

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

Пусть L₂={} - алгоритмический язык, L₁={} - язык операндов, z - связь (n+1)-ого ранга и W - алгоритм выполнения. Обозначим через конструкцию, получаемую путем связывания языка L₂ и n предложений языка L₁. Тогда равенство означает, что t является алгоритмом и что . При этом - запись искомого результата.

Для каждого семейства алгоритмов, определяемого некоторым алгоритмом выполнения W, множество L₃={r} записей всех возможных искомых результатов является формальным языком. Таким образом, каждому семейству алгоритмов отвечает еще один формальный язык: язык искомых результатов. В частном случае он может быть подмножеством языка операндов.

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

О п р е д е л е н и е. Два алгоритма, которые имеют одинаковые записи и эквивалентны, являются одним и тем же алгоритмом (или экземплярами одного и того же алгоритма).

Теперь нетрудно уточнить приведенное выше общее определение алгоритма (вернее, дополнить его).

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