Книга: Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман «Введение в теорию автоматов, языков и вычислений»
|
Книга ВВЕДЕНИЕ В ТЕОРИЮ АВТОМАТОВ, ЯЗЫКОВ И ВЫЧИСЛЕНИЙ известных американских ученых посвящена теории автоматов и соответствующих формальных языков и грамматик -как регулярных, так и контекстно-свободных. Во второй части рассматриваются различные машины Тьюринга, при помощи которых формализуются понятия разрешимых и неразрешимых проблем, а также определяются функции временной и емкостной оценки сложности алгоритмов. Изложение ведется строго, но доступно, и сопровождается многочисленными примерами, а также задачами для самостоятельного решения. Книга ВВЕДЕНИЕ В ТЕОРИЮ АВТОМАТОВ, ЯЗЫКОВ И ВЫЧИСЛЕНИЙ будет полезна читателям различных категорий - студентам, аспирантам, научным сотрудникам, преподавателям высших учебных заведений, а также всем, кто интересуется математическими основами современной вычислительной техники. Издательство: "Вильямс" (2015) Формат: 70x100/16, 528 стр.
ISBN: 978-5-8459-1969-4, 0-201-44124-1 Купить за 2151 руб на Озоне |
Другие книги автора:
| Книга | Описание | Год | Цена | Тип книги |
|---|---|---|---|---|
| Введение в теорию автоматов, языков и вычислений | Книга ВВЕДЕНИЕ В ТЕОРИЮ АВТОМАТОВ, ЯЗЫКОВ И ВЫЧИСЛЕНИЙ известных американских ученых посвящена теории… — Вильямс, (формат: 70x100/16, 528 стр.) Несерийные Подробнее... | бумажная книга |
Джон Хопкрофт
| Джон Эдвард Хопкрофт | |
| John Edward Hopcroft | |
| Дата рождения: | |
|---|---|
| Место рождения: | |
| Гражданство: | |
| Научная сфера: | |
| Место работы: | |
| Альма-матер: | |
| Награды и премии | |
| Сайт: | |
Джон Эдвард Хопкрофт (англ. John Edward Hopcroft, 7 октября 1939 года, Сиэтл, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга.
Содержание |
Биография
Хопкрофт получил в 1961 году степень бакалавра в университете Сиэтла, после чего перешёл в Стэнфордский университет и получил там звания мастера наук (1962) и доктора философии (1964). После трёхлетней работы доцентом в Принстонском университете, Хопкрофт начинает работать в Корнелльском университете, где с 1972 года имеет полную профессуру по прикладной математике и информатике.
Его исследовательская деятельность состоит из теоретических аспектов информатики, в частности анализа алгоритмов, теории автоматов и теории графов. Хопкрофт — соавтор нескольких книг о формальных языках и конечных автоматах.
Вместе с Ричардом Карпом Хопкрофт разработал в 1973 году алгоритм для нахождения максимального покрытия в биграфах, работающий за время 
. Кроме того, Роберт Тарьян и Джон Хопкрофт разработали алгоритм для нахождения ориентации рёбер в неориентированном графе с целью создания сильно связного графа. Оба алгоритма были названы в честь их изобретателей.
В 1986 году Хопкрофт и Тарьян были награждены премией Тьюринга за «фундаментальный вклад в разработку и анализ алгоритмов и структур данных».[1]
Награды
- 1986 — Премия Тьюринга
- 1990 — Honoris causa от университета Сиэтла
- 1994 — почётное членство в Ассоциации вычислительной техники
- 2005 — Мемориальная премия Гарри М. Гуда
См. также
- Алгоритм Хопкрофта—Тарьяна
- Алгоритм Хопкрофта—Карпа
Ссылки
- Сайт Хопкрофта при Корнелльском университете (англ.)
- Список публикаций (англ.)
Примечания
Источник: Джон Хопкрофт
См. также в других словарях:
Теория автоматов — Теория автоматов раздел дискретной математики, изучающий абстрактные автоматы вычислительные машины, представленные в виде математических моделей и задачи, которые они могут решать. Теория автоматов наиболее тесно связана с… … Википедия
Сведение (теория сложности вычислений) — У этого термина существуют и другие значения, см. Сведение. В теории сложности вычислений сведение преобразование одной задачи к другой. В общем случае, если у нас есть алгоритм, преобразующий экземпляры задачи в экземпляры задачи , которые … Википедия
Лемма о разрастании для контекстно-свободных языков — Лемма о разрастании для контексто свободных языков лемма, по аналогии с одноименной леммой для регулярных языков позволяющая относительно несложно доказывать, что данный язык не является контекстно свободным. Содержание 1 Формулировка 2… … Википедия
Диаграмма состояний (теория автоматов) — У этого термина существуют и другие значения, см. Диаграмма состояний. Диаграмма состояний ориентированный граф для конечного автомата, в котором вершины обозначают состояния дуги показывают переходы между двумя состояниями На практике… … Википедия
Машина Тьюринга — Художественное представление машины Тьюринга Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма … Википедия
Детерминированная машина Тьюринга — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия
