Обсуждение:Абстрактный тип данных

Эта статья уровня 5 жизненно важна и имеет рейтинг C-класса по шкале оценки контента Википедии . Она представляет интерес для следующих WikiProjects :

Информатика Высокая важность Эта статья находится в рамках WikiProject Computer science , совместных усилий по улучшению охвата статей, связанных с Computer science, в Wikipedia. Если вы хотите принять участие, посетите страницу проекта, где вы можете присоединиться к обсуждению и увидеть список открытых задач.Информатика Wikipedia:WikiProject Информатика Шаблон:WikiProject Информатика Информатика Высокий Данная статья имеет высокую степень важности по шкале важности проекта . Чем вы можете помочь WikiProject Computer science : Вот некоторые задачи, ожидающие внимания: Запросы статей  : Запрошенные статьи/Прикладные искусства и науки/Информатика, вычисления и Интернет Очистка  : Статьи по информатике, требующие внимания Статьи по информатике, требующие внимания экспертов Копирование  : Вычислительная техника Расширять  : Информатика Информационное поле  : Статьи по информатике без информационных блоков Поддерживать  : Хронология вычислений с 2020 г. по настоящее время Фото  : Найдите фотографии биографий компьютерных ученых (см. Список компьютерных ученых ) Вычислительные статьи, требующие изображений Заглушки  : Заготовки по компьютерным наукам Нессылки  : WikiProject Информатика/Неиспользуемые BLP Связанные с проектом  : Пометьте все соответствующие статьи в категории: Компьютерные науки и подкатегории тегом {{ WikiProject Computer science }}

В вычислительной технике абстрактный тип данных ( АТД ) состоит из «домена» (набора данных), набора операций и набора «аксиом» (правил, которым должны подчиняться операции).

Первый абзац неверен по нескольким причинам: (a) классы, хотя и являются одним из лучших способов реализации АТД, не являются единственным, и описанный здесь стиль — всего лишь одна из нескольких возможных реализаций даже на объектно-ориентированном языке; (b) в нем нет упоминания об аксиомах (они неявно подразумеваются в «спецификации», если хотите, но это слишком легко упустить из виду).

Вот моя попытка это исправить:

В программировании АТД часто используются в качестве средства проектирования и документирования: если в каком-то коде есть комментарий, который сводится к тому, что «это реализует стек», то сразу становится ясно, что основные свойства кода соответствуют свойствам АТД «стека», а все остальное программист посчитал случайными «деталями реализации».

ХТХ. -- Йоахим Дурххольц [[1]]

Как, черт возьми, сбалансированное двоичное дерево может соответствовать этой категории? Ведь сбалансированность означает, что внутренние компоненты ВАЖНЫ. Пользователь:hfastedge

Ответ -- нет. Тот факт, что бинарное дерево сбалансировано, является свойством реализации. Хотя это может значительно улучшить практическую производительность бинарного дерева, это не должно иметь никакого влияния на функциональные свойства. Сбалансированные и несбалансированные бинарные деревья идентичны с точки зрения ADT -- Дерек Росс

На самом деле сбалансированное бинарное дерево *является* АТД. Это набор данных (деревьев по некоторым заданным данным), операций (вставка/удаление/поиск путем обхода узлов дерева) и аксиом (сбалансированность).

Однако обычно пользователи сбалансированного двоичного дерева интересуются не АТД. АТД для них — это карта (вставка/удаление/поиск неважно как), плюс некоторые гарантии производительности (гарантии производительности обычно не считаются частью АТД, хотя я бы лично сказал, что это сделало бы концепцию более полезной). — Йоахим Дурххольц [[2]]

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

Ldo 12:33, 12 сентября 2003 (UTC)

На этой странице должна быть размещена информация о предварительных условиях, постусловиях и инвариантах.

ДА! Абстрактный тип данных — это не класс или какая-либо другая реализация. Он абстрактный, а не реализация. И абстрактный тип данных определяется не только в терминах его программного интерфейса, но и, как заметил комментатор выше: спецификацией поведения: предусловиями, постусловиями и инвариантами. — Предыдущий неподписанный комментарий был добавлен 67.161.67.58 ( talk • contribs ) 19:08, 16 марта 2007 г.

Исходный пример показался слишком сложным. Надеюсь, просмотр интерфейса и реализации поможет читателю разобраться.

Надеюсь, когда у меня появится больше времени, я добавлю альтернативную реализацию.

Билл Прингл | Обсуждение]] 20:39, 10 августа 2004 (UTC)

Действительно ли комплексное число является ADT?????? Talam 00:56, 6 декабря 2005 (UTC) [ ответить ]

