12 января 2012 в 12.00 лекции Рубчинского Александра Анатольевича

Тема лекций - The shortest path problem and cluster analysis problems and its applications

Рубчинский Александр Анатольевич прочтет следующие лекции 12 января 2012, 12.00 - 13.00, Родионова 136, ауд. 401.

Кратчайшие пути с модифицированными функциями веса

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

Дивизимно-агломеративный алгоритм классификации на основе минимаксной модификации частотного подхода

Аннотация. В работе рассматривается традиционная задача автоматической классификации (АК). Предло-женный  подход состоит в новой комбинации достаточно известных методов и их модификации. Сначала осуществляются последовательные дихотомии исходного множества и тем самым строит-ся семейство классификаций на 2, 3, …, k подмножеств где k – некоторое число, заведомо превос-ходящее предполагаемое число классов (дивизимный этап). Используемая дихотомия относится к частотным методам, представляя собой их новую модификацию; она естественно включает в себя элементы рандомизации. Затем из каждой из полученных классификаций строится новое семейст-во классификаций путём последовательного объединения наиболее близких подмножеств (агломе-ративный этап). После  этого для дальнейшего анализа оставляются только несовпадающие класс-сификации. Наконец, весь процесс повторяется несколько раз, в результате чего большинство из оставшихся классификаций оказываются стохастически неустойчивыми. Устойчивая классифика-ция с максимально возможным числом классов и объявляется решением исходной задачи АК, а отсутствие устойчивых классификаций интерпретируется как отсутствие кластерной структуры в исходном множестве.