ДС18о01-введение (1238916)
Текст из файла
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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
