Комбинаторный анализ. Теория графов

Публикуются оригинальные статьи, обзоры и краткие сообщения ученых ЮУрГУ, университетов и научно-исследовательских организаций России, посвященные актуальным вопросам математики, механики и физики.

"Учебник написан по материалам курса ""Дискретная математика"", который читается студентам младших курсов факультета компьютерных наук НИУ ВШЭ. Темы этого курса являются частью базовой математической культуры и необходимы будущим математикам, программистам и специалистам в области анализа данных, но не входят в традиционно сложившиеся курсы начального математического цикла (математический анализ, алгебра, линейная алгебра). В книге излагаются начальные сведения из перечислительной комбинаторики, теории графов, теории чисел, теории множеств, теории вероятностей, теории игр, теории вычислимости. Не претендуя на полноценный охват какой-либо из упомянутых теорий, учебник дает введение в эти области, с одной стороны, достаточное для студентов соответствующих специальностей, а с другой –– позволяющее читать специализированную литературу.

В журнале публикуются результаты фундаментальных и прикладных научных исследований отечественных и зарубежных ученых, включая студентов и аспирантов, в области дискретной математики и её приложений в криптографии, компьютерной безопасности, кибернетике, информатике, программировании, теории надежности, интеллектуальных системах. Включен в Перечень ВАК.

Рассмотрены задачи о потоках в сетях с нестандартной достижимостью. Показано, что классическое определение потока в сети не учитывает тот факт, что допустимыми на таких сетях являются не все пути. Введенные в работе определения позволяют корректно определить поток в таких сетях, максимальный поток и пропускную способность сетей с нестандартной достижимостью. Рассмотрено семейство сетей с барьерной достижимостью. Найден предел последовательности пропускных способностей семейства, когда высота барьеров неограниченно возрастает.

Рассмотрены комбинаторные вычисления, их основные операционные объекты: сочетания, перестановки, размещения и разбиения элементов конечных множеств и натуральных чисел.

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

Рассмотрена задача нахождения максимального потока в сетях специального вида. В таких сетях для каждой дуги меняется длительность прохождения по ней. Считаем длительности прохождения периодическими по времени. Показано, что для таких сетей не выполняется теорема Форда и Фалкерсона, согласно которой величина максимального потока равна пропускной способности минимального разреза. Предложены оценки величины максимального потока в сети с циклической зависимостью длительностей прохождения по дугам от времени. Разработан алгоритм нахождения максимального суммарного потока для рассматриваемых сетей.

Публикуются оригинальные статьи, обзоры и краткие сообщения ученых ЮУрГУ, университетов и научно-исследовательских организаций России, посвященные актуальным вопросам математики, механики и физики.

Публикуются статьи, обзоры и краткие сообщения ученых ЮУрГУ, вузов и научно-исследовательских организаций России, посвященные актуальным вопросам математического моделирования и программирования.

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

Граф-решетка имеет вершины в точках плоскости с неотрицательными целыми координатами. Из каждой вершины выходят две ориентированные дуги: горизонтальная и вертикальная в соседние вершины (правую и верхнюю). Вероятность перехода по каждой из дуг равна 1 2 . Рассмотрена задачи о случайных блужданиях по вершинам графа с ограниче- ниями на достижимость. Допустимыми на графе-решётке считаются только 2- и 3-пути. Под 2(3)-путем на графе решётке будем понимать путь, удовлетворяющий условию: его начальный и все внутренние максимальные по вложению подпути, состоящие только из вертикальных дуг, имеют длину, кратную 2 (3). Получена формула для количества таких путей, соединяющих заданные вершины графа-решётки, найдена вероятность попадания из одной вершины в другую по 2и 3-путям. Следствием последнего является комбинаторное тождество, использующее элементы треугольника Паскаля.

Публикуются оригинальные статьи, обзоры и краткие сообщения ученых ЮУрГУ, университетов и научно-исследовательских организаций России, посвященные актуальным вопросам математики, механики и физики.