В зависимости от того, как вы на это смотрите... Если дать достаточно объяснений, почему (являясь экземпляром Number и AlgebraicallyClosedField), то да, но нет, в том смысле, что это контейнер, как List и Tree. — Р. Кут 16:15, 6 декабря 2005 (UTC) [ ответить ]

Не то, чтобы комплексное число было ADT, но вы можете создать ADT для комплексного числа. Это список примеров ADT, которые можно найти в учебниках. Лично я считаю, что Complex Numbers — паршивый пример, но учебник, которым я пользуюсь, как раз использует этот пример. wrp103 (Билл Прингл) - [[User talk:Wrp103|Talk]] 21:17, 7 декабря 2005 (UTC) [ ответить ]

Я обнаружил, что это наиболее успешный способ объяснить, что такое ADT, дать наглядные примеры. ADT для упорядоченного набора информации предоставляет тот же API для доступа к данным, независимо от того, хранятся ли они в массиве, неупорядоченном связанном списке, упорядоченном связанном списке, двоичном дереве, дереве 3-2 и т. д. Список общих интерфейсов для ADT также необходимо добавить в статью.

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

Я попытался внести правку, чтобы исправить вашу страницу об абстрактных типах данных. Вы перечислили "связанный список" и "двоичное дерево поиска" как абстрактные типы данных, и я удалил их из списка, потому что считаю, что их не следует включать. Я не пытался испортить запись или "эксперимент", как вы сказали в своем сообщении мне.

Абстрактный тип данных не должен определять реализацию; поэтому связанный список определенно НЕ является ADT. Список, также записанный на странице, ЯВЛЯЕТСЯ ADT. Но не связанный список, не более, чем список массивов.

По той же причине бинарное дерево поиска не является ADT. Бинарные деревья поиска, как и связанные списки, являются определенными структурами данных и не зависят от реализации. Бинарное дерево поиска может *ИСПОЛЬЗОВАТЬСЯ* для реализации ADT, например, набора или карты.

(Редактор использовал разные IP-адреса при редактировании и при написании сообщений на моей странице обсуждения, поэтому у меня нет простого способа связаться с ним напрямую.)

Я не совсем согласен с логикой, но они высказали хорошее замечание, поэтому я откатился к их версии. Они правы, что ADT скрывает реализацию от пользователя, но это (на мой взгляд) не мешает ADT реализовывать структуру данных.

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

У кого-нибудь еще есть сильные чувства в ту или иную сторону? wrp103 (Билл Прингл) 00:48, 27 октября 2006 (UTC) [ ответить ]

---

Билл, я был тем, кто сделал анонимную правку о связанных списках и бинарных деревьях. Прошу прощения за мою ненужную анонимность. Меня зовут Марти Степп, и я преподаватель CS&E в Университете Вашингтона. Я по-прежнему считаю, что связанный список не является ADT, потому что само название подразумевает точный стиль реализации, который противоречит идее ADT.

Пользователь:Martnstepp (Марти Степп) 02:36, 14 ноября 2006 (PST)

Я вижу аргументы с обеих сторон. Существует много способов реализации связанного списка (одинарный / двойной, внутренний / внешний, указатели / массив и т. д.). Предоставление объекту ряда методов позволяет пользователю включать связанный список в свою программу, ничего не зная о реализации. Новая версия класса может быть распространена с совершенно новой реализацией, которая не повлияет ни на одного пользователя. Это, кажется, соответствует критериям ADT. Я не вижу, чтобы это отличалось от, скажем, Vector в Java: это абстрактный массив. wrp103 (Билл Прингл) 14:15, 14 ноября 2006 (UTC) [ ответить ]

Что касается последнего абзаца раздела «Разделение интерфейса и реализации», я ценю замечание относительно представления ADT с использованием конструкции класса. Однако последние два предложения, похоже, вводят языковые контрасты, о которых я не знаю. C также предоставляет механизмы принуждения и иерархии. Возможно, было бы понятнее добавить C в список или удалить все примеры языка.

Также не ясно, что такое "объектно-ориентированный АТД". Может быть, АТД, представленный в виде класса?

--Sector7agent 22:59, 8 января 2007 (UTC) [ ответить ]

Вот о чем я думал, когда писал это. C ограничен объявлением статических функций, которые не создают точек входа, но Java/C++ имеют private, public и protected. На самом деле, я написал этот текст некоторое время назад, и не вижу проблем, если кто-то захочет его подправить (или переписать). wrp103 (Билл Прингл) 16:00, 9 января 2007 (UTC) [ ответить ]

