ДС18о01-введение (Лекции Северов Часть 1)

Carnegie MellonВведениеАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 1, 07 сентября, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771Алгоритмы и структуры данных (1/2)¢¢Часть I Теоретические основы информатики§ Формализация понятия алгоритм§ Машина Тьюринга§ Алгорифмы МарковаЧасть II Структуры данных§ О диалектах Си§ Составные типы данных§ Абстрактные типы данных2Алгоритмы и структуры данных (2/2)¢¢Часть III Основы теории алгоритмов§ Анализ эффективности алгоритмов§ РекурсияЧасть IV Основные (базовые) алгоритмы§ Задачи сортировки§ Задачи поиска§ Поиск на графах3Литература ?ISBN:Тысяч Тысяч978-5-8459- страниц рублейЯзык программирования C.Лекции и упражнения0986-21,03,0Язык программирования C++.Лекции и упражнения2048-51,23,0Программирование.

Принципы ипрактика с использованием C++1949-61,32,9Язык программирования C++.Базовый курс1839-01,12,2Алгоритмы.Построение и анализ2016-41,33,8Алгоритмы на C++2070-61,12,94Предусловие – умения…алгоритмически мыслитьМожно проверить с помощью http://lightbot.comформально излагать решение задачиМожно проверить с помощью https://drakon-editor.comсамостоятельно изучать ЯПМожно проверить с помощью http://cs.mipt.ru/c_intro5Из википедии (1/2)¢Программи́рование§ процесс создания компьютерных программ¢Компью́терная програ́мма1. комбинация компьютерных инструкций и данных,позволяющая аппаратному обеспечению вычислительнойсистемы выполнять вычисления или функции управления(стандарт ISO/IEC/IEEE 24765:2010)[1];2.

синтаксическая единица, которая соответствует правиламопределённого языка программирования, состоящая изопределений и операторов или инструкций, необходимыхдля определённой функции, задачи или решения проблемы(стандарт ISO/IEC 2382-1:1993)[2].6Из википедии (2/2)¢Програ́мма (от греч. προ — пред, греч. γράμμα — запись)термин, в переводе означающий «предписание», то есть предварительноеописание предстоящих событий или действий. Данное понятиенепосредственно связано с понятием алгоритм. …¢Алгори́тмнабор инструкций, описывающих порядок действий исполнителя длядостижения некоторого результата.

<…> Независимые инструкции могутвыполняться в произвольном порядке, параллельно, если это позволяютиспользуемые исполнители¢Инструќ ция или опера́тор (англ. statement)наименьшая автономная часть языка программирования; команда илинабор команд. Программа обычно представляет собой последовательностьинструкций.7Понятия программированияПрограммаопределённый наборпредписанийпрограммистДанныенеопределённый наборинформацииПрограммаПроцессожидаемый набор событийДанныеПрограммируемаясистема(исполнитель)РесурсыПроцессРесурсыВремя работы¢§§¢¢ПрограммистаСистемыЭнергияПространство8Из определений ГОСТ 33707 (1/3)¢Программа§ Данные, предназначенные для управленияконкретными компонентами системыобработки информации в целях реализацииопределенного алгоритма.¢Язык программирования§ Искусственный язык для изложения текстовпрограмм9Из определений ГОСТ 33707 (2/3)¢Алгоритм§ 2015: Конечное упорядоченное множествоточно определенных правил для решенияконкретной задачи§ 1984: Конечный набор предписаний,определяющий решение задачи посредствомконечного количества операций¢Алгоритмический язык§ Искусственный язык, предназначенный длявыражения алгоритмов10Из определений ГОСТ 33707 (3/3)¢Язык спецификаций§ Язык прикладного характера, который,1.2.3.4.5.часто являясь ориентированным накомпьютеры синтезом естественного языка иискусственного языка,используются для выражения требований ксистеме или компоненте,для описания их конструкции,а иногда и протоколов проверки,для проектирования, исследования идокументирования указанных характеристик.11[Около]компьютерные явления¢¢¢Модель – упрощённоепредставление законовповедения частей иотношений системыЯзык модели - знаковаяподсистема фиксации,переработки и передачиинформацииМашина – модельныйисполнитель, которомунаправленыпредписания на языкемоделиРынки¢ Потребители¢ Задачи¢Алгоритмы¢ Программы¢ Система/Аппаратура¢ Цифровые схемы¢ Аналоговые схемы¢Физические явления в[не]линейных структурах¢12Некоторые [около]компьютерные языки¢Задачи¢Языки спецификаций¢Языки проектирования¢Алгоритмы¢Алгоритмические языки¢Программы¢Языки программирования¢Архитектура «системы»¢Языки обращений к «системе»¢Архитектура аппаратуры¢Языки команд аппаратуры¢Блоки архитектуры¢Языки микрокоманд¢Цифровые схемы¢Языки цифровых схем¢Аналоговые схемы¢Языки аналоговых схем¢Языки физических моделей¢Физические явления в[не]линейных структурах13Алгоритм интуитивноПоиск НОД(a,b), где a,b > 0, a < b§ Перебор: 1 – подходит, 2 - ?, 3 - , … а -?§ Алгоритм Эвклида1.

Разделить первое на второе и получитьостаток2. Если остаток равен нулю, то второе –результат3. Иначе: заменить первое на второе,второе – на остаток и перейти к шагу 114Свойства алгоритмаДискретность данных и действий над нимиПонятность: доступность и однозначность правилКонечность: решение задачи за конечное число шаговОпределённость: воспроизводимость результатаМассовость: применимость к различным данным15Алгоритм формально:отступление к функцииИсходныеданныеРезультаты16Алгоритм формально:отступление к множествам (1/2)1. Элемент множестваа2.

МножествоА3. Элемент принадлежит множеству а Î А4. Не принадлежитаÏА5. А = {a,b,c}6. Æ7. Подмножество AÌB Û " a Î A : a Î B8. A = B Û A Ì B и B Ì A17Алгоритм формально:отступление к множествам (1/2)9. ОбъединениеАÈВ10.ПересечениеAÇB = {aÎA:aÎB}11.РазностьA \ B = {aÎA:aÏB}12.Декартово (прямое) произведение A х BА={0,1}, B={a,b,c}, A x B = {0a, 0b, 0c, 1a, 1b, 1c}A1 x A2 x A3 x … x AnA0=Æ, A1=A, A2=A x A,An = A x A x A x … x An18Алгоритм формально:функция формально¢Множество F есть функция из множества А в B тогда и толькотогда, когда верно следующее.1.

F Í A x B,2. если …1. aÎA,2. b,cÎB3. abÎF,4. acÎF,… то b=c.10,1515,256,914,2119Алгоритм формально: итог§A={a1,a2,…,ap} - алфавит§A* = A0 È A1 È A2 È …È An –множество всех слов,состоящих не более чем из n символов.§F: A* ® A*20Алан ТьюрингЭмиль ПостНорберт ВинерАлонзо ЧёрчАндрей Марков21ПрограммаРеализация алгоритма на языкепрограммирования, определяющем…1.2.3.4.Действия - операции и операторыДанные - типы и экземплярыКонструкцию сложных данных и действийВзаимодействие со средой22Масштабы событий вашей программы¢Ваш исполнительЯдропроцессораПамятьУBBУBBУBBУBBКрупнее:§ Среда разработк觧§§СоединительРедактированиеТрансляцияСвязывание…§ Среда исполненияЗагрузка§Выделение ресурсов§Нормирование работы иреагирование на запросы§Освобождение ресурсов§…Мельче – за рамками семестра§¢Ваш процесс§§¢Выполнение операцийИзменение состоянияДругие процессы23Создание программыРедактирование⇓ Текст программыТрансляция⇓ Объектный кодКомпоновка⇓ Загрузочный кодЗагрузка⇓ Исполняемый кодВыполнение, отладка⇓ Результат24Создание программы вместеРедактирование⇓ Текст программы⇐ Ваши изменения вручнуюТрансляция⇓ Объектный код⇐ Библиотечный исходный текстКомпоновка⇓ Загрузочный код⇐ Библиотечный машинный кодЗагрузка⇓ Исполняемый код⇐ Решения среды исполненияВыполнение, отладка⇓ Результат⇐ Внешние данные, коды, события25Создание программы в окруженииРедактированиеG Предписания редактору⇓ Текст программы⇐ Ваши изменения вручнуюТрансляцияE Предписания трансляции⇓ Объектный код⇐ Библиотечный исходный текстКомпоновкаE Предписания компоновки⇓ Загрузочный код⇐ Библиотечный машинный кодЗагрузкаE Предписания загрузки⇓ Исполняемый код⇐ Решения среды исполненияВыполнение, отладка E Предписания исполнения⇓ Результат⇐ Внешние данные, коды, события26Carnegie Mellon(Само)обман¢Что есть (само)обман ?§§§§§¢Брать чужой код: копируя, перенабирая, подглядывая, принимая файлыПересказывать: устное описание кода одним человеком другомуНатаскивание: помощь другу в построчном написании заданийПоиск решения в сетиКопирование кода предыдущих кусов и экзаменовЧто НЕ есть (само)обман?§ Объяснять как использовать инструменты или системы§ Помогать другим в вопросах конструкции верхнего уровня27.