Бендерский Педагогический Колледж — часть 2.


Учебная работа Учебную работу возглавляет заместитель директора по учебной работе — Оболоник Екатерина Федоровна, отличник народного образования ПМР, руководитель высшей квалификационной категории, преподаватель естественных дисциплин, высшей квалификационной категории.

Введение в теорию автоматов, языков и вычислений. Глава 11.


ГЛАВА 11 Дополнительные классы проблем Труднорешаемые проблемы не ограничиваются классом MP. Существует много других классов труднорешаемых проблем, по разным причинам представляющих интерес. Не­которые вопросы, связанные с этими классами, вроде V = MP, остаются нерешенными. Дж.Хопкрофт — Введение в теорию автоматов. Глава 1-2 Дж.Хопкрофт — Введение в теорию автоматов. Глава 3-5 Дж.Хопкрофт — Введение в теорию Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 10.


ГЛАВА 10 Труднорешаемые проблемы Обсуждение вычислимости переносится на уровень ее эффективности или неэффектив­ности. Предметом изучения становятся разрешимые проблемы, и нас интересует, какие из них можно решить на машинах Тьюринга за время, полиномиально зависящее от раз­мера входных данных. Напомним два важных факта из раздела 8.6.3.

Введение в теорию автоматов, языков и вычислений. Глава 9.


ГЛАВА 9 Неразрешимость Эта глава начинается повторением рассуждений из раздела 8.1, которые неформально обосновывали существование проблем, не разрешимых с помощью компьютера. Недос­татком тех «правдоподобных рассуждений» было вынужденное пренебрежение реаль­ными ограничениями, возникающими при реализации языка С (или другого языка про­граммирования) на любом реальном компьютере. Однако эти ограничения, вроде конеч­ности адресного пространства, не являются фундаментальными. Наоборот, с Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 8.


ГЛАВА 8. Введение в теорию машин Тьюринга В этой главе направление наших усилий меняется. До сих пор нас интересовали в основ­ном простые классы языков и пути их использования для относительно ограниченных задач, вроде анализа протоколов, поиска в текстах или синтаксического анализа. Теперь начнется исследование языков, которые вообще можно определить с помощью вычисли­тельных устройств. Это равносильно изучению Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 7.


ГЛАВА 7 Свойства контекстно- свободных языков Наше изучение контекстно-свободных языков завершается знакомством с некоторыми из их свойств. Вначале определяются ограничения на структуру продукций КС-грамматик и доказывается, что всякий КС-язык имеет грамматику специального вида. Этот факт об­легчает доказательство утверждений о КС-языках.

Введение в теорию автоматов, языков и вычислений. Глава 6.


ГЛАВА 6 Автоматы с магазинной памятью Контекстно-свободные языки задаются автоматами определенного типа. Такой автомат называется автоматом с магазинной памятью, или магазинным автоматом, и является расширением недетерминированного конечного автомата с f-переходами, представляю­щего собой один из способов определения регулярных языков. Магазинный автомат — это, по существу, е-НКА с добавлением магазина. Магазин может читаться, в его верши­ну могут Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 5.


ГЛАВА 5 Контекстно-свободные грамматики и языки Перейдем от рассмотрения регулярных языков к более широкому классу языков, которые называются контекстно-свободными. Они имеют естественное рекурсивное описание в ви­де контекстно-свободных грамматик. Эти грамматики играют главную роль в технологии компиляции с начала 1960-х годов; они превратили непростую задачу реализации синтак­сических анализаторов, распознающих структуру программы, из неформальной в рутин­ную, которую можно решить Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 4.


ГЛАВА 4 Свойства регулярных языков В этой главе рассматриваются свойства регулярных языков. В разделе 4.1 предлагается инструмент для доказательства нерегулярности некоторых языков — теорема, которая называется «леммой о накачке» («pumping lemma»).

Введение в теорию автоматов, языков и вычислений. Глава 3.


ГЛАВА 3 Регулярные выражения и языки В этой главе вводится система записи «регулярных выражений». Такие выражения пред­ставляют собой еще один способ определения языков, рассмотренный вкратце в разде­ле 1.1.2. Регулярные выражения можно рассматривать также как «язык программирова­ния» для описания некоторых важных приложений, например, программ текстового поиска или компонентов компилятора. Регулярные выражения тесно связаны с НКА и Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 2.


ГЛАВА 2 Конечные автоматы В этой главе мы введем класс языков, известных как «регулярные». Это языки, которые могут быть описаны конечными автоматами. Последние мы уже обсудили вкратце в разделе 1.1.1. Перед тем как формально определить конечные автоматы, рассмотрим развернутый пример, из которого станет ясной мотивация последующего изучения этих объектов.

Введение в теорию автоматов, языков и вычислений. Глава 1.


Предисловие В предисловии к своей книге 1979 года, предшествовавшей данному изданию, Дж. Хопкрофт и Дж. Ульман с удивлением отмечали, что за время, прошедшее после выхода их первой книги в 1969 году, произошел взрыв в развитии теории автоматов. Действительно, книга, вышедшая в 1979 году, содержала множество тем, не затронутых в предыдущей работе, и по объему была Читать далее

