ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА
Основатель
, д. техн. н., профессор, член-корр. НАН Беларуси.
Руководитель научно-педагогического коллектива
, д. техн. н., профессор, отличник высшей школы СССР.
Факультеты, кафедры (лаборатория)
Факультет прикладной математики и кибернетики, кафедра защиты информации и криптографии, кафедра программирования, лаборатория компьютерной безопасности.
Радиофизический факультет, кафедра информационных технологий в исследовании дискретных структур,
Направление научных исследований научно-педагогического коллектива
– Дискретная математика и ее приложения в теории дискретных автоматов, криптографии и компьютерной безопасности.
По рубрикатору ГРНТИ
27.47.15 – Математическая теория управляющих систем.
49.33.35 – Надежность сетей связи и защита информации.
По рубрикатору ВАК
05.13.17 – Теоретические основы информатики.
05.13.19 – Методы и системы защиты информации, информационная безопасность.
Направления подготовки инженеров, бакалавров и магистров
010200 - Прикладная математика и информатика.
075200 - Компьютерная безопасность.
071500 - Радиофизика и электроника.
Состав коллектива
Всего – 30, в том числе:
Докторов наук – 4,
Кандидатов наук – 13.
Ведущие представители коллектива
, к. техн. н., доцент.
, к. техн. н., доцент.
, д. физ.-мат. н., профессор
, д. техн. н., профессор.
, д. техн. н., доцент.
История становления научно-педагогического коллектива
Исследования по дискретной математике в ТГУ начались около 45 лет назад с научной работы тогдашнего аспиранта РФФ Аркадия Дмитриевича Закревского:
Закревский синтеза функционально устойчивых автоматов // ДАН СССР. 1959. Т. 129, вып. 4. С. 729-731.
Тот факт, что эти исследования зародились на РФФ, а не на мехмате, наложило определенный отпечаток на их характер. Изначально они велись как прикладные, т. е. вызывались не потребностями самой математики, но ее применениями - главным образом, к синтезу дискретных автоматов (тогда - релейных схем управления). Прикладной характер исследований выразился и в том, что их результатами должны были стать алгоритмы решения задач дискретной математики, аттестованные в эксперименте на вычислительной машине.
В 1960 г. защищает диссертацию на соискание ученой степени кандидата физико-математических наук на тему «Матричный метод синтеза релейных схем». В это же время его студенты-дипломники , , и получают Золотую медаль АН СССР за лучшую научную студенческую работу. Эти «четверо под одной крышей» реализовали на единственной в то время в Сибири ЭВМ (по современному – компьютере) «Урал-1» идеи из диссертации своего руководителя и практически доказали, что «машина может строить машины». Одновременно стало ясно, что обучить машину делать это, пользуясь ее машинным языком, для человека весьма затруднительно по причине неестественности этого языка. И тогда решает – ни много ни мало – построить специализированную ЭВМ, ориентированную исключительно на решение задач логического синтеза, т. е. такую ЭВМ, язык которой содержит в качестве элементарных машинных команд все логические операции, которые разработчик ЭВМ применяет при создании ее функциональной схемы. В считанные месяцы создает язык такой машины, описывает на формальном языке ее архитектуру и вместе со своими учениками и коллегами (, , ) разрабатывает принципиальные схемы всех ее блоков. Ее назвали L-машиной. В 1961 г. студент-дипломник создает эмулятор L-машины на ЭВМ «Урал-1», а студент-дипломник уже программирует для нее свой алгоритм синтеза контактных схем.
Но дальше дело не пошло: в условиях вуза воплотить машину «в железе» оказалось невозможно, и с пути «железного» переходит на путь «математический» – решает создать язык общения с ЭВМ, который, с одной стороны, был бы близок языку представления алгоритмов синтеза человеком, а с другой – был бы совершенно формальным и, следовательно, переводимым на язык машины средствами ее же языка. Фактически речь шла о том, чтобы язык L-машины «поднять» без утраты его строгости до языка человеческого. Было ясно, что связка «ЭВМ+L-язык» будет медленнее L-машины, но другого выбора не оставалось. Уже в марте 1962 г. на одном из международных научных форумов компьютерщиков докладывает об основных элементах такого языка, а к концу 1963 года завершает работу над ним и создает транслятор с него на язык ЭВМ «Урал-1». Язык получил название ЛЯПАС – Логический Язык для Представления Алгоритмов Синтеза. В 1964 г. в Томске по инициативе состоялся первый в СССР научный коллоквиум по языкам конечных автоматов, на котором язык ЛЯПАС получил всесоюзное признание. Он стал первым и пока единственным "русским языком программирования", который нашел применение в научной, образовательной и производственной сферах не только в СССР, но и за рубежом – в Польше, Германии, США. В 1966 г. в Московском издательстве «Наука» выходит тематический сборник трудов школы , который вскоре издательством США Academic Press выпускается на английском языке. До начала 1990-х годов ученики школы (в ТГУ – , , , ; в Новосибирске – ; в Минске – , , и др.) развивают и поддерживают ЛЯПАС на всех отечественных ЭВМ – М-20, М-220, БЭСМ-4, БЭСМ-6, Минск-22, Минс-32, ЕС, СМ, ПК. На его основе в 1970-е и 1980-е годы в школе был создан ряд систем автоматического синтеза и диагностики дискретных автоматов, которые широко применялись на предприятиях министерств электронной и радиопромышленности СССР вплоть до его развала. В их создании в ТГУ непосредственное участие принимали , , , , . Параллельно развивалась теоретическая и алгоритмическая база для создаваемых систем. В ТГУ ее составили методы декомпозиции конечных автоматов (, ), технология решения комбинаторно-логических задач (, ), теория дискретных автоматов на полурешетках (), полурешеточная теория интегральных схем (, , ), методы синтеза комбинационных схем (, , ), методы синтеза тестов и легкотестируемых схем (, , ), методы структурной декомпозиции дискретных автоматов (, ). Кроме того, в 1960-е годы в школе в ТГУ велись закрытые научные исследования по применению криптографии для защиты управляющей информации в открытом радиоканале.
В 1990-е годы изменения в стране сказались и на научных исследованиях в школе . И хотя по-прежнему алгоритмические результаты исследований испытываются в эксперименте на компьютере, в ТГУ они теперь уже не связаны с отечественным производством, носят, как правило, абстрактный характер, финансируются в основном за счет разного рода грантов (РФФИ, Минобразования и др.) и в традиционной области (логического синтеза и диагностики) ориентированы в значительной степени на западные научные круги. Так, научная группа под руководством (, , ) ведет свои работы по синтезу самопроверяемых и контролепригодных схем в содружестве с университетами Телль-Авива (Израиль), Таллинна (Эстония), Турина (Италия), Потсдама (Германия), с Национальным политехническим институтом Франции, а научная группа под руководством (, , М. Дорофеева, С. Жарикова, А. Кириллов. , , В. Маракин, , ) в своих исследованиях по тестированию автоматных сетей и недетерминированных автоматов успешно сотрудничает с университетами Беркли (США), Оттавы (Канада), Кайзерслаутерн (Германия), с научно-исследовательскими центрами Монреаля, Рима и Национальным институтом Франции по телекоммуникациям.
Заметные успехи в это время достигнуты также в синтезе дискретных автоматов из программируемых компонент ( и ), а на рубеже столетий – в решении проблемы полноты и выразимости в классе квазимонотонных функций на конечной полурешетке () и в синтезе схем для реализации таких функций (). Новые области исследований – фрактальное сжатие изображений и квантовые вычисления – открыла для школы . На пороге нового тысячелетия в школе в ТГУ в связи с проблемами компьютерной безопасности возобновились научные исследования в области криптографической защиты информации (, , ).
В 1960-е годы школа в ТГУ опирается на кафедру электронной вычислительной техники и автоматики РФФ (зав. каф. ) и лабораторию счетно-решающих устройств ТГУ (зав. лаб. ); в 1970 г. с открытием ФПМК она получает собственную кафедру – математической логики и программирования (зав. каф. ), а в 1972 г., после открытия отдела кибернетики СФТИ, – собственную научно-исследовательскую лабораторию синтеза дискретных автоматов (зав. лаб. ). В настоящее время она имеет 3 кафедры – информационных технологий в исследовании дискретных структур РФФ (зав. каф. ), программирования ФПМК (зав. каф. ), защиты информации и криптографии ФПМК (зав. каф. ) и научно-исследовательскую лабораторию компьютерной безопасности (зав. лаб. ).
Основные научные результаты, полученные коллективом в течение последних пяти лет
Математическая модель и технология разработки безопасных корпоративных информационных систем.
Критерии полноты и выразимости в классе квазимонотонных функций на конечных полурешетках.
Методы решения конечно-автоматных уравнений.
Методы синтеза и анализа недетерминированных автоматов.
Методы синтеза самопроверяемых и самовосстанавливаемых схем из функциональных элементов.
Методы синтеза управляющих систем из программируемых логических интегральных схем.
Методы синтеза переключательных схем с заданным динамическим поведением
Алгоритмы криптоанализа для кодовых криптосистем.
Алгоритмы криптоанализа генераторов ключевого потока.
Параллельный алгоритм фрактального сжатия изображений.
Критическая технология федерального уровня.
Системы математического моделирования.
Важнейшие публикации коллектива
Монографии – 2, учебники – 2, статьи – 200, в т. ч. в центральных журналах – 50.
1. Buffalov S. A., Yevtushenko N. V. The study of solutions to a parallel FSM equation // Bulletin of the Novosibirsk Computing Center, series: Computer Science, issue 14, NCC Publisher, Novosibirsk, 2001. P. 7-19.
2. Petrenko A., Yevtushenko N. Solving Asynchronous Equations // Proc. IFIP FORTEXI/PSTV, XVIII, Kluwer Academic Publishers, 1998. P. 231-247.
3. Агибалов автоматы на полурешетках. – Томск: Изд-во Том. ун-та, 1993. 227 с.
4. О прикладной дискретной математике в ТГУ (1970-1999 гг.) // Вестник Томского государственного университета. 2000. Т. 271. С.19-28.
5. , Беляев решения комбинаторно-логических задач. Томск: Изд-во Том. ун-та, 1981. 128 с.
6. , Евтушенко конечных автоматов. Томск: Изд-во Том. ун-та, 1985. 125 с.
7. , О полноте систем монотонных функций для реализации квазимонотонных функций на конечных полурешетках // Дискретный анализ и исследование операций. 2002. Серия 1. Т. 9, № 4. С. 5-22.
8. , Оранов погрешности двух приближенных алгоритмов разбиения // Известия РАН. Теория и системы управления. 1999. № 1. С.89-93.
9. Беляев алгоритмы структурной декомпозиции управляющих систем // Вестник Томского государственного университета. 2000. Т. 271. С. 92-97.
10. , Шабалдин сжатие изображений и его параллельная реализация // Новые информационные технологии в исследовании дискретных структур. Томск: Спектр, 2000. С. 74-79.
11. , Куфарева между недетерминированными автоматами. Томск: Спектр, 2001. 26 с.
12. , О контрольном эксперименте с детерминированной реализацией при недетерминированном эталоне // Кибернетика и системный анализ. 1998. № 1. С. 57-65
13. , , Петренко проверяющих тестов для недетерминированного автомата относительно редукции // Автоматика и вычислительная техника. 1998. № 3, С.10-20.
14. , , К синтезу контролепригодных комбинационных устройств // Автоматика и телемеханика. 1999. № 2. С. 129-137.
15. Матросова, А. Ю., , Синельников самопроверяемых автоматных сетей в базисе ПЛМ // Автоматика и телемеханика. 2002. № 10. С. 120-136.
16. К синтезу дискретных схем в базисе ПЛИС // Известия РАН. Теория и системы управления. 1999. № 2. С. 160-166.
17. Парватов полнота в замкнутых классах квазимонотонных и монотонных трехзначных функций на полурешетке // Дискретный анализ и исследование операций. 2003. Сер. 1. Т. 10, № 1. С. 61-78.
Участие в течение последних трех лет в
научно-технических программах
федеральных – 3:
1 – НТП «Производственные технологии»,
1 – НП «Университеты России»,
1 – ФЦП «Интеграция».
Международных – 4:
научные стажировки в Корее, Франции, Израиле.
Международных проектах – 2:
НАТО, Intel.
Победы в конкурсе грантов – 7:
3 – РФФИ, 4 – Минобразования РФ.
Подготовка кадров высшей квалификации за последние девять лет
Всего аспирантов – 15, из других вузов – 1.
Всего докторантов – 2. Защит докторских – 3. Защит кандидатских – 11.
Общественное признание научно-педагогического коллектива
Международные и государственные премии, научные медали
Государственная научная стипендия для выдающихся ученых и стипендия НК «ЮКОС» ().
Лауреат конкурса молодых ученых ТГУ ().
Лауреат конкурса в сфере образования и науки Томской области (, , ).
Медали и дипломы выставок, конференций и т. д.
9 премий за лучшие доклады молодых ученых (Туапсе, 2001; Новосибирск, 2001; Томск, 2000).
Связь с другими организациями
Российская академия наук
Совместное проведение трех конференций, организация лаборатории компьютерной криптографии в отделении информатизации ТНЦ СО РАН.
Высшие учебные заведения
Университеты Монреаля, Оттавы, Франкфурта, Беркли (США),
Национальный институт Франции по телекоммуникациям,
Московский государственный университет,
Институт криптографии, связи и информатики Академии ФСБ
Деятельность научно-педагогического коллектива в области
Организации специальных школ
Ежегодная Сибирская школа-семинар «Проблемы компьютерной безопасности и криптография» - SIBECRYPT.
Открытия новых специальностей
075200 - Компьютерная безопасность.
Создания новых учебных дисциплин
Более 60 дисциплин, в том числе:
Анализ безопасности компьютерных систем.
Вычислительные методы в теории чисел и общей алгебре.
Введение в специальность 075200.
Надежность компьютерных систем.
Криптографические методы защиты информации.
Дискретное математическое моделирование интегральных схем.
Технология разработки комбинаторных алгоритмов.
Математическая электроника и др.
Разработки учебных программ
Учебные программы по 20 общепрофессиональным и специальным дисциплинам учебного плана специальности 075200.
Организации симпозиумов, конференций
11-е Международное совещание IFIP по тестированию систем связи, 1998.
3-я и 4-я российские конференции «Новые информационные технологии в исследовании дискретных структур», 2000, 2002 гг.
1-я Сибирская школа-семинар «Проблемы компьютерной безопасности», 2002.
Членство в различных российских и зарубежных организациях
Программный комитет ежегодных (1996-2003) международных IFIP конференций TestCom, FORTE/PSTV ().
Материально-техническая база, имеющаяся в распоряжении коллектива
3 локальные вычислительные сети из 33 персональных компьютера, с выходом в Internet.
Контактные адреса и телефоны
634050, Томск, пр. Ленина, 36, ФПМК.
Телефон (382-2)-426099, (382-2)-412893, Факс (382-2)-415585, *****@***tsu. ru
