Алгоритм Дейкстры является одним из наиболее популярных и фундаментальных алгоритмов решения проблемы поиска кратчайшего пути в ориентированном графе. Хорошо известно, что алгоритм Дейкстры применим к орграфам с неотрицательно взвешенными дугами. Но, как показывают простые наблюдения, существует множество орграфов и даже классов орграфов с отрицательно взвешенными дугами, к которым алгоритм Дейкстры также применим. Таким образом, условие неотрицательности весов дуг является достаточным, но не является необходимым. Необходимое условие применимости алгоритма Дейкстры не было известно. В этой статье мы представляем и доказываем необходимое и достаточное условие применимости алгоритма Дейкстры. Условие основано на введённом нами понятии рекорда пути. С. 5-13.

Dijkstra’s algorithm is one of the most popular and fundamental algorithms solving the shortest path problem in directed graphs (digraphs). It is well known that Dijkstra’s algorithm is applicable to digraphs with non-negative weighted arcs. But as simple observations show there are many digraphs and even classes of digraphs with negatively weighted arcs for which the Dijkstra’s algorithm is also applicable. Thus the non-negative weight of the arcs condition is not a necessary condition but only a sufficient one. pagebreak The necessary condition for applicability of Dijkstra’s algorithm was unknown. In this paper, we present and prove a necessary and sufficient condition for the applicability of Dijkstra’s algorithm. The condition is based on the notion of a path's record that we introduce.

В настоящее время онтологии широко используются в информатике для формализованного представления знаний о различных предметных областях. Разработаны и успешно применяются специальные формальные языки описания онтологий, которые позволяют описывать онтологии в форме, доступной для использования как человеком, так и компьютером. Среди разнообразных вариантов использования онтологий особое место занимает применение онтологий в образовании, поскольку систематизация и упорядочение знаний, будучи главным конкурентным преимуществом онтологического подхода, одновременно является одной из главных целей образовательного процесса. В статье предложены оригинальные приёмы построения онтологий для использования в образовательном процессе высшей школы. Центральной идеей является построение фасетных, иначе говоря, – многогранных онтологий, в которых различные аспекты одной и той же предметной области описываются концептуально схожими, но синтаксически различными средствами. Такой подход обеспечивает более точное и семантически адекватное описание при сохранении известной лаконичности и наглядности обозначений. В качестве языка описания онтологий предлагается использовать унифицированный язык моделирования UML 2, прекрасно зарекомендовавший себя при формализации во многих случаях. Изложение ведётся на примере построения онтологии дискретной математики, причём приводимые в статье диаграммы онтологий внедрены в учебные процессы Академического и Политехнического университетов Санкт-Петербурга. С. 68-84.

Currently, ontologies are widely used in computer science for the formalized representation of knowledge about various subject areas. Special formal languages for describing ontologies have been developed and are successfully used, which allow describing ontologies in a form that is accessible for use by both humans and computers.Among the various options for using ontologies, a special place is occupied by the use of ontologies in education, since the systematization and ordering of knowledge, being the main competitive advantage of the ontological approach, is at the same time one of the main goals of the educational process. The article proposes original methods of constructing ontologies for use in the educational process of higher education. The central idea is the construction of faceted, in other words, multifaceted ontologies, in which different aspects of the same subject area are described by conceptually similar, but syntactically different means. This approach provides a more accurate and semantically adequate description while maintaining the known brevity and clarity of designations. As a language for describing ontologies, it is proposed to use the unified modeling language UML 2, which has proven itself in formalization in many cases. The presentation is based on the example of constructing an ontology of discrete mathematics, and the ontology diagrams given in the article are introduced into the educational processes of the Academic and Polytechnic Universities of St. Petersburg.

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