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

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

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

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

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

Answer 5

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

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

Answer 6

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