В журнале публикуются результаты фундаментальных и прикладных научных исследований отечественных и зарубежных ученых, включая студентов и аспирантов, в области дискретной математики и её приложений в криптографии, компьютерной безопасности, кибернетике, информатике, программировании, теории надежности, интеллектуальных системах. Включен в Перечень ВАК.

В сборнике «Труды РФЯЦ-ВНИИЭФ» опубликованы результаты научных исследований, а также методических и проектно-конструкторских разработок в области прикладных задач теоретической физики, математического моделирования физических процессов, ядерной физики, физики ядерных реакторов, исследований по термоядерному синтезу, электрофизики, физики ускорителей, приборов и техники эксперимента, физики лазеров, гидродинамики, реологии, физики горения и взрыва, физической химии, экологии, материаловедения, безопасности, средств защиты от несанкционированных действий, электроники, радиотехники, оптоэлектроники.

В сборнике «Труды РФЯЦ-ВНИИЭФ» опубликованы результаты научных исследований, а также методических и проектно-конструкторских разработок в области прикладных задач теоретической физики, математического моделирования физических процессов, ядерной физики, физики ядерных реакторов, исследований по термоядерному синтезу, электрофизики, физики ускорителей, приборов и техники эксперимента, физики лазеров, гидродинамики, реологии, физики горения и взрыва, физической химии, экологии, материаловедения, безопасности, средств защиты от несанкционированных действий, электроники, радиотехники, оптоэлектроники.

Рассматриваются четыре комбинаторные задачи, параметризованные кратностью r элемента базового мультимножества: распределение индексов vp-монотонных перестановок, обобщенные перестановки Гесселя-Стенли и обобщенные частично упорядоченные множества Баклавского-Эдельмана, обобщенные числа Стирлинга и обобщенные частично упорядоченные множества разбиений, обобщенные статистики и обобщенные многочлены Эйлера. Для исследования этих задач привлекаются различные методы.

В сборнике «Труды РФЯЦ-ВНИИЭФ» опубликованы результаты научных исследований, а также методических и проектно-конструкторских разработок в области прикладных задач теоретической физики, математического моделирования физических процессов, ядерной физики, физики ядерных реакторов, исследований по термоядерному синтезу, электрофизики, физики ускорителей, приборов и техники эксперимента, физики лазеров, гидродинамики, реологии, физики горения и взрыва, физической химии, экологии, материаловедения, безопасности, средств защиты от несанкционированных действий, электроники, радиотехники, оптоэлектроники.

Публикуются оригинальные статьи, обзоры и краткие сообщения ученых ЮУрГУ, университетов и научно-исследовательских организаций России, посвященные актуальным вопросам математики, механики и физики.

Публикуются оригинальные статьи, обзоры и краткие сообщения ученых ЮУрГУ, университетов и научно-исследовательских организаций России, посвященные актуальным вопросам математики, механики и физики.

Рассматривается обобщенная формула Родрига, позволяющая определить некоторые важные семейства многочленов, используемые в комбинаторном анализе. Эта формула применяется для получения рекуррентных соотношений и производящих функций. В частности, с этих позиций исследуются обобщенные многочлены Эйлера и рассматриваются их свойства. Для комбинаторной интерпретации коэффициентов этих многочленов привлекаются обобщенные перестановки Гесселя-Стенли и корневые помеченные r-угольные кактусы. Также рассматриваются конечно-разностные и g-аналоги обобщенной формулы Родрига, с помощью которых, в частности, изучаются g-аналоги экспоненциальных многочленов и многочленов Эйлера, а также их свойства.

Публикуются оригинальные статьи, обзоры и краткие сообщения ученых ЮУрГУ, университетов и научно-исследовательских организаций России, посвященные актуальным вопросам математики, механики и физики.

Методические указания содержат краткий теоретический материал, необходимый для выполнения домашнего задания по курсу «Дискретная математика». Рассмотрены примеры решения задач, приведены задачи для самостоятельной работы.

