Алгоритмы, часть I from Coursera

What's inside

Syllabus

Введение в курс

Введение в алгоритмы, часть I.

Система непересекающихся множеств

Мы демонстрируем наш базовый подход к разработке и анализу алгоритмов через рассмотрение проблемы динамической связности. Мы представляем тип данных непересекающихся множеств и рассматриваем несколько вариантов его реализации (быстрый поиск, быстрое объединение, взвешенное быстрое объединение и взвешенное быстрое объединение со сжатием пути). Наконец, мы применяем тип данных непересекающихся множеств для решения проблемы перколяции из физической химии.

Анализ алгоритмов

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

Стеки и очереди

Мы рассмотрим два фундаментальных типа данных для хранения коллекций объектов: стек и очередь. Каждый из них реализуется с помощью односвязного списка или массива изменяющегося размера. Мы представим две продвинутые функции Java, упрощающие клиентский код: обобщенные коллекции и итераторы. Наконец, будут рассмотрены различные применения стеков и очередей, начиная от разбора арифметических выражений и заканчивая моделированием систем массового обслуживания.

Элементарные методы сортировки

Мы познакомим вас с проблемой сортировки и интерфейсом Comparable Java. Мы изучим два элементарных метода сортировки (сортировку выбором и сортировку вставкой), а также разновидность одного из них — сортировку методом Шелла. Также мы рассмотрим два алгоритма для равномерного перемешивания массива. В завершение мы продемонстрируем применение сортировки на практике для вычисления выпуклой оболочки множества точек с помощью алгоритма сканирования Грэма.

Сортировка с объединением

Мы изучим алгоритм сортировки с объединением и покажем, что он позволяет отсортировать любой массив из n элементов с максимальным количество сравнений n lg n. Также будет рассмотрена нерекурсивная версия этого алгоритма («снизу вверх»). Мы докажем, что любой алгоритм сортировки, основанный на сравнении, в худшем случае должен выполнить не менее n lg n сравнений. Мы обсудим применение различных схем упорядочения сортируемых объектов и связанную с этим концепцию устойчивости.

Быстрая сортировка

Мы изучим и реализуем алгоритм рандомизированной быстрой сортировки и проанализируем его эффективность. Кроме того, рассмотрим рандомизированный быстрый выбор — вариант быстрой сортировки, находящий k-й наименьший элемент за линейное время. В завершение мы рассмотрим 3-направленную быструю сортировку — вариант быстрой сортировки, особенно хорошо работающий при наличии дублирующихся ключей.

Приоритизированные очереди

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

Таблицы элементарных символов

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

Сбалансированные деревья поиска

В этой лекции наша цель состоит в создании таблицы символов с гарантированной логарифмической эффективностью поиска и вставки (а также множества других операций). Мы начнем с рассмотрения 2-3-деревьев, которые легко анализировать, но сложно реализовать. Затем рассмотрим красно-черные бинарные деревья поиска, которые послужат новым способом реализации 2-3-деревьев в виде бинарных деревьев поиска. Наконец мы представим B-деревья — обобщение 2-3-деревьев, широко применяющееся при реализации файловых систем.

Применение БДП в геометрии

Мы начнем с поиска в 1-мерных и 2-мерных диапазонах, цель которого — найти все точки в заданном 1-мерном или 2-мерном диапазоне. Для выполнения данной задачи рассмотрим k-мерные деревья — естественное обобщение БДП, ключи которого — точки на плоскости (или в пространствах более высокого порядка). Также рассмотрим проблемы пересечений, когда требуется найти все пересечения среди множества отрезков или прямоугольников.

Хэш-таблицы

Вначале мы опишем желательные свойства хэш-функции и ее реализацию в Java, включая фундаментальное допущение о равномерности хэширования, определяющее потенциальную успешность хэширования. Затем рассмотрим две стратегии реализации хэш-таблиц — раздельное связывание цепочками и линейное исследование. Обе стратегии имеют постоянную по времени эффективность поиска и вставки при удовлетворении допущения о равномерности хэширования.

Области применения таблиц символов

Рассмотрим различные практические области применения таблиц символов, включая множества, клиенты словарей, клиенты индексирования и разреженные векторы.

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

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

Дает практические знания о научном анализе эффективности алгоритмов, которые высоко ценятся на собеседованиях и в работе

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

Хорошее введение в анализ эффективности алгоритмов, но без сертификата по его окончании

Reviews summary

Highly engaging java algorithms

This course on algorithms in Java receives stellar reviews, with all 3 reviewers giving it a perfect score. Students appreciate the practical focus and clear explanations of complex concepts.

Activities

Be better prepared before your course. Deepen your understanding during and after it. Supplement your coursework and achieve mastery of the topics covered in Алгоритмы, часть I with these activities:

Review what is a data structure?

Show steps

Starting the course with a clear idea of what data structures are and the importance of their use will improve students' learning outcomes, especially in the early units of the course.

Browse courses on Data Structures

Show steps

Review your notes on data structures from previous coursework
Read a few articles on data structures online

Решить задачу с Leetcode

Show steps

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

Show steps

Выбрать задачу
Разобраться с условиями
Решить задачу
Протестировать решение

Пройти онлайн-урок по алгоритмам и структурам данных

Show steps

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

Show steps

Найти онлайн-уроки
Просмотреть уроки
Выполнить задания

Four other activities

