Фундаментальные алгоритмы
Фундаментальные алгоритмы и структуры данных
[править]Задачей этого курса является создание учебника с описанием базового набора алгоритмов:
- Сортировка и поиск
- Комбинаторные алгоритмы
- Получисленные алгоритмы
- алгоритмы на графах
- алгоритмы работы со строками
- структуры данных
В идеале этот курс должен плавно провести начинающего программиста от базовых понятий алгоритмической науки к овладению тем базисом, который позволит приступить к решению прикладных проблем. Естественно как и во всяком курсе посвященному алгоритмике для начала будет дано определение понятия алгоритма.Будут приведены примеры простейших математических алгоритмов.Крайне приветствуется знание языков Pascal или С.Хотя базовые конструкции такие как цикл или условный оператор вводятся по ходу изложения очень желательно знание их читателем курса. Поскольку автор нематематически-ориентирован, то сам должные математические выкладки сделать не сможет, но был бы очень благодарен в том случае, если бы они появились.Несомненно речь идет о доказательствах сложности алгоритмов.
Ответственность за этот курс берет на себя: Guranvir
§1. Понятие алгоритма
[править]В этом параграфе мы с вами обсудим что такое алгоритм и что не является алгоритмом. Рассмотрим его свойства, которые нам в последствии будут важны. Не обойдем вниманием и машину Тьюринга и его же с Чёрчем тезис.Одна из основных проблем алгоритмики это эффективность данного алгоритма, а поэтому мы рассмотрим по каким критериям устанавливают его эффективность. Совершенно неотвратимо вслед за этим нам придется осветить вопрос сложности алгоритмов. Но не надо пугаться такого обилия тем: по таинственной стране теории алгоритмов мы совершим небольшое турне подобно туристам приехавшим посмотреть на экзотику. Однако при всем том все ж помните что эта "экзотика" является фундаментом всего здания алгоритмической науки.
Ну а вот здесь уже никакой легкой прогулки не будет. Мы начинаем погружение в океан алгоритмов и в одну из его главных частей: алгоритмы сортировки. Сначала мы поплаваем в прибрежной зоне, где нам компанию составит алгоритм сортировки пузырьком и алгоритм сортировки вставками.Однако стремление к быстроте нас увлечет в глубины, где мы встретим алгоритм быстрой сортировки, сортировки слиянием и множество других. Так что наберите в грудь побольше воздуха и помните большой путь начинается с малого:)