Малополезные темы для программиста по Дискретной математике

[romzes200677]

Привет Всем форумчанам !!!

Я программист delphi/oracle(пытаюсь переучиться на java самомтоятельно)

Недавно решил подтянуть знания по "алгоритмам и структурам данных" т.к собеседование(на java junior, не game dev) не пройдешь без этих знаний. Начал читать книги и понял что без дискретной математики здесь ловить нечего (т.к я ее особо не учил в универе).Книгу "Дискретная математика для программистов" Новикова не захотел т.к там плохо объясняется и нужен уже хороший уровень знаний математики. Сейчас решил восполнить пробелы знаний , взял книгу Андресона "Дискретная математика и комбинаторика" , выбрал ее потому что там есть задачи и ответы и достаточно подробно все расписано , но книга достаточно объемная 800 страниц . Я уже 8 глав прочитал и прорешал задачи . Так вот осталась еще большая часть книги , может какие-нибудь темы можно пропустить т.к по расчетам еще пол года минимум мне ее учить если все полностью читать и решать а времени мало .Если не трудно напишите какие тему можно/допустимо пропустить из книги.

Вот список оставшихся тем :

Алгебраические структуры 392
9.1. Вновь о частично упорядоченных множествах 392
9.2. Полугруппы и полурешетки 397
9.3. Решетки 403
9.4. Группы 409
9.5. Группы и гомоморфизмы 415
Некоторые специальные вопросы
теории чисел 422
10.1. Целочисленные решения линейных уравнений 422
10.2. Решения сравнений 424
10.3. Китайская теорема об остатках 428
10.4. Свойства функции ф 433
10.5. Порядок целого числа 439
Некоторые специальные вопросы
теории рекурсии 448
11.1. Однородные линейные рекуррентные
отношения 448
11.2. Неоднородные линейные рекуррентные
отношения 460
11.3. Конечные разности 469
11.4. Факториальные многочлены 473
11.5. Суммирование разностей 483

Снова о комбинаторных подсчетах 489
12.1. Задачи о размещении 489
12.2. Числа Каталана 495
12.3. Общее включение-исключение
и разупорядочения 502
12.4. Ладейные полиномы и запрещенные позиции 509
ПрОИЗВОДЯЩИе фуНКЦИИ 523
13.1. Определение производящей функции 523
13.2. Производящие функции и рекуррентные
отношения 525
13.3. Производящие функции и комбинаторные
подсчеты 535
13.4. Разбиения 542
13.5. Экспоненциальные производящие функции 549
Некоторые специальные вопросы
теории графов 556
14.1. Алгебраические свойства графов 556
14.2. Планарные графы 580
14.3. Раскраска графов 586
14.4. Пути и циклы Гамильтона 600
14.5. Взвешенные графы и алгоритмы поиска
кратчайшего пути 611
Деревья 624
15.1. Свойства деревьев 624
15.2. Бинарные деревья поиска 631
15.3. Взвешенные деревья 638
15.4. Обход бинарных деревьев 649
15.5. Остовные деревья 658
15.6. Минимальные остовные деревья 682
Сети 691
16.1. Сети и потоки 691
16.2. Паросочетание 707
16.3. Сети Петри 716

Теория вычислений 725
17.1. Регулярные языки 725
17.2. Автоматы 731
17.3. Грамматики 741
ТеорИЯ КОДОВ 753
18.1. Введение 753
18.2. Порождающие матрицы 757
18.3. Коды Хемминга 767
Перечисление цветов 775
19.1. Теорема Бернсайда 775
19.2. Теорема Пойа 781
Кольца, области целостности
И ПОЛЯ 788
20.1. Кольца и области целостности 788
20.2. Области целостности 797
20.3. Полиномы 801
20.4. Алгебры и полиномы 808
Характеры групп и полугрупп 819
21.1. Комплексные числа 819
21.2. Характеры групп 820
21.3. Характеры полугрупп 825

[Munin]

Обычно в учебниках по "Алгоритмам и структурам данных" необходимая математика и так объясняется по месту. Хватает школьных знаний. Зачем вам дополнительно целый курс?

Если что и нужно, так это немного линала (чтобы знать, как умножают матрицы), и матана (чтобы знать, что такое "О-большое").

-- 23.09.2017 14:02:00 --

Из перечисленного можете выбросить всё, кроме главы 15 (деревья). Главы 14 (спец. вопросы графов) и 17 (языки и грамматики) вам понадобятся в особых случаях, их можно будет добрать потом (в "джентльменский набор" алгоритмов они не входят). Остальное вам не встретится в жизни вообще никогда.

[romzes200677]