Введение в теорию автоматов, языков и вычислений


2-Е ИЗДАНИЕ. ДЖОН ХОПКРОФТ РАДЖИВ МОТВАНИ ДЖЕФФРИ УЛЬМАН. Перевод с английского О. И. Васылык, М. Саит-Аметова, канд.физ.-мат.наук А.Б. Ставровского Под редакцией канд.физ.-мат.наук А. Б. Ставровского Книга известных американских ученых посвящена теории автоматов и соответст¬вующих формальных языков и грамматик — как регулярных, так и контекстно- свободных. Во второй части рассматриваются различные машины Тьюринга, при помо¬щи которых формализуются Читать далее

Баранов. Введение в теорию автоматов.


Глава третья КОДИРОВАНИЕ СОСТОЯНИЙ АВТОМАТА 3-1. Гонки в автомате Как уже отмечалось во второй главе, задача кодирования состоя­ний является одной из основных задач канонического метода струк­турного синтеза автоматов. Напомним, что кодирование заключается в сопоставлении с каждым состоянием автомата набора состояний эле­ментарных автоматов памяти одинаковой длины I (в данном параграфе для простоты ограничимся использованием в качестве Читать далее

Выхованец В.С. Сборник задач по теории автоматов.


Выхованец В.С. Сборник задач по теории автоматов Учебное пособие для вузов. Оглавление ПРЕДИСЛОВИЕ…………………………………………………………………………………………………………………………………………………….. 2 Раздел 1. Формальные языки и грамматики…………………………………………………………………………………. 3 СКАЧАТЬ! Выхованец В.С. Теория автоматов Учеб. пособие для вузов Выхованец В.С. Теория автоматов/

Как рассматривать этот сайт


Что такое вычислительный центр, какие бывают компьютеры, как они устроены, почему учат работать с компьютером в школе – обо всем этом и многом другом расскажет данный сайт. Красочные иллюстрации помогут понять и усвоить основные принципы работы компьютеров Как рассматривать этот сайт? Да, вообще-то его можно рассматривать, как и любой другой. Но можно и иначе. Этот Читать далее

Сто профессий компьютера


Когда наш предок впервые взял палку, чтобы сбить плод с дерева, он удлинил свою руку. Когда человек придумал рычаг, чтобы сдвинуть тяжелый камень, он увеличил свою физическую силу. Подзорная труба увеличила зоркость человека, а велосипед увеличил его скорость. Но человек на этом не остановился. Рычаг сменил мощный подъемный кран, подзорную трубу заменил телескоп, на смену Читать далее

Как компьютер появился на свет


«С голубого ручейка начинается река…» Компьютерная река тоже началась с «ручейка», точнее – с нескольких ручейков. Они нарисованы на картинке. Левый ручеек – это различные технические устройства, с помощью которых люди увеличивали скорость счета. Средний – машины и механизмы, где использовались принципы программирования. Справа собраны научные открытия, использовавшиеся потом при создании компьютеров. Слившись вместе, эти Читать далее

Что такое информация


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

Как устроен компьютер


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

Центральный процессор


Компьютер может многое: считать, писать, рисовать. Может говорить, исполнять музыку (Сто профессий компьютера.). Но все эти сложные действия обязательно дробятся на самые простые: сложение, вычитание, сравнение. И производит эти действия центральный процессор. Всё, что обрабатывает центральный процессор, поступает в него из оперативной памяти. В это «всё» входят как сами числа, которые нужно обрабатывать, так и Читать далее

Кладовые памяти


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

Дисплеи


Представь себе пишущую машинку. Только вместо листа бумаги – телеэкран. Нажал клавишу – и буква появилась на экране. Это и есть дисплей. Работать с дисплеем не труднее, чем с обыкновенной пишущей машинкой. Правда, клавиш побольше и есть еще дополнительные переключатели. Благодаря им каждая клавиша может дать не два символа, как на машинке, а четыре. Кроме Читать далее

Сколка, мышка и джойстик


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

Компьютер слушает и говорит


Ты уже знаешь, что клавиатура не единственное средство ввода информации в компьютер. Есть и сколка, и мышка… (Сколка, мышка и джойстик.). Но все это хорошо для ввода графической информации: чертежей, рисунков. А как быть с речью? И нужно ли это? Мысль о говорящем и слушающем компьютере владела учеными давно, почти с рождения вычислительных машин. Однако Читать далее

Типография на столе


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

Языки программирования


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

Операционные системы


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

Типы современных компьютеров


Таким должен быть автомобиль? А это смотря для чего его использовать. Если нужно перевозить тонны руды или песка, то лучше всего это делать на огромных КамАЗах и БелАЗах. Чтобы перевозить небольшие партии груза, берут «рафик» или УАЗ. Для личного пользования служат «Москвичи», «Жигули» и «Запорожцы». Так же обстоит дело и с компьютерами. Их выбор определяется Читать далее