Истоки регулярных выражений лежат в теории автоматов, теории формальных языков и классификации формальных грамматик по Хомскому.
Эти области изучают вычислительные модели (автоматы) и способы описания и
классификации формальных языков. В 1940-х гг. Уоррен Маккалок и Уолтер Питтс описали нейронную систему, используя простой автомат в качестве модели нейрона.
Математик Стивен Клини позже описал эти модели, используя свою систему математических обозначений, названную «регулярные множества».
Кен Томпсон встроил их в редактор QED, а затем в редактор ed под UNIX. С этого времени регулярные выражения стали широко использоваться в UNIX и UNIX-подобных утилитах, например в expr, awk, Emacs, vi, lex и Perl.
Регулярные выражения в Perl и Tcl происходят от реализации, написанной Генри Спенсером. Филип Хейзел разработал библиотеку PCRE (англ. Perl-compatible regular expressions — Perl-совместимые регулярные выражения), которая используется во многих современных инструментах, таких как PHP и Apache.
Эти области изучают вычислительные модели (автоматы) и способы описания и
классификации формальных языков. В 1940-х гг. Уоррен Маккалок и Уолтер Питтс описали нейронную систему, используя простой автомат в качестве модели нейрона.
Математик Стивен Клини позже описал эти модели, используя свою систему математических обозначений, названную «регулярные множества».
Кен Томпсон встроил их в редактор QED, а затем в редактор ed под UNIX. С этого времени регулярные выражения стали широко использоваться в UNIX и UNIX-подобных утилитах, например в expr, awk, Emacs, vi, lex и Perl.
Регулярные выражения в Perl и Tcl происходят от реализации, написанной Генри Спенсером. Филип Хейзел разработал библиотеку PCRE (англ. Perl-compatible regular expressions — Perl-совместимые регулярные выражения), которая используется во многих современных инструментах, таких как PHP и Apache.
Forwarded from Книги для программистов
Д.Бейдер - Чистый Python - 2018.pdf
6.9 MB
Чистый Python, Бейдер Д.О. (2018)
Теория графов представляет собой один из наиболее важных и интересных, но в то же время один из самых сложных и непонятных разделов в информатике.
Понимание и использование графов делает нас более квалифицированными специалистами. По крайней мере, так должно быть. Граф – это множество вершин V и множество рёбер E, содержащих упорядоченную пару G=(V, E).
Пытаясь изучать теорию графов и реализовать некоторые алгоритмы, многие программисты просто прекращают этим заниматься, потому что считают данное занятие слишком скучным.
Лучший способ освоить что-то – понять, как и где оно применяется. В этой статье мы покажем различные примеры применения теории графов, проиллюстрировав каждый из них.
Пусть эта статья покажется слишком детальной для опытных программистов, но, поверьте, подробные объяснения гораздо эффективнее сжатых определений.
Понимание и использование графов делает нас более квалифицированными специалистами. По крайней мере, так должно быть. Граф – это множество вершин V и множество рёбер E, содержащих упорядоченную пару G=(V, E).
Пытаясь изучать теорию графов и реализовать некоторые алгоритмы, многие программисты просто прекращают этим заниматься, потому что считают данное занятие слишком скучным.
Лучший способ освоить что-то – понять, как и где оно применяется. В этой статье мы покажем различные примеры применения теории графов, проиллюстрировав каждый из них.
Пусть эта статья покажется слишком детальной для опытных программистов, но, поверьте, подробные объяснения гораздо эффективнее сжатых определений.
Семь мостов Кёнигсберга
Начнём с того, с чем чаще всего сталкивается программист, читающий книгу про теорию графов – история про мосты и островы Калининграда. В Калининграде было семь мостов, соединяющих два больших острова, окруженных рекой Преголя, и две части материка, разделенные той же рекой.
Начнём с того, с чем чаще всего сталкивается программист, читающий книгу про теорию графов – история про мосты и островы Калининграда. В Калининграде было семь мостов, соединяющих два больших острова, окруженных рекой Преголя, и две части материка, разделенные той же рекой.
В 18 веке это был Кёнигсберг, город Пруссии, и на этой территории было гораздо больше мостов. Задача или просто головоломка состояла в том, что необходимо было найти такой маршрут, который проходил через каждый мост ровно один раз. Вот иллюстрированный вид семи мостов Кёнигсберга в 18 веке:
Попробуйте решить эту головоломку. Посмотрите, сможете ли вы пройти по всем мостам ровно один раз.
Непосещённых мостов быть не должно.
Пройти по мосту можно только один раз.
Если вы знакомы с этой задачей, то знаете, что это невозможно. Даже если вы очень сильно пытались, в конечном итоге вам пришлось сдаться.
Непосещённых мостов быть не должно.
Пройти по мосту можно только один раз.
Если вы знакомы с этой задачей, то знаете, что это невозможно. Даже если вы очень сильно пытались, в конечном итоге вам пришлось сдаться.
Есть четыре разных места: два острова и две части материка. И семь мостов. Интересно узнать, существует ли какая-либо закономерность в отношении количества мостов, связанных с островами или материком (мы будем использовать термин “земля” для обозначения четырех различных мест)?
На первый взгляд кажется, что это похоже на какой-то шаблон. Есть нечётное количество мостов, связанных с каждой землёй. Если нужно пересечь каждый мост один раз, то вам достаточно зайти на землю и сойти с неё, если она имеет два моста.
На рисунке выше видно, что если вы заходите на землю, проходясь по одному мосту, вы всегда можете покинуть землю, пройдя по её второму мосту. Всякий раз, когда появляется третий мост, вы не сможете покинуть землю, как только войдёте в нее.
Если вы попытаетесь обобщить это рассуждение для одного участка земли, то увидите, что в случае чётного количества мостов всегда можно покинуть землю, а в случае нечётного – нет.
На рисунке выше видно, что если вы заходите на землю, проходясь по одному мосту, вы всегда можете покинуть землю, пройдя по её второму мосту. Всякий раз, когда появляется третий мост, вы не сможете покинуть землю, как только войдёте в нее.
Если вы попытаетесь обобщить это рассуждение для одного участка земли, то увидите, что в случае чётного количества мостов всегда можно покинуть землю, а в случае нечётного – нет.
Изменим условие
Давайте добавим новый мост, чтобы узнать, как изменится количество общих соединённых мостов, и решит ли он проблему:
Давайте добавим новый мост, чтобы узнать, как изменится количество общих соединённых мостов, и решит ли он проблему:
Теперь, когда у нас есть два четных (4 и 4) и два нечетных (3 и 5) числа мостов, соединяющих четыре части земли, давайте нарисуем новый маршрут с добавлением этого нового моста.
Forwarded from Книги для программистов
Джоши_П_Искусственный_интеллект.pdf
69.6 MB
Искусственный интеллект с примерами на Python
Автор книги: Джоши П.
Год издания: 2019
Автор книги: Джоши П.
Год издания: 2019
Переходим к графам
Мы увидели, что число чётных и нечётных мостов сыграло свою роль в определении возможного решения. Возникает вопрос. Количество мостов решает проблему? И должно ли это работать во всех случаях? Оказывается, это не так. Вот что сделал Эйлер. Он нашёл способ показать, что количество мостов имеет значение. Что более интересно, также имеет значение количество участков земли с нечётным количеством соединённых мостов. Именно тогда Эйлер начал преобразовывать земли и мосты в то, что мы знаем как графы. Вот как может выглядеть граф этой задачи (обратите внимание, что временно добавленного моста нет).
Мы увидели, что число чётных и нечётных мостов сыграло свою роль в определении возможного решения. Возникает вопрос. Количество мостов решает проблему? И должно ли это работать во всех случаях? Оказывается, это не так. Вот что сделал Эйлер. Он нашёл способ показать, что количество мостов имеет значение. Что более интересно, также имеет значение количество участков земли с нечётным количеством соединённых мостов. Именно тогда Эйлер начал преобразовывать земли и мосты в то, что мы знаем как графы. Вот как может выглядеть граф этой задачи (обратите внимание, что временно добавленного моста нет).