Огромное Вам спасибо ,Munin , за бесценную подсказку. Вы сэкономили мне огромное количество времени.Буду доучивать оставшиеся темы и приниматься за алгоритмы

[mihaild]

Добавлю.
16.1 жизненно необходимая часть - потоки встречаются очень часто, а распознать их довольно сложно.
17.1 (регулярные языки) нужны почти везде (хотя их практика довольно далека от теории - например, в большинстве стандартов регулярными выражениями можно задать нерегулярный язык).
10я глава явно нужна для криптографии, 11 - для численных методов, 18 - для написания сетевых протоколов, файловых систем и подобных штук. Но в любом случае если заниматься этими областями, то нужен материал заметно более солидный, чем одна глава из общей книги, так что их можно пропустить без вреда для практики.
Про остальное соглашусь с Munin.

[Dmitriy40]

(Вот не знаю что за вакансия java junior, потому скажу для прикладника)

mihaild в сообщении #1250041 писал(а):

18 - для написания сетевых протоколов, файловых систем и подобных штук.

Вот с этим немного не соглашусь, для прикладного программирования (написании программ работающих с аппаратурой) довольно часто приходится или придумывать свои протоколы, или обслуживать уже готовые - и везде встаёт вопрос контроля ошибок, а значит 18.3 точно будет полезна, а при разработке чего-то своего нестандартного - и 18.2.
Иногда похожие вопросы возникают и в других областях, вон например пару дней назад коды Хэмминга (точнее понятие его расстояния) пригодилось для оптимизации перебора координат точек многогранника.
Потому если не изучить 18 главу, то хотя бы ознакомиться будет полезно.

Полезность знакомства с регуляркой (17.1) поддерживаю. И с 17.2 тоже, хотя бы в общих чертах. Чтобы представлять какие вопросы удобно решаются этими методами.
Подчеркну, владеть "на отлично" не так уж обязательно, но иметь общее представление и знать когда применять и что и где искать для уточнения своих знаний в случае необходимости - полезно.
В остальном согласен с товарищами выше.

[arseniiv]

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

[Anton_Peplov]

arseniiv в сообщении #1250048 писал(а):

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

Хм. Это ж какие объёмы текста надо обрабатывать, чтобы программа стала заметно (для человеческого восприятия) лагать из-за такой, не побоюсь этого слова, фигни? Или мы интернет-поисковик пишем?

[arseniiv]

А вы знаете, какой нужен регэкс, чтобы соответствовать какому-то RFC насчёт, например, формата e-mail? Ну вообще, конечно, здесь с оптимизацией всё ровно так же как и везде — делать её надо только если есть доказательства, что именно здесь узкое место, и когда оно действительно мешает.

[mihaild]

Anton_Peplov в сообщении #1250142 писал(а):

Это ж какие объёмы текста надо обрабатывать, чтобы программа стала заметно (для человеческого восприятия) лагать из-за такой, не побоюсь этого слова, фигни?

Используется синтаксис Python

import re,timeit
print(timeit.timeit(lambda: re.findall('a?' * 25 + 'a' * 25, 'a' * 25), number=1)

(спойлер про время)

обратите внимание на разницу в единицах измерения

[slu4ayniyProcess]

А в чем собственно такая сложность. Java она же ведь либо в каком то энтерпрайзе либо в android.
Если вы писали на дельфи, то знания по основным структурам данных, у вас должны быть. А алгоритмы они не встречаются ни там ни там. Либо эти алгоритмы на столько стандартны, что уже давно реализованы и предоставляются в виде готовых библиотек, зачастую в родном sdk.
В общем, если вы хотите найти работу java программистом, то явно не тем занимаетесь. Нужно сам язык учить. И фреймворки изучать(android sdk или spring какой нибудь). Плюс сразу лучше писать, какие то тестовые проекты, которые можно показать на собеседовании будет. Да и сам лучше разберешься что к чему.
А чтобы отделаться от вопросов по "алгоритмам и структурам данных", которые любят задавать на собеседовании (а что еще задавать junior'у в самом деле?=) ), достаточно прочитать несколько статей с хабра про самые стандартные.

А уж потом, как на работу устроишься, можно будет углубляться в алгоритмы, и читать книги по математике. Правда скорее всего эти знания на текущей работе не пригодятся. Там где они нужны, это немного другие специальности.
Кстати поверьте, те кто вам на собеседовании задает вопросы по "алгоритмам и структурам данных", сами разбираются в этих алгоритмах достаточно поверхностно (на уровне тех же статей с хабра). Да и что говорить, для некоторых хорошо зарабатывающих программистов с опытом, до сих пор может быть загадкой как работает HashMap например. При этом это им не мешает его использовать в работе.

[Munin]

slu4ayniyProcess в сообщении #1250179 писал(а):

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

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