Журнал физико-химического профиля. Адресован специалистам, работающим в области квантовой химии, физических методов исследования, кристаллохимии, супрамолекулярной химии, структуры и свойств наноматериалов, строения жидкостей, а также широкому кругу химиков. Своеобразие журнала заключается в том, что для исследования электронного и пространственного строения химических соединений в публикуемых работах широко применяются современные физические методы, оригинальные теоретические и экспериментальные подходы. Форма публикаций - статьи, краткие сообщения, тематические обзоры по различным проблемам структурной химии. С 2004 г. Издаётся ежегодное Приложение к Журналу, в котором публикуются статьи по актуальным направлениям структурной химии. Журнал переводится на английский язык, издается и распространяется за рубежом Издательством Springer. Название англоязычного издания Journal of Structural Chemistry.

В сборнике «Труды РФЯЦ-ВНИИЭФ» опубликованы результаты научных исследований, а также методических и проектно-конструкторских разработок в области прикладных задач теоретической физики, математического моделирования физических процессов, ядерной физики, физики ядерных реакторов, исследований по термоядерному синтезу, электрофизики, физики ускорителей, приборов и техники эксперимента, физики лазеров, гидродинамики, реологии, физики горения и взрыва, физической химии, экологии, материаловедения, безопасности, средств защиты от несанкционированных действий, электроники, радиотехники, оптоэлектроники.

Публикуются статьи, обзоры и краткие сообщения ученых ЮУрГУ, вузов и научно-исследовательских организаций России, посвященные актуальным вопросам математического моделирования и программирования.

В сборнике «Труды РФЯЦ-ВНИИЭФ» опубликованы результаты научных исследований, а также методических и проектно-конструкторских разработок в области прикладных задач теоретической физики, математического моделирования физических процессов, ядерной физики, физики ядерных реакторов, исследований по термоядерному синтезу, электрофизики, физики ускорителей, приборов и техники эксперимента, физики лазеров, гидродинамики, реологии, физики горения и взрыва, физической химии, экологии, материаловедения, безопасности, средств защиты от несанкционированных действий, электроники, радиотехники, оптоэлектроники.

Журнал "Системы анализа и обработки данных" (до 2021г назывался "Научный вестник НГТУ") основан в 1995 году на базе Новосибирского государственного технического университета. Печатная версия журнала зарегистрирована в Министерстве РФ по делам печати, телевещания и средств массовых коммуникаций в 2000 году. Свидетельство о регистрации ПИ № ФС77-76010 от 03.07.2019 г. Периодичность выхода издания - раз в три месяца (4 номера в год). Научно-технические статьи, направленные в адрес журнала, проходят рецензирование и редактирование. Публикация статей бесплатная. В журнале "Системы анализа и обработки данных" (до 2021г назывался "Научный вестник НГТУ") публикуются оригинальные статьи по следующим группам специальностей: 05.13.00 - Информатика, вычислительная техника и управление (05.13.01; 05.13.11; 05.13.17; 05.13.18), 05.11.00 - Приборостроение, метрология и информационно-измерительные приборы и системы (05.11.07; 05.11.16; 05.11.17). До 2021 года журнал назывался "Научный вестник Новосибирского государственного технического университета".

Учебник предназначен для изучения алгебры и начал математического анализа в 11 классе общеобразовательных организаций. В нём предусмотрена уровневая дифференциация, позволяющая формировать у школьников познавательный интерес к алгебре и началам математического анализа. Учебник соответствует Федеральному государственному образовательному стандарту среднего общего образования.

Публикуются оригинальные статьи, обзоры и краткие сообщения ученых ЮУрГУ, университетов и научно-исследовательских организаций России, посвященные актуальным вопросам математики, механики и физики.

Публикуются статьи, обзоры и краткие сообщения ученых ЮУрГУ, вузов и научно-исследовательских организаций России, посвященные актуальным вопросам математического моделирования и программирования.

Рассмотрены основные понятия, используемые для описания работы блочных шифров, примеры типовых узлов, входящих в их конструкцию, а также наиболее распространенные схемы построения блочных шифров. Для большинства вводимых терминов приведены соответствующие англоязычные эквиваленты.

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

