Алгоритмическая полнота

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

А. н. не означает неразрешимости тех или иных единичных проблем данного класса — часть из них может иметь свои решения. Но в целом данный класс задач не имеет ни общего универсального алгоритма решения, ни ветвящегося алгоритма полного разбиения класса на подклассы, к каждому из которых был бы применим свой специфический алгоритм. А. н. как невозможность обобщенной системы точных предписаний по решению задач одного и того же типа имеет принципиальное значение для психологии мышления, обучения и теории познания. В т. ч. из нее вытекает, что основные компоненты деятельности человека (планирование, выполнение, контроль результатов, коррекция) не м. б. построены на алгоритмической основе, хотя и могут включать в качестве вспомогательных те или иные алгоритмические процедуры.

Решение задачи, относящейся к типу алгоритмически неразрешимых, с неизбежностью включает неалгоритмизуемые компоненты и требует творчества: способ ее решения не выводится из более общего известного типового метода, а изобретается. Успех здесь не может быть гарантирован на 100% никакими методами (в отличие от ситуации с алгоритмически разрешимыми задачами).

Тема 4. Структурная организация данных. Теоретические основы поиска и сортировки данных.

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

Понятие структуры данных. Основные логические структуры данных. Линейные структуры (списки данных, векторы данных). Табличные структуры (таблицы данных, матрицы данных, многомерные таблицы). Иерархические структуры данных. Двоично-поисковые деревья, их разновидности.

Базовая структура компьютерной памяти. Единицы хранения данных (байты, слова, полуслова, двойные слова, файлы). Описание структуры записей в файлах.

Файловая структура хранения данных.

Задачи поиска информации и основные типы условия поиска(по совпадению, по интервалу, по близости, по сложному арифметическому условию, по семантическому условию, по логической совокупности нескольких условий, по текстовому значению).

Методы информационного поиска: простого перебора, многоступенчатого перебора, дихотомического поиска, вычисляемых адресов, деревьев сравнений. Оценка эффективности методов поиска.

Постановка задачи упорядочения данных в компьютерной памяти. Основные стратегии сортировки данных: выборка, включение, распределение, слияние, учет сортированности. Реализация стратегий сортировки различными методами (метод пузырька, метод выборки с применением турнира, метод простых вставок, цифровая сортировка, сортировка слиянием, деревьев сравнений, Шелла и др.)

Оценка эффективности методов сортировки.

Дата добавления: 2014-01-20