Expand to see all activities and additional details

Show all seven activities

Attend a workshop on data structures and algorithms

Show steps

Attending a data structures workshop provides a great opportunity to improve practical knowledge and interact with experts and peers.

Browse courses on Data Structures

Show steps

Find a workshop that fits your schedule and interests
Register for the workshop
Attend the workshop and actively participate

Solve problems involving data structures

Show steps

The best way to improve skills with data structures is to reinforce the learning through repetitive problem solving. This will enhance the transfer of classroom learning to real-world applications.

Browse courses on Data Structures

Show steps

Find a website or book with data structure problems
Set aside time each week to solve problems

Пройти тренировочные тесты

Show steps

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

Show steps

Найти тренировочные тесты
Пройти тесты
Проанализировать результаты

Create a presentation on a data structure

Show steps

Creating a presentation will provide a thorough understanding of a specific data structure, allowing students to master the material.

Browse courses on Data Structures

Show steps

Choose a data structure to present on
Gather information on your chosen structure
Create a presentation using slides or a whiteboard

Career center

Learners who complete Алгоритмы, часть I will develop knowledge and skills that may be useful to these careers:

Computer Scientist

If you're interested in a career as a computer scientist, taking this course in Algorithms, Part I can provide you with a strong foundation in the subject. The course covers essential concepts such as data structures and algorithms, which are fundamental to computer science. With a fit score of 88, this course is highly recommended for anyone interested in pursuing a career in computer science.

See salaries and explore the career path for Computer Scientist

Software Engineer

A career as a software engineer requires a strong understanding of algorithms and data structures. This course can help you master these concepts, providing you with a solid foundation for success in the field. The course covers the basics of algorithm analysis, helping you to develop the skills needed to evaluate the efficiency of different algorithms and choose the best one for a given task. With a fit score of 85, this course is highly recommended for aspiring software engineers.

See salaries and explore the career path for Software Engineer

Computer Programmer

Computer programmers write and maintain computer programs. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for writing efficient and effective computer programs. With a fit score of 80, this course is recommended for those interested in a career as a computer programmer.

See salaries and explore the career path for Computer Programmer

Data Scientist

Data scientists use data to solve real-world problems. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for managing and analyzing large datasets. With a fit score of 78, this course may be useful for those interested in a career as a data scientist.

See salaries and explore the career path for Data Scientist

Data Analyst

For those seeking a role in data analysis, this course in Algorithms, Part I offered by Princeton University would be very helpful. It will help you build a solid foundation in data structures and algorithms, which are essential for success as a data analyst. The course also covers practical applications of algorithms in Java programming, so you can gain hands-on experience with the tools used in the industry. With a fit score of 77, this course is a great choice for anyone interested in pursuing a career in data analysis.

See salaries and explore the career path for Data Analyst

Web Developer

Web developers design and develop websites. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for managing and analyzing large datasets. With a fit score of 75, this course may be useful for those interested in a career as a web developer.

See salaries and explore the career path for Web Developer

Information Security Analyst

Information security analysts protect computer systems and networks from unauthorized access, use, disclosure, disruption, modification, or destruction. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for managing and analyzing large datasets. With a fit score of 75, this course may be useful for those interested in a career as an information security analyst.

See salaries and explore the career path for Information Security Analyst

Quantitative Analyst

Quantitative analysts use mathematical and statistical models to analyze data and make predictions. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for managing and analyzing large datasets. With a fit score of 75, this course may be useful for those interested in a career as a quantitative analyst.

See salaries and explore the career path for Quantitative Analyst

Actuary

Actuaries use mathematical and statistical methods to assess risk and uncertainty. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for managing and analyzing large datasets. With a fit score of 75, this course may be useful for those interested in a career as an actuary.

See salaries and explore the career path for Actuary

Systems Analyst

Systems analysts design and implement computer systems. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for managing and analyzing large datasets. With a fit score of 75, this course may be useful for those interested in a career as a systems analyst.

See salaries and explore the career path for Systems Analyst

Artificial Intelligence Engineer

Artificial intelligence engineers design and develop artificial intelligence systems. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for managing and analyzing large datasets. With a fit score of 75, this course may be useful for those interested in a career as an artificial intelligence engineer.

See salaries and explore the career path for Artificial Intelligence Engineer

Machine Learning Engineer

Machine learning engineers build and maintain machine learning systems. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for managing and analyzing large datasets. With a fit score of 75, this course may be useful for those interested in a career as a machine learning engineer.

See salaries and explore the career path for Machine Learning Engineer

Business Analyst

Business analysts analyze business processes and develop solutions to improve efficiency and effectiveness. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for managing and analyzing large datasets. With a fit score of 75, this course may be useful for those interested in a career as a business analyst.

See salaries and explore the career path for Business Analyst

Operations Research Analyst

Operations research analysts use mathematical and analytical techniques to solve problems in business and industry. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for managing and analyzing large datasets. With a fit score of 75, this course may be useful for those interested in a career as an operations research analyst.

See salaries and explore the career path for Operations Research Analyst

Database Administrator

Database administrators manage and maintain databases. This course in Algorithms, Part I can help you develop the skills needed to succeed in this field. The course covers topics such as data structures and algorithms, which are essential for managing and analyzing large datasets. With a fit score of 75, this course may be useful for those interested in a career as a database administrator.

See salaries and explore the career path for Database Administrator