Публикуются статьи, обзоры и краткие сообщения ученых ЮУрГУ, вузов и научно-исследовательских организаций России, посвященные актуальным вопросам математического моделирования и программирования.

Публикуются оригинальные статьи, обзоры и краткие сообщения ученых ЮУрГУ, университетов и научно-исследовательских организаций России, посвященные актуальным вопросам математики, механики и физики.

В девятнадцатом выпуске серии «Математика в техническом университете» изложены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классические понятия теории булевых функций, а также основы теории формальных языков, куда включены теории конечных автоматов, регулярных языков, контекстно-свободных языков и магазинных автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методом. Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н.Э. Баумана.

Журнал "Системы анализа и обработки данных" (до 2021г назывался "Научный вестник НГТУ") основан в 1995 году на базе Новосибирского государственного технического университета. Печатная версия журнала зарегистрирована в Министерстве РФ по делам печати, телевещания и средств массовых коммуникаций в 2000 году. Свидетельство о регистрации ПИ № ФС77-76010 от 03.07.2019 г. Периодичность выхода издания - раз в три месяца (4 номера в год). Научно-технические статьи, направленные в адрес журнала, проходят рецензирование и редактирование. Публикация статей бесплатная. В журнале "Системы анализа и обработки данных" (до 2021г назывался "Научный вестник НГТУ") публикуются оригинальные статьи по следующим группам специальностей: 05.13.00 - Информатика, вычислительная техника и управление (05.13.01; 05.13.11; 05.13.17; 05.13.18), 05.11.00 - Приборостроение, метрология и информационно-измерительные приборы и системы (05.11.07; 05.11.16; 05.11.17). До 2021 года журнал назывался "Научный вестник Новосибирского государственного технического университета".

Публикуются оригинальные статьи, обзоры и краткие сообщения ученых ЮУрГУ, университетов и научно-исследовательских организаций России, посвященные актуальным вопросам математики, механики и физики.

Публикуются статьи, обзоры и краткие сообщения ученых ЮУрГУ, вузов и научно-исследовательских организаций России, посвященные актуальным вопросам математического моделирования и программирования.

В сборнике «Труды РФЯЦ-ВНИИЭФ» опубликованы результаты научных исследований, а также методических и проектно-конструкторских разработок в области прикладных задач теоретической физики, математического моделирования физических процессов, ядерной физики, физики ядерных реакторов, исследований по термоядерному синтезу, электрофизики, физики ускорителей, приборов и техники эксперимента, физики лазеров, гидродинамики, реологии, физики горения и взрыва, физической химии, экологии, материаловедения, безопасности, средств защиты от несанкционированных действий, электроники, радиотехники, оптоэлектроники.

Журнал физико-химического профиля. Адресован специалистам, работающим в области квантовой химии, физических методов исследования, кристаллохимии, супрамолекулярной химии, структуры и свойств наноматериалов, строения жидкостей, а также широкому кругу химиков. Своеобразие журнала заключается в том, что для исследования электронного и пространственного строения химических соединений в публикуемых работах широко применяются современные физические методы, оригинальные теоретические и экспериментальные подходы. Форма публикаций - статьи, краткие сообщения, тематические обзоры по различным проблемам структурной химии. С 2004 г. Издаётся ежегодное Приложение к Журналу, в котором публикуются статьи по актуальным направлениям структурной химии. Журнал переводится на английский язык, издается и распространяется за рубежом Издательством Springer. Название англоязычного издания Journal of Structural Chemistry.

Учебное пособие по курсу «Математические и алгоритмические основы построения интеллектуальных систем» (часть 1) совмещает в себе конспект лекций и практикум в части модуля «Использование графовых и гиперграфовых моделей в интеллектуальных системах» и отражает состояние современных аспектов теории графов и гиперграфов с элементами научной новизны, а также возможности их применения для решения реальных практических задач. Пособие содержит теоретический, практический и методический материал по темам: «Основные понятия теории графов», «Виды графов», «Алгоритмы на графах», «Использование графов в интеллектуальных системах», «Гиперграфы» и «Специальные графы в интеллектуальных системах». Каждая тема завершается заданиями для самостоятельной работы студентов и списком вопросов для самоконтроля.

