Маркс - Философия

  • 17 янв. 2013 г.
  • 2815 Слова
Билет №1.
Понятие алгоритма является фундаментальной категорией математики и не может быть выражено через другие, более простые понятия, а рассматривается как нечто неопределяемое. Другими словами, единого определения алгоритма не существует, есть только разные подходы, описания этого понятия, причем, в полном соответствии с той областью знаний, где он применяется. Опишем понятие алгоритма,например, так:
Алгоритм - это строгая, четкая последовательность математических и логических операций, приводящая к решению задачи.
В Толковом словаре по информатике (1991г.) дано общепринятое понятие: алгоритм - точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату.
Описание основных свойств помогает углубить само понятие алгоритма. Итак,алгоритм должен обладать следующими свойствами:
Детерминированность (определенность, точность, однозначность). Это свойство заключается в том, что при задании одних и тех же исходных данных несколько раз алгоритм будет выполняться абсолютно одинаково и всегда будет получен один и тот же результат. Свойство детерминированности проявляется также и в том, что на каждом шаге выполнения алгоритмавсегда точно известно, что делать дальше, а каждое действие однозначно понятно исполнителю и не может быть истолковано неопределенно. Благодаря этому свойству выполнение алгоритма носит механический характер.
Массовость - выражается в том, что с помощью алгоритма можно решать не одну конкретную задачу, а любую задачу из некоторого класса однотипных задач при всех допустимых значениях исходныхданных.
Результативность (направленность) - означает, что выполнение алгоритма обязательно должно привести к решению поставленной задачи, либо к сообщению о том, что при заданных исходных величинах задачу решить невозможно. Алгоритмический процесс не может обрываться безрезультатно.
Дискретность - означает, что алгоритм состоит из последовательности отдельных шагов - элементарныхдействий, выполнение которых не представляет сложности. Именно благодаря этому свойству алгоритм может быть реализован на ЭВМ.
Конечность (финитность)- заключается в том, что последовательность элементарных действий алгоритма не может быть бесконечной, неограниченной, хотя может быть очень большой (если требуется, например, большая точность вычислений).
Корректность - означает, что если алгоритм создандля решения определенной задачи, то для всех исходных данных он должен всегда давать правильный результат и ни для каких исходных данных не будет получен неправильный результат. Если хотя бы один из полученных результатов противоречит хотя бы одному из ранее установленных и получивших признание фактов, алгоритм нельзя признать корректным.
Если разработанная Вами последовательность действий необладает хотя бы одним из перечисленных выше свойств, то она не может считаться алгоритмом
Вычислительная сложность алгоритма — это функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от размера входных данных.
Время, затраченное на реализацию алгоритма, как функция размерности задачи называется временной сложностью алгоритма и обозначается как O[fA(n)].
Временнаясложность алгоритма - это функция от длины записи набора входных данных задачи, определяемая по аналогии с временной сложностью машины Тьюринга. Отличия заключаются в следующем. Вместо шага работы машины должна фигурировать элементарная операция.
Полиномиальная и экспоненциальная сложность.
Асимптотическая нотация:
В случае, когда необходимо определить только асимптотическую
верхнюю границу, используютO-обозначения.

Для определения асимптотическую нижней границы есть Ω-обозначение.

Для точной оценки используется Ѳ - обозначение. Его можно ввести
несколькими способами.

Билет № 2
PDF Рекуррентные отношения

Билет №3
«Разделяй и властвуй». Если проблема элементарна, то сразу решаем её. Если нет, то делим её на более мелкие «под-проблемы» и выполняем это до...
tracking img