Конференции ИВТ СО РАН

Тезисы докладов

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

Класс тьюрингово вычислимых функций охватывает все рекурсивные функции: всякая рекурсивная функция вычислима по Тьюрингу. Языки программирования также являются адекватными формализациями понятия алгоритма. Они могут использоваться для задания точно очерченного и представительного класса алгоритмов. Здесь важно то, что каждый алгоритм может быть записан на языке. Формальные задания алгоритмов (исчислений) могут быть объектом алгоритмических (исчислительных) преобразований. Возникает понятие способ программирования и программы как объекта вычисления и порождения (и объекта нашего рассмотрения). Соответственно, создается способ программирования как способ погружения формального задания алгоритма в ансанбль входов и выходов. Для каждого алгоритма существует исчисление с соответствующими свойствами.

К приложениям. Само понятие программы как описания программы и данных на языке программирования принадлежит к числу весьма сложных, трудных для точного исследования математическими методами. Аналогично, процессы, изображаемые программой, характеризуются высоким уровнем сложности, превосходящим сложность многих систем и технологий. Менее формально, программирование это дисциплина, описывающая понятия, методы, приемы, средства, процесс конструирования и исполнения программ. Под термином “искусство конструирования” понимается главным образом знание и применение приемов программирования, позволяющих создавать программы, удовлетворяющие определенным требованиям. При конструировании программ реализуют(ся) определенные алгоритмы обработки информации с помощью средств программирования [2].

Применения. Отметим важность обучения программированию на основе использования алгоритмов. Лучший эффект достигается при обучении с использованием электронного учебника, изучением текстов программ, изучением базовых приемов программирования. Наиболее значимыми являются методы и алгоритмы работы с динамическими структурами данных, алгоритмы обработки сложных структур (массивы, графы, деревья, списки), алгоритмы трансляции (компиляции, интерпретации) [2]. На них основаны алгоритмы анализа (семантический, потоковый) и преобразования программ (трансляции, оптимизирующие, конкретизирующие, смешанные вычисления), с обоснованием их применений, методами и способами реализации. Не менее привлекательны алгоритмы работы с базами данных. Алгоритмы поиска, сортировки, и им подобные, удобны и как базовые, и для обучения приёмам доказательства правильности и существования алгоритма, вычисления их сложности. Имеются инструменты преобразований, инструменты обучения, соответственные информационные системы. Соблюдение и использование приёмов (технологий) программирования необходимый элемент конструирования качественных (надёжных, эффективных) программ.

Литература
1. В.А. Успенский, А.Л. Семёнов. Теория алгоритмов: основные открытия и приложения, // М.: Наука, 1987 г. , 288 стр.
2. М.М. Бежанова, Л.А. Москвина, И.В. Поттосин. Практическое программирование. Структуры данных и алгоритмы. // М.: Логос, 2001 г., 223 стр.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск