Введение в курс и ожидания В этой главе представлен курс CSE 373 - Введение в алгоритмы. Преподаватель подчеркивает важность взаимодействия учащихся и поощряет задавать вопросы на протяжении всего занятия. Он также обсуждает механику курса, включая ежедневные задачи, которые необходимо решать перед каждым занятием.
Учебная программа и учебник "Руководство по разработке алгоритмов" рекомендуется в качестве учебного пособия для этого курса. Учебная программа охватывает предварительные требования, критерии оценивания (включая ежедневные задачи и домашние задания), промежуточные экзамены, технологию подачи заявок на экзамены (возможно, онлайн с помощью браузера lockdown), партнерскую систему для домашних заданий, доску обсуждений на платформе Piazza.
Ожидания от студентов Студентам рекомендуется ознакомиться со всеми материалами, предоставленными преподавателем на его веб-сайте. Они должны активно участвовать в дискуссиях во время лекций или задавать вопросы либо устно, либо через функцию чата, если они предпочитают не высказываться напрямую. Важно досконально понимать концепцию алгоритма, поскольку это отразится на результатах экзамена.
Рабочее время и оценка - Часы работы офиса доступны через Zoom по вторникам и четвергам. - Инструктору не нравится выставлять оценки и разбираться с жалобами на выставление оценок. - Ошибки при выставлении оценок распределяются случайным образом, но жалобы на выставление оценок распределяются неравномерно.
Политика курса - Учебное пособие по курсу является вторым изданием. - Учащиеся с ограниченными возможностями должны проконсультироваться в Отделе поддержки учащихся с ограниченными возможностями. - Рекомендуется серьезно относиться к психическому здоровью в это напряженное время пандемии. - Списывание приведет к последствиям академической нечестности. Новые способы обмана могут возникнуть из-за онлайн-формата, но существуют и новые методы обнаружения. - Допускается одно бесплатное продление на неделю для выполнения домашних заданий.
Расписание лекций В семестре будут рассмотрены вводные материалы по алгоритмам, структурам данных, алгоритмам сортировки, графовым алгоритмам, алгоритмам перебора / алгоритмам экспоненциального времени, динамическому программированию и NP-полноте
Доказательство корректности алгоритмов Чтобы убедиться в правильности алгоритма, нам нужно доказать его корректность. Это означает, что алгоритм всегда выдает правильный результат в каждом экземпляре. Если правильность алгоритма не может быть доказана, он считается неверным.
Описание алгоритмов - Существуют разные способы описания алгоритмов: на английском языке, псевдокоде или языке программирования. - Описание идеи алгоритма на английском языке и использование псевдокода для уточнения деталей может помочь прояснить понимание. - Использование визуальных представлений также может способствовать пониманию.
Поиск оптимального тура для робота - Проблема заключается в поиске оптимального маршрута для робота, паяющего точки печатной платы. - Один из предложенных подходов заключается в использовании эвристики ближайшего соседа, начиная с одной точки и посещая ближайших непосещенных соседей последовательно, пока не будут посещены все точки. - Однако такой подход не гарантирует нахождение кратчайшего тура, как показывает контрпример.
Проблема с роботизированным туром - Эвристика ближайшей пары в определенных случаях может привести к неверным результатам. - Пробовать все возможные туры - правильное, но неэффективное решение для поиска оптимального тура. - Задача коммивояжера - это пример NP-полной задачи.
Поиск встречных примеров - Поиск встречных примеров, нарушающих эвристику, помогает выявить их ограничения. - Связи и экстремальные сценарии полезны для демонстрации некорректности.
Доказательство корректности алгоритма с помощью индукции - Математическая индукция - это метод, используемый для доказательства правильности алгоритмов путем демонстрации того, что это верно для небольших случаев, а затем рассуждения, основанные на предположении, что это верно до n - 1. - Рекурсия и индукция - тесно связанные понятия, поскольку рекурсия также включает в себя разбиение проблем на более мелкие подзадачи.