В сборнике «Труды РФЯЦ-ВНИИЭФ» опубликованы результаты научных исследований, а также методических и проектно-конструкторских разработок в области прикладных задач теоретической физики, математического моделирования физических процессов, ядерной физики, физики ядерных реакторов, исследований по термоядерному синтезу, электрофизики, физики ускорителей, приборов и техники эксперимента, физики лазеров, гидродинамики, реологии, физики горения и взрыва, физической химии, экологии, материаловедения, безопасности, средств защиты от несанкционированных действий, электроники, радиотехники, оптоэлектроники.

Публикуются статьи, обзоры и краткие сообщения ученых ЮУрГУ, вузов и научно-исследовательских организаций России, посвященные актуальным вопросам математического моделирования и программирования.

В сборнике «Труды РФЯЦ-ВНИИЭФ» опубликованы результаты научных исследований, а также методических и проектно-конструкторских разработок в области прикладных задач теоретической физики, математического моделирования физических процессов, ядерной физики, физики ядерных реакторов, исследований по термоядерному синтезу, электрофизики, физики ускорителей, приборов и техники эксперимента, физики лазеров, гидродинамики, реологии, физики горения и взрыва, физической химии, экологии, материаловедения, безопасности, средств защиты от несанкционированных действий, электроники, радиотехники, оптоэлектроники.

Публикуются оригинальные статьи, обзоры и краткие сообщения ученых ЮУрГУ, университетов и научно-исследовательских организаций России, посвященные актуальным вопросам математики, механики и физики.

Полициклы и симметричные полиэдры возникают как обобщения графов при моделировании молекулярных структур, возникающих в химии и кристаллографии, таких как фуллерены, за открытие которых была присуждена Нобелевская премия. Химия породила много интересных вопросов в математике и компьютерном моделировании, которые, в свою очередь, предлагают новые направления при синтезе молекул. Данная монография содержит новые результаты теории полициклов и биполициклов вместе с необходимой вводной информацией, включающей в себя описание необходимых для изучения материала математических инструментов. Книга организована так, что после чтения вводной главы каждая последующая может быть прочитана независимо от предыдущих. Многие приводимые результаты потребовали использование компьютерного перебора. Соответствующие программы доступны на сайтах авторов.

В сборнике «Труды РФЯЦ-ВНИИЭФ» опубликованы результаты научных исследований, а также методических и проектно-конструкторских разработок в области прикладных задач теоретической физики, математического моделирования физических процессов, ядерной физики, физики ядерных реакторов, исследований по термоядерному синтезу, электрофизики, физики ускорителей, приборов и техники эксперимента, физики лазеров, гидродинамики, реологии, физики горения и взрыва, физической химии, экологии, материаловедения, безопасности, средств защиты от несанкционированных действий, электроники, радиотехники, оптоэлектроники.

Изложен ряд основных разделов теории графов, необходимых для разработки моделей объектов и задач дискретной оптимизации. Рассмотрены модели структур сложных систем в виде различного вида графов: ультра-, гипер-, ориентированных и неориентированных, а также формальные постановки задач комбинаторной оптимизации на графах. Описаны особенности и сущность точных методов дискретной оптимизации, таких как жадный выбор, поиск в ширину и в глубину с возвращением, ветвей и границ, Дейкстры, Форда — Фалкерсона и динамического программирования.

Публикуются статьи, обзоры и краткие сообщения ученых ЮУрГУ, вузов и научно-исследовательских организаций России, посвященные актуальным вопросам математического моделирования и программирования.

В журнале публикуются результаты фундаментальных и прикладных научных исследований отечественных и зарубежных ученых, включая студентов и аспирантов, в области дискретной математики и её приложений в криптографии, компьютерной безопасности, кибернетике, информатике, программировании, теории надежности, интеллектуальных системах. Включен в Перечень ВАК.