Первый абзац, особенно последнее предложение; это классика! речь идет об объяснении чего-либо на языке неспециалиста. Arcturus 22:16, 8 февраля 2007 (UTC) [ ответить ]

Я переписал статью с нуля.

СДЕЛАННЫЙ

• добавлен раздел резюме и две ссылки.
• четко обозначьте концептуальные границы.
• расширил разграничение, сделав акцент на ценностях.
• расширенное резюме, дающее представление о том, как работать с ADT.
• ссылки на некоторые инструменты ADT, чтобы дать читателю больше зацепок.

Статья теперь, по крайней мере, должна прояснить, что такое ADT, а что нет.

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

-- 85.182.79.140 (обсуждение) 22:48, 26 июля 2008 (UTC) [ ответить ]

Я не думаю, что 85.182.72.125 вообще улучшил статью. Его статья лишена какой-либо технической строгости и конкретного описания того, что такое Abstract Data Type. —Предыдущий неподписанный комментарий, добавленный 66.117.143.86 ( обсуждение ) 09:25, 6 августа 2008 (UTC) [ ответить ]

Я переписал только пример, пытаясь понять, смогу ли я найти приемы, которые сделают тему более доступной для более широкой аудитории. Если это сработает, аналогичные методы можно будет использовать для статьи в целом. Как только это будет достигнуто, возможно, больше не будет смысла писать так много в этом конкретном примере. Часть того, что я написал здесь, вероятно, следует написать более обобщенно обо всей теме ADT, и тогда не нужно будет повторять это здесь.

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

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

Это прекрасно выражает, что такое абстрактная структура данных. Те, кто знает, что это такое, узнают ее и почувствуют красоту.

Но даже читатель, который прошел курсы программирования до такой степени, что может закодировать быструю сортировку по описанию, не сможет легко понять, что на самом деле означает, что вещи являются «абстрактными». Что такое «абстрактное хранилище»? Представьте себе читателя, который думает: «Я полагаю, что жесткий диск — это конкретное хранилище. Может ли это быть сетевое хранилище?» Вывести это из этой статьи — в лучшем случае кроссворд.

Чтобы сделать статью более читабельной для неспециалистов, нужно дать немного больше контекста. Совсем немного может быть достаточно. (Цель все еще не в том, чтобы написать вводный курс по программированию в целом для среднестатистической домохозяйки.) Контекст здесь означает, например, ситуацию, когда большая компьютерная система разбивается на модули, модули часто делаются разными людьми, часто некоторые модули покупаются на рынке среди нескольких конкурирующих предложений и т. д. Даже когда система написана одним человеком, невозможно запомнить все детали модуля один во время написания модуля два. Даже если бы это было возможно, гибкость все равно нужна на практике, и трудно достичь гибкости без модуляризации и сокрытия информации. А сокрытие информации на самом деле не о «сокрытии», как тайные агенты ЦРУ, а просто о разъединении.

Другими словами, если ADT — это ответы, то каковы вопросы? О чем мы на самом деле говорим?

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

До этого, а возможно и сегодня, ООП часто «продавали» нереалистичными способами, подчеркивая неправильные аспекты. Я помню, что в течение многих лет у меня было ощущение, что статьи об ООП говорили вам, что все эти чудеса произошли из-за изменения синтаксиса: obj.method(args) вместо method(obj, args). Затем писатели говорили вам, что это было не просто изменение синтаксиса, но они не могли сказать, что именно это было. Было много поэзии, удовлетворяющей в основном тех, кто овладел черным искусством.

Затем стало модным говорить, что чудеса были результатом отправки сообщений объектам, делая объекты похожими на одушевленные вещи, которые более или менее продолжат с того места, где остановился программист, освобождая программиста от некоторой нагрузки. Тем не менее, эта версия была гораздо ближе к аспекту сокрытия информации, развязки. Вместо того, чтобы снять с (единственного) программиста всю нагрузку системы , ООП и более поздние изобретения снимают часть нагрузки с программистов клиентских классов, оставляя эту нагрузку программисту серверного класса. Трудно понять суть ADT и связанных с ним концепций, пока человек не попытается создать что-то сложное и не поймет, какие ошибки он совершил. Видно, как сложность каждой части течет, как вода, через всю систему, пока человек не научится сдерживать этот поток в водонепроницаемых отсеках.

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

Описание в предыдущем абзаце описывает более или менее одинаково хорошо несколько других связанных концепций. Тонкости, различия между ADT и, например, "интерфейсами", кто может сказать что-то разумное об этом?

