Александр Соловьев - ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ

Здесь есть возможность читать онлайн «Александр Соловьев - ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ» весь текст электронной книги совершенно бесплатно (целиком полную версию без сокращений). В некоторых случаях можно слушать аудио, скачать через торрент в формате fb2 и присутствует краткое содержание. Жанр: Математика, на русском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале библиотеки ЛибКат.

ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ: краткое содержание, описание и аннотация

Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.

ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ — читать онлайн бесплатно полную книгу (весь текст) целиком

Ниже представлен текст книги, разбитый по страницам. Система сохранения места последней прочитанной страницы, позволяет с удобством читать онлайн бесплатно книгу «ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ», без необходимости каждый раз заново искать на чём Вы остановились. Поставьте закладку, и сможете в любой момент перейти на страницу, на которой закончили чтение.

Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

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

Для того, чтобы грамматика относилась к типу КЗ достаточно, чтобы хотя бы одно правило было именно первого типа. (Остальные могут быть других типов, кроме нулевого).

Грамматики второго типа называют КОНТЕКСТНО-СВОБОДНЫМИ (или просто КС ). Каждое правило может применяться без оглядки на контекст. Вместо грязной тарелки – новая закуска (без всяких дополнительных условий)… Грамматики разных типов могут порождать один и тот же язык. Компиляторы диктуют требование приводить грамматику к типу КС . Обычно в рамках уже этого типа накладываются дополнительные ограничения, что позволяет существенно упростить грамматический разбор в компиляторе.

Грамматики последнего третьего типа называются АВТОМАТНЫМИ или РЕГУЛЯРНЫМИ . Это связано с тем, что они порождаются и распознаются автоматами (эту математическую модель ассоциируют не с Калашниковым, а с фамилиями математиков-логиков Мили Мура Трахтенбротта и т. п.) и регулярными выражениями (это, как и в регулярной армии – выражения строятся по простым правилам и просто распознаются – это тоже математическая модель).

Обычно автоматные грамматики используются на уровне лексики. Лексема, в обычном понимании – это словарная единица. Тем ни менее, с точки зрения компилятора это «символ», коль скоро «словом» будет вся программа. В данном случае, например, 345.08 может быть распознан как один символ – действительное число.

Лексический анализ в компиляторе предшествует синтаксическому анализу… Существуют знаменитые команды UNIX lex и yacc , который позволяют автоматизировать процесс написания лексического и синтаксического анализаторов компилятора.

Что– то мы очень уклонились в сторону программирования. Программирование -это тоже математика. Тоже дискретная. Но уже другая. И это другая история.

А из программирования уже, обычно, так просто не возвращаются…

Лекция 13. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ

Мало того, что есть алгоритмически неразрешимые задачи и их бесконечно больше, чем задач алгоритмически разрешимых. С практической точки зрения нам не легче, если решение разрешимой задачи мы сможем получим через миллион лет. Раньше не закончить расчеты… Это трудно-решаемые задачи. Для нас (простых смертных) такие задачи не отличаются от задач алгоритмически неразрешимых.

А ситуация с такими задачами еще более туманная, чем с алгоритмической разрешимостью. Пока единственный, фактически, «железный» аргумент нашей беспомощности, что задача относится к трудно-решаемым, что никто пока не нашел для нее легкого решения! Даже американские политики.

Ненормальность такой ситуации усугубится, если учесть, что теоретики рассматривают только конечные дискретные задачи (задачи либо на поиск оптимума, либо распознавания [да-нет]), любая из которых (теоретически) может быть решена хотя бы (за неимением лучшего) простым перебором. Но от этого не легче, если вспомнить легенду об изобретателе шахмат, который попросил в награду за первую клеточку шахматной доски одно зернышко, за вторую два… за 64-ю клеточку – 2 в 64-ой степени зернышек. Что превышает зерновые ресурсы Земного шара.

Одна из книг по сложности вычислений начиналась с цитаты из украинского философа Георгия Сковороды:" Спасибо тебе Господи, что ты создал все нужное нетрудным, а все трудное – ненужным." Но кажется, что здесь более точной будет другая мысль из Сковороды, а именно, эпитафия на его могиле: «Мир ловил меня, но не поймал»… И еще одна мысль более конкретная мысль уже от современных математиков: «Сложность становится проблемой века».

Из-за огромного количества несущественных особенностей различных способов (методов, парадигм) вычисления признаки, которые следовало бы учитывать при определении сложности вычислений слишком многочисленны и противоречивы. Но в конечном счете большинство сходится к тому, что все можно свести к времени (числу элементарных шагов) вычисления и объему памяти. Более того, многие так и видят при этом в качестве наилучших моделей – машины Тьюринга.

Проблему быстро свели к двум словам и их сочетанию.

Эти слова Polinomial – полиномиальный и Nondeterministic – недетерминированный .

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Похожие книги на «ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ»

Представляем Вашему вниманию похожие книги на «ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ» списком для выбора. Мы отобрали схожую по названию и смыслу литературу в надежде предоставить читателям больше вариантов отыскать новые, интересные, ещё непрочитанные произведения.


Отзывы о книге «ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ»

Обсуждение, отзывы о книге «ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ» и просто собственные мнения читателей. Оставьте ваши комментарии, напишите, что Вы думаете о произведении, его смысле или главных героях. Укажите что конкретно понравилось, а что нет, и почему Вы так считаете.

x