Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Некоторые необходимые определения и понятия.

Читайте также:
  1. A) Необходимые соглашения об эффективной связи между различными звеньями сети, реализованные в виде библиотек процедур, соответствующих уровню обработки сообщения
  2. I. ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ
  3. III. Разделы, изученные ранее и необходимые для данного занятия
  4. IV. Разделы, изученные ранее и необходимые для данного занятия (базисные знания)
  5. Q.1.3. Некоторые явления нелинейной оптики.
  6. VIII. Порядок определения безопасных расстояний
  7. XXXIV. ОПРЕДЕЛЕНИЯ

При сравнении скорости роста двух неотрицательных функций f(n) и g(n) удобно использовать следующие обозначения.

Говорят, что функция g(n) f(n)-ограничена, если g(n)£f(n). Если f(n) - полином, то функция g(n) называется полиномиально ограниченной, а если экспонента – экспоненциально ограниченной.

Будем говорить, что f(n)= O(g(n)), если существуют такие положительные константы c и N, что f(n)≤c g(n)для всех n>N.

В этой же ситуации можно использовать и обозначение g(n)=Ω(f(n)). Например, справедливы соотношения log2 n = O(n), n = Ω(log2 n), n = O(2n).

Будем говорить, что f(n)= o(g(n)), если .

Если f(n)= O(g(n) и O(f(n))= g(n), то это будем обозначать через f(n)=Θg(n).

Для числа x целые числа [x] и ]x[ - это целые части числа с недостатком и с избытком.

Опр. Алфавит A – это конечный или бесконечный набор символов: A={a1,a2,…,an,…}.

Опр. Слово – это конечный упорядоченный набор символов алфавита.

Выделяется специальное пустое слово (слово, не содержащее символов).

Пусть – множество всех слов в алфавите .

Опр. Язык L – это подмножество . ().

Опр. Конкатенация слов и .

.

Число сочетаний (без повторений) из n элементов по k элементов обозначим через . Число сочетаний с повторениями из n элементов по k элементов обозначим через .

Если не оговорено обратное, вместо log 2n будем писать log n.

Простой граф с множеством вершин V, |V|=n, и множеством ребер E, |E|=m, будем обозначать через G=(V,E). Ориентированность графа будет оговариваться отдельно.

 

Булевы переменные - это переменные, принимающие значения из множества B ={0,1}. Множество n-мерных векторов из нулей и единиц называется булевым кубом и обозначается B n. Очевидно, что число вершин этого куба равно2n.

Отображение f: B n® B называется булевой функцией. Число булевых функций от n переменных равно

Примеры известных булевых функций: конъюнкция (&), дизъюнкция (È), отрицание (Ø), импликация (®), сложение по модулю «два» (Å), эквивалентность () и пр.

Табличный способ задания функции представляет собой таблицу размером 2n x (n+1). В последнем столбце таблице записаны значения функции на каждом из 2n возможных наборах значений переменных. Сами эти наборы записаны в первых n клетках каждой строки.

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


Дата добавления: 2015-07-11; просмотров: 118 | Нарушение авторских прав


Читайте в этой же книге: Алгоритм | Нормальные алгорифмы Маркова (НАМ). | Одноленточная МТ | Недетерминированная МТ | Оракульная МТ | Равнодоступная адресная машина (РАМ) и некоторые другие подходы. | Кодировки входных данных. | О мерах сложности | Теоремы сравнения | Задача о кратчайшем (минимальном) остове (остовном дереве). |
<== предыдущая страница | следующая страница ==>
Введение| Задачи, алгоритмы

mybiblioteka.su - 2015-2024 год. (0.007 сек.)