(Кстати, слово «интерфейс» используется во многих смыслах... Представьте себе не совсем начинающего пользователя компьютера, который думает, что «интерфейс» — это сетевая карта или ее программный эквивалент... Было бы грубо говорить просто «интерфейс» и позволять читателям, которые не понимают, что вы имеете в виду, чувствовать себя идиотами.)

Эволюция ООП служила нескольким целям, идя в нескольких направлениях. ADT и интерфейсы являются следующим шагом в одном из направлений. ООП и классы по-прежнему работают в основном с конкретными реализациями. ADT удаляют все, что не является существенным для знания программистами других модулей. С другой стороны, он идет дальше, когда исследует другие вещи, о которых пользователю может понадобиться знать, например, сложность. Быстрые реализации всегда были очевидной целью. Новое измерение открылось, когда STL была задокументирована с компромиссом различных видов эффективности для различных видов контейнеров. Было легко понять, что многие компромиссы были неизбежны, и это прояснило, что что-то должно было быть в спецификации, чтобы направлять выбор пользователей. Сначала это была, конечно, просто «лучшая» документация. Затем она была повышена до спецификации.

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

Может быть, я попробую сделать это сам. Но сначала мне нужен перерыв, чтобы немного остыть. Cacadril ( обсуждение ) 14:11, 24 января 2009 (UTC) [ ответить ]

Если вы действительно хотите сделать пример стека ADT, то вам не нужно беспокоиться о том факте, что он реализован с использованием дескриптора. Было бы гораздо чище typedef stack_t как long, а затем использовать этот тип для ссылки на стеки (обратите внимание, как мне все равно и я не хочу знать о деталях реализации — например, «почему long, а не unsigned?» — хотя на это могут быть веские причины, когда вы пересекаете барьер реализации). Помните, люди: пример кода должен быть образцовым (как цитируется в «Good API design and why it important» на googletechtalks). 62.166.203.162 (обсуждение) 12:50, 12 марта 2009 (UTC) [ ответить ]

ADT — это АБСТРАКТНАЯ (=теоретическая) структура. Реализация ADT — это не ADT, это (конкретная) структура данных или тип данных (на определенном языке). Всего наилучшего, — Хорхе Столфи ( обсуждение ) 23:05, 14 мая 2009 (UTC) [ ответить ]

Следующее определение неверно:

« Абстрактный тип данных — это набор значений и набор процедур, которые манипулируют этими значениями. Клиент абстрактного типа данных (то есть часть программы, которая использует этот тип) Все объявления, составляющие абстрактный тип данных, помещаются в модуль Локальные идентификаторы, которые должны быть видны за пределами модуля, экспортируются ; все остальные локальные идентификаторы невидимы за пределами модуля, что позволяет программистам скрывать детали реализации от клиентов модуля. Идентификаторы из окружающих модулей не наследуются автоматически модулем. Вместо этого те, которые необходимы, должны быть явно импортированы . Некоторые идентификаторы, такие как предварительно объявленные типы integer и Boolean, могут быть объявлены всепроникающими , что означает, что они автоматически импортируются во все вложенные области имен.

Это определение путает ADT (который является теоретической концепцией) с концепциями программной инженерии "модуль" и "интерфейс". Разница такая же, как между математической функцией exp() и библиотечной процедурой, которая ее вычисляет. Концепции клиентов, идентификаторов, наследования, видимости и т. д. так же чужды ADT, как концепции переполнения и NAN чужды математической exp(). Всего наилучшего, -- Хорхе Столфи ( обсуждение ) 23:33, 14 мая 2009 (UTC) [ ответить ]

Существуют алгоритмы, которые работают , когда V — неинициализированная переменная, и зависят от этого для достижения оптимального асимптотического времени выполнения. Примером является проверка того, есть ли повторения в заданном массиве из n чисел, каждое из которых находится в диапазоне от 0 до n ² -1. С массивом из n ² переменных, каждая из которых может хранить число в диапазоне от 0 до n -1, задача может быть решена за O( n ) шагов. Обратите внимание, что это невозможно, если элементы массива должны быть инициализированы либо алгоритмом, либо операцией выделения памяти. В статье есть примечание на этот счет. Оно требует ссылки или вики-ссылки; но я не могу вспомнить название этого трюка или его изобретателя. Поиск в Google по запросу «неинициализированный массив» не дал такой информации. Есть ли она у кого-нибудь? Спасибо и всего наилучшего, — Хорхе Столфи ( обсуждение ) 00:59, 23 мая 2009 (UTC) [ ответить ]fetch(V)

