Какая тема в дискретной математике считается необходимым условием для курса структур данных?

Question

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

P.S. Я программист-самоучка; Я не посещал курсы информатики.

Answer 1

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

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

Вам не нужно знать что-либо из этого, чтобы прочитать о структурах данных.

Answer 2

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

Кстати, классический учебник по этой теме - Конкретная математика: Фонд компьютерных наук , автор Рональд Грэм, Дональд Кнут и Орен Паташник.

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

Answer 3

Некоторые темы, обычно встречающиеся в вводных дискретных математических книгах, которые пригодятся в курсе алгоритмов / структуры данных:

1. Некоторые основные вероятности / статистика: полезны для понимания хеширования и рандомизированных алгоритмов
2. В большинстве дискретных учебников по математике есть главы о графиках и связанных с ними понятиях, таких как топологическая сортировка, отношения, частичные и общие порядки.
3. Теория множеств и формальная логика: основные инструменты в рассуждениях о правильности и сложности алгоритмов.

Вероятно, есть несколько других, которые избегают меня в этот момент. Прошло много времени с тех пор, как я покинул колледж.

Сказав это, хорошая книга о структуре данных / алгоритмах часто содержит одну или две вводные главы и разделы в большинстве других глав, которые направлены на то, чтобы помочь читателю быстрее освоить некоторые из соответствующих отдельных математических тем. Но ИМО, лучше знать этот материал просто для более глубокого понимания, если у вас есть время и желание. В противном случае, я не думаю, что вы застрянете, если у вас будет хорошая книга.

PS: Темы, которые я упоминаю, взяты из этих двух книг: «Дискретная и комбинаторная математика: прикладное введение» Гримальди "Дискретная математика и ее приложения" Розена («Конкретная математика» слишком сложна для чтения только для структур данных)

Answer 4

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

Answer 5

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

Answer 6

Для структур данных и алгоритмов, я думаю, вы, скорее всего, захотите узнать область исчисления, связанную с вычислением пределов ряда. Это, в свою очередь, включает в себя некоторые знания алгебры.

Вам нужно знать, как вычислять пределы серии, чтобы можно было вычислять сложность алгоритма.