Что представляет собой матрица?

Матрица - это двумерный массив, каждый элемент которого имеет два индекса: номер строки - i; номер столбца - j.

37. В чем заключается работа с элементами матрицы?

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

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

1 алг) Обнуляется ячейка для накапливания суммы (переменная S). Затем с помощью двух циклов (первый по строкам, второй по столбцам) просматривается каждый элемент матрицы, но суммирование происходит только в том случае если, этот элемент находится выше главной диагонали, то есть выполняется свойство i < j.

2 алг) Проверка условия i<j не выполняется, но, тем не менее, в нем так же суммируются элементы матрицы, находящиеся выше главной диагонали. В первой строке заданной матрицы необходимо сложить все элементы, начиная со второго. Во второй - все, начиная с третьего, в i -й строке процесс начнется с (i+1) -го элемента и так далее. Таким образом, первый цикл работает от 1 до N, а второй от i+1 до M.

39. Что представляет собой машина Тьюринга?

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

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

40. Какие основные составляющие машины Тьюринга?

1) неограниченная в обе стороны лента, разделенная на ячейки;

2) автомат (головка для считывания/записи, управляемая программой).

40. В чем заключается работа машины Тьюринга?

С каждой машиной Тьюринга связаны два конечных алфавита: алфавит входных символов A = {a0, a1,..., am}и алфавит состояний Q = {q0, q1,..., qp}. Состояние q0 называется пассивным. Считается, что если машина попала в это состояние, то она закончила свою работу. Состояние q1 называется начальным. Находясь в этом состоянии, машина начинает свою работу. Входное слово размещается на ленте по одной букве в расположенных подряд ячейках. Слева и справа от входного слова находятся только пустые ячейки.

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

41. Что представляет собой машина Поста?

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

42. Из каких составляющих состоит машина Поста?

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

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

43. В чем заключается работа машины Поста?

В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Состояние ленты меняется в процессе работы машины. Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной ячейки ленты; говорят, что каретка обозревает одну ячейку. За единицу времени каретка может совершить одно из трех действий: стереть метку, поставить метку, совершить движение на соседнюю ячейку. Состояние машины Поста складывается из состояния ленты и положения каретки.

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

1. записать 1 (метку), перейти к i-й строке программы;

2. записать 0 (стереть метку), перейти к i-й строке программы;

3. сдвиг влево, перейти к i-й строке программы;

4. сдвиг вправо, перейти к i-й строке программы;

5. останов;

6. если 0, то перейти к i, иначе перейти к j.

44. Что представляет собой нормальный алгоритм Маркова?

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

45. Что изучает теория сложности вычислений?

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

46. Что называют классами сложности?

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

47. Какие задачи относятся к классу P?

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

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

48. Какие задачи относятся к классу NP?

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

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

49. В чем заключается равенство классов P и NP?

Если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить (используя некоторую вспомогательную информацию, называемую сертификатом), то верно ли, что и сам ответ (вместе с сертификатом) на этот вопрос можно быстро найти? Задачи первого типа относятся к классу NP, второго — классу P. (Т.е. можно ли все задачи, решение которых проверяется с полиномиальной сложностью, решить за полиномиальное время?)

Проблема равенства этих классов является одной из важнейших проблем теории алгоритмов.

Что представляет собой модель?

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

Что такое моделирование?

Процесс построения и использования модели называется моделированием.

Моделирование – это:

– построение моделей реально существующих объектов (предметов, явлений, процессов);

– замена реального объекта его подходящей копией;

– исследование объектов познания на их моделях.

Различают материальное и идеальное моделирование.

Какие различают методы моделирования?

Различают материальное и идеальное моделирование.

· Материальное (или физическое) моделирование – это экспериментальный метод. Реальному объекту ставится в соответствие его материальная копия – физическая модель (увеличенная или уменьшенная), допускающая исследование в лабораторных условиях.

· Идеальное моделирование – это теоретический метод. Реальный объект заменяется его знаковой, математической моделью (поэтому этот метод обычно называют математическим моделированием). Модель формируется в виде математических соотношений и проводится ее исследование – аналитическое или с применением вычислительной техники.

Что представляют собой численне методы?

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

Что такое вычислительных экперимент?

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

Какие этапы включает в себя вычислительный эксперимент?

Вычислительный эксперимент включает в себя следующие этапы.

1. Постановка задачи:

· словесная формулировка задачи;

· определение конечных целей решения.

2. Построение математической модели, т.е. математическая формулировка задачи.

3. Выбор численного метода для решения математической задачи.

4. Разработка алгоритма.

5. Программная реализация алгоритма.

6. Тестирование программы (отладка на тестовых задачах).

7. Проведение расчетов на реальных данных.

8. Анализ результатов.

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

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

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

Что являются источниками погрешности приближенного решения?

Источниками погрешности приближенного решения являются:

1) Несоответствие математической модели изучаемому реальному явлению; погрешность исходных данных.

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

3) погрешности округлений в арифметических операциях.

На какие группы можно разбить методы решения систем линейных уравнений?

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

Какие методы являются точными?

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

Какие методы относятся к точным?

К точным методам относятся, например, метод Крамера, метод Гаусса, метод квадратных корней.

Какие методы называются приближенными методами?

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

Какие методы относятся к приближенным?

К приближенным методам относятся метод простой итерации, метод Зейделя

В чем состоят итерационные методы?

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

Какая идея лежит в основе метода Гаусса?

В основе метода Гаусса лежит идея последовательного исключения неизвестных.

В чем заключаются итерационные методы?

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

В чем суть метода простой итерации решения систем линейных уравнений?

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

.

Расчётные формулы имеют следующий вид: ,

В чем заключается метод Зейделя?

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

Из каких этапов состоит приближенное нахождение изолированных действительных корней уравнения

Приближенное нахождение изолированных действительных корней уравнения (1) состоит из двух этапов:

1) отделение корней, т.е. отыскание достаточно малых промежутков , в каждом из которых содержится один и только один корень уравнения (1);

2) уточнение приближенных корней, т.е. вычисление их с заданной степенью точности.

Что подразумевает собой отделение корней?

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

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

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

Затем необходимо определить знаки функции в ряде промежуточных точек , выбор которых учитывает особенности функции . Если окажется, что , где , то, в силу теоремы 1, в интервале имеется корень уравнения (1). Далее тем или иным способом нужно убедиться, является ли этот корень единственным.

В чем состоит алгоритм метода половинного деления нахождения корня уравнения?

Алгоритм метода половинного деления нахождения корня уравнения состоит в следующем.

Полагаем a ₀ =a, b ₀ =b. Для нахождения корня уравнения, принадлежащего отрезку , делим этот отрезок пополам точкой c₀ = (a ₀ +b ₀)/2 и вычисляем значение функции в этой точке. Если , то является корнем уравнения и работа алгоритма закончена. Если , то выбираем ту из половин или , на концах которой функция имеет противоположные знаки. Другой отрезок, как не содержащий корня, отбрасываем и т.д.

Что представляет собой метод хорд?

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