Вопрос о связи между абстрактными типами данных и объектами является сложным. В предыдущих версиях этой страницы говорилось, что «Абстрактные типы данных также являются важным концептуальным инструментом в объектно-ориентированном программировании и методологиях проектирования по контракту для разработки программного обеспечения . ^{[ требуется ссылка ]} ». Однако более детальное изучение связи показывает, что объектно-ориентированное программирование и абстрактные типы данных являются фундаментально различными формами абстракции данных.

Название «абстрактный тип данных», по-видимому, было придумано исследователями в области разработки программного обеспечения и дизайна языков программирования ; в то время как «абстрактная структура данных» была придумана исследователями в области структур данных и алгоритмов. ^{[ необходима ссылка ]}

Я удалил два абзаца выше из статьи, так как они представляют собой интересные наблюдения, но требуют обоснования и уточнения. 71.146.74.108 ( обсуждение ) 14:56, 19 апреля 2010 (UTC) [ ответить ]

Что касается последнего замечания, было бы интересно услышать мнение историка в области компьютерных наук. Мое впечатление таково, что хотя эти два термина могли использоваться независимо и взаимозаменяемо с течением времени, термин ADT получил предпочтение, поскольку он лучше отражает соответствующую концепцию абстракции, которая является *поведением*, а не *организацией* абстрагированного представления данных. Что касается того, кто что придумал, следует помнить, что в те ранние времена существовало сильное совпадение между исследователями в области теоретической программной инженерии и теоретической компьютерной науки, судя по таким именам, как Хопкрофт или Ульман. 71.146.74.108 ( talk ) 15:12, 19 апреля 2010 (UTC) [ ответить ]

Я удалил следующее эссе, вставленное в текст пользователем 101.210.91.186 (обсуждение  · вклад  · WHOIS) в этой редакции от 21 февраля 2012 г., и восстановил раздел о преимуществах абстрактной типизации данных . -- Петри Крон ( обсуждение ) 19:45, 12 мая 2012 (UTC) [ ответить ]

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

На самом деле весь текст был нарушением авторских прав и копипастом с tutorialspoint.com, подходящим образом названного Data Abstraction in C++ . Теперь удален. (tutorialspoint.com внесен в черный список Wikipedia:Spam , поэтому я не могу дать ссылку на источник.) -- Петри Крон ( обсуждение ) 12:06, 13 мая 2012 (UTC) [ ответить ]

Этот раздел больше похож на учебник, чем на статью энциклопедии. Подходит ли он для статьи? Может быть, контент можно перераспределить таким образом, чтобы он имел больше смысла. 77.11.28.130 (обсуждение) 10:08, 20 июня 2014 (UTC) [ ответить ]

Похоже, что это было скопировано из какого-то школьного учебника, особенно потому, что это ссылается на Википедию ;) Я скопировал это сюда, но удалил из статьи. -- WiseWoman ( обсуждение ) 21:34, 26 октября 2014 (UTC) [ ответ ]

==Тип данных Abstract по компьютерным наукам IB==В курсе абстрактный тип данных относится к обобщенной структуре данных, котораяпринимает объекты данных, хранящиеся в виде списка с определенным поведением, определяемым методамисвязанные с базовой природой списка.Это очень важная идея в информатике. Она основана на признании того, чточасто группа данных — это просто список в случайном или определенном порядке. Список чиселможет быть как целым, так и действительным, но, как и в арифметике, числа могут представлять любые числовые значения.количество, например, вес списка учеников в классе, в этом случае мы будем иметьсписок действительных чисел. Математические операции, например, среднее, минимум, максимум, выполняются точноодинаково для любого списка действительных чисел, независимо от конкретной природы списка.Например: группу людей, стоящих в очереди в столовой, можно представить в виде списка сопределенные характеристики или поведение. Люди приходят и прикрепляются к концу очереди,люди обслуживаются и покидают очередь с головы или начала очереди. Любая простая очередьможно описать точно так же. Те же основные операции: добавить, удалить, вставитьвсегда одинаковы, не имеет значения, представляет ли объект данных человека иличто-то еще. Добавление объекта в конец очереди — это точно такая же операция длялюбой набор данных, описываемый как очередь.ADT имеет обобщенное имя, например, Stack, Queue, BinaryTree и т. д. Каждый ADT принимает данныеобъекты, представленные как элементы базового списка, например, целое число, PersonОбъект. Каждый АТД имеет набор предопределенных методов (поведений в терминологии ООП)которые можно использовать для манипулирования членами списка - независимо от того, что онина самом деле в реальности представляют.Другие специальные материалы по ADT можно найти в соответствующих разделах Википедии, например, «Стек», «Очередь», «Массив» и т. д.