Словарь - это абстрактный тип данных, который связывает ключи со значениями. Его ещё называют ассоциативный массив, карта, таблица символов, коллекция. Будет две статьи на эту тему, где мы покажем шесть картинок / способов реализации словаря, которые отличаются друг от друга по времени работы и по требованию к памяти.
Программист и Преподаватель
Способы хранения графа в памяти компьютера
В предыдущей статье мы познакомились с терминами и определениями теории графов. В этой же статье обсудим различные способы представления графа в памяти компьютера для его обработки. Покажем, какие структуры данных можно использовать, а также проговорим преимущества и недостатки каждого способа.
Теория графов. Термины и определения в картинках
В этой статье мы познакомимся с основными терминами и определениями Теории графов. Каждый термин схематично показан на картинках.
Граф - это топологичекая модель, которая состоит из множества вершин и множества соединяющих их рёбер. При этом значение имеет только сам факт, какая вершина с какой соединена.
Пирамидальная сортировка выбором
Один из самых необычных алгоритмов сортировки массива - это HeapSort, в основе которого лежит алгоритм сортировки выбором, используется структура данных «куча» для быстрого нахождения максимального элемента, а также способ хранения двоичного дерева в линейном массиве. Разберёмся со всем по порядку.
Идеальное хэширование
Какова сложность поиска элемента по ключу?
Это зависит от того, какую структуру данных использовать.
В односвязном списке - линейная сложность.
В отсортированном массиве или в двоичном дереве поиска - логарифмическая сложность.
В хэш-таблице - сложность константная. Но это в лучшем случае. А в худшем … стремится к линейной…
А можно ли создать идеальную хэш-таблицу, чтобы сложность поиска элемента даже в худшем случае оставалась константной?
В общем случае - нет. Но если список всех ключей установлен заранее и не изменяется, а хэш-коды у всех ключей различны, то можно построить идеальную хэш-таблицу без коллизий, где поиск любого элемента происходит за несколько тривиальных операций, причём, количество этих операций не зависит от размера хэш-таблицы.
Идеально! Поговорим о том, как это сделать.
Кстати, на курсе "Алгоритмы и структуры данных" на платформе OTUS у нас есть отдельный модуль, посвящённый вопросам создания хэш-таблиц.
Удаление узлов из красно-чёрного дерева
Удаление узлов из красно-чёрного дерева — непростая задача, поэтому имеет смысл разделить её на несколько частей и рассмотреть каждый случай отдельно.
Использовано изображение портала cartoonbank.ru
В прошлой статье мы рассмотрели правила формирования красно-чёрного дерева поиска и рассмотрели случаи балансировки при добавлении элементов.
Теперь поговорим об удалении элементов.
Возьмём, для примера, вот такое красно-чёрное дерево:
Алгоритм Джонсона на орграфе с отрицательными дугами
Статья подготовлена в преддверии старта курса «Алгоритмы и структуры данных»
Алгоритм Джонсона находит кратчайший путь между всеми парами вершин во взвешенном ориентированном графе с отрицательными весами без негативных контуров.
О, как звучит! Давайте разберём условие задачи по частям.
Ход конём по битам. Шахматный Bitboard
Шахматный конь стоит на шахматной доске и задумчиво смотрит в шахматную даль.
Сколько разных ходов он может сделать?
Хвала изобретателю шахмат, на доске 64 клетки.
Хвала архитектору компьютеров — у типа ulong тоже 64 бита.
Это же надо было случиться такому совпадению!
Напрашивается гениальная идея — хранить всю доску в одном целом числе! Для этого решения существует даже специальный термин — Bitboard — битовая доска.
Так как же быстро найти количество ходов шахматного коня, используя эту идею?
Балансировка красно-чёрных деревьев — Три случая
В этой статье мы дадим определение, перечислим правила размещения элементов в красно-чёрном дереве, рассмотрим алгоритм балансировки и закрепим сказанное на примере. Более подробно эту тему, а также другие виды двоичных деревьев поиска мы изучаем на курсе «Алгоритмы для разработчиков».
Мат конём и слоном. База решений
Попросите его поставить мат конём и слоном.
Хотите озадачить начинающего программиста?
Попросите его рассчитать мат конём и слоном.
Шахматные задачи будоражат воображение программиста,
именно поэтому для практической демонстрации комбинаторики
я выбрал самую сложную шахматную задачу из цикла «мат одинокому королю».
Изучение C# — Практический подход
Проблема в том, что для практического опыта недостаточно книжек и научных статей. Для эффективной практической работы требуется регулярное живое общение, интересный учебный план, обратная связь, а также самостоятельные задания с обязательной проверкой, и последовательный доступ к урокам. Речь пойдёт о проекте "Формула программиста".
Об альтернативном образовании вообще и про C# в частности
Только вот конкретных решений этой проблемы почти не видно — что именно нужно поменять и как следует строить современную систему образования, чтобы она отвечала духу нового времени, помогала развиваться творческим способностям и была при этом эффективной.
У меня есть некоторые свои собственные соображения и наработки для решения этой проблемы в рамках своей специальности — способа изучения языка программирования C#, речь пойдёт о проекте www.videosharp.info
Как я создавал методику изучения C#
В этом я нашёл своё призвание — мотивировать к изучению программирования.
Я не ставлю своей целью «научить писать программы», потому что этому нельзя научить, этому можно только научиться самостоятельно. Моя цель — сделать этот процесс максимально интересным, увлекательным, захватывающим, организовать «тусовку», сообщество, в котором можно и хочется решать задачи, развивать свои навыки программирования. Общество, в котором можно видеть успехи коллег, чтобы было к чему стремиться, кого обгонять.
Как не надо учить английские слова
Как я писал модуль обновления на C#
Я решил не искать стандартных громоздких решений, а изобрести свой собственный велосипед для автоматического обновления установленных программ.
Честно, мне самому не очень нравятся приложения, которые вечно скачивают обновления, но в моём случае проще автоматизировать этот процесс, чем писать должностные инструкции и заставлять коллег скачивать обновления вручную (а потом бегать по всем этажам и делать это самому).
Information
- Rating
- Does not participate
- Location
- Висагинас, Литва, Литва
- Works in
- Date of birth
